荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: huhaiming (一生只爱她), 信区: Program
标 题: problem D
发信站: 荔园晨风BBS站 (Sat May 24 20:05:43 2003), 站内信件
Traveling in Solar System
Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 0 Accepted Submit: 0
------------------------------------------------------------------------
--------
It is in the year of 3114. Bernie lives on moon. This summer his
younger
sister Rosie will come to see him. Bernie is very excited about this
because
he hasn't seen his lovely sister for years! So, he decides to take his
little
sister to travel around solar system. He soon asks The Department of
Traveling on moon for a list of trips available this summer.
Trip-ID Destination Length(days) Cost(RMB)
1001 Mars 2 155
1002 Mars 3 170
1003 Jupiter 4 180
1004 Jupiter 5 220
1005 Pluto 1 230
1006 Pluto 2 250
1007 Pluto 3 270
1008 Pluto 4 380
Then he tells his little sister about this and asks for her opinion. But
to
his surprise, she wants to travel as muuuuuuch as poooooooooossible
since
this summer she's gonna have a three-month holiday, and has already done
all
the tasks her professor had assigned to her! Poor Bernie doesn't have
a lot
of pocket money and cannot afford all the trips available in the list.
So,
he asks Rosie which ones she likes best. And this is her reply:
From the first trip in the list, one by one sequentially,
Trip-ID 1001 1002 1003 1004 1005 1006 1007 1008
Preference 30% 70% 75% 65% 110% 100% 90% 120%
Eh.., for the naughty Rosie, the preference above maybe somehow seems
unreasonable. Don't care, you just take it. In order to make full use
of
his money, he needs to find out the trips that satisfy her most. But
poor
Bernie is really busy these days. So he asks you, the best friend of
him,
to help him. Of cause you will receive a big bonus after they finishes
the
memorable trips with the help of your excellent job.
Input
The very first line of the input represent the number of test cases it
has.
And there are three parts for each test case.
The first part contains only one line, there is an integer T (0 < T <=
5000),
follow by a string of "RMB", represent the total pocket money Bernie
has. The
second part represents the trips available this summer. The first line
of this
part contains an integer N (0 < N <= 9), which represents the number
of
destinations available. The rest of the second part contains N blocks,
which
specify the trips available for each destination. The first line of
the block
contains an integer K (0 < K <= 10), which represents the number of
different
trips to this destination. The next K lines of the block, of cause,
specify
the details of each trip. And each line has an integer D (0 < D <= 10),
represents the length of the trip, followed by a string of "days", and
an
integer C (0 < C <= 300), which represents the cost of that trip,
followed by
a string of "RMB".
Finally, here comes the second part of each test case. There are
several
lines in this part, each contains an integer P (0 < P <= 120),
represents
the preference of Rosie for a certain trip. The preferences are listed
one
by one according to the trips listed above in the second part of each
case
sequentially, discard the notation "%" and treat it as an integer.
Output
Your job is to select some trips, so that Bernie could afford it and
also the
sum of the preferences is the biggest. For each test case, just output
two
integers S and H (separated by a single space) in a single line, which
represent how much money he should spend according to your plan, and
how
much 'preference' he could get.
Note: you can assume that the holiday is long enough so that they
could
finish all the trips available. Never mind to make out a plan of
traveling
to a certain destination several times because she likes it! But
remember
that after they finish a certain trip, the preference of that trip
becomes
0 immediately, since make the same traveling is extremely boring.
Sample Input
2
150 RMB
2
Neptune 1
1 days 100 RMB
Earth 1
1 days 60 RMB
90
80
1153 RMB
3
Mars 2
2 days 155 RMB
3 days 170 RMB
Jupiter 2
4 days 180 RMB
5 days 220 RMB
Pluto 4
1 days 230 RMB
2 days 250 RMB
3 days 270 RMB
4 days 380 RMB
30
70
75
65
110
100
90
120
Sample Output
100 90
1100 445
Note: for the second case, one of the best selections is traveling to
Mars for 3
days, and Jupiter for 4 days, and Pluto for 1 day, 2 days, and 3 days.
Author: Bernie.H
------------------------------------------------------------------------
--------
Submit Back Status
------------------------------------------------------------------------
--------
Zhejiang University Online Judge V1.0
--
菩提本无树，明镜亦非台
本来无一物，何处惹尘埃
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店