没有合适的资源?快使用搜索试试~ 我知道了~
2006 ACM决赛题目
需积分: 6 55 下载量 2 浏览量
2007-04-04
14:13:12
上传
评论
收藏 279KB PDF 举报
温馨提示
试读
20页
大家可以挑战一下(^_^)
资源详情
资源评论
资源推荐
Problem A
Low Cost Air Travel
Input File: air.in
Air fares are crazy! The cost of a ticket is determined by numerous factors, and is usually not directly related to the
distance traveled. Many travelers try to be creative, sometimes using only parts of tickets with stops in various cities
to achieve lower-cost travel. However, the airlines are aware of this behavior, and usually require that the travel
covered by a ticket be completed in order and without intervening travel. For example, if you have a ticket for travel
from City-1 to City-2 then to City-3, you are not allowed to use only the portion of the ticket for travel from City-2
to City-3. You must always start at the first city on the ticket. In addition, you are not allowed to travel from City-1
to City-2, fly elsewhere and return, and then continue your journey from City-2 to City-3.
Let’s consider an example. Suppose you are allowed to purchase three types of tickets:
Ticket #1: City-1 to City-3 to City-4 $225.00
Ticket #2: City-1 to City-2 $200.00
Ticket #3: City-2 to City-3 $50.00
Suppose you wanted to travel from City-1 to City-3. There are two ways to get there using only the available ticket
choices:
Purchase Ticket #1 for $225.00 and use only the first leg of the ticket.
Purchase Ticket #2 for $200.00 and Ticket #3 for $50.
The first choice is the cheapest.
Given a set of airline ticket offers, and one or more trip itineraries, you must determine how to purchase tickets in
order to minimize the cost of travel. Each trip will be possible.
Input
Input consists of multiple test cases, each describing a set of ticket offers and a set of trip itineraries.
Each case begins with a line containing NT, the number of ticket offers, followed by NT offer descriptions, one to a
line. Each description consists of a positive integer specifying the price of the ticket, the number of cities in the
ticket’s route, and then that many cities. Each city in a case has an arbitrary, but unique, integer identification
number. Note that several tickets may be purchased from the same offer.
The next line contains NI, the number of trips that are to have their cost minimized. NI lines follow, giving the
itineraries for each trip. Each line consists of the number of cities in the itinerary (including the starting city),
followed by that many city identification numbers, given in the order they are to be visited.
There will be no more than 20 ticket offers or 20 itineraries in a test case. Each offer and itinerary lists from 2 to 10
cities. No ticket price exceeds $10,000. Adjacent cities in a route or itinerary will be distinct. Tickets and trips are
numbered sequentially in each set, starting with 1.
The last case is followed by a line containing a zero.
Output
For each trip, output two lines containing the case number, the trip number, the minimum cost of the trip, and the
numbers of the tickets used for the trip, in the order they will be used. Follow the output format shown below. The
output will always be unique.
Sample Input Output for the Sample Input
3
225 3 1 3 4
200 2 1 2
50 2 2 3
1
2 1 3
3
100 2 2 4
100 3 1 4 3
200 3 1 2 3
2
3 1 4 3
3 1 2 4
0
Case 1, Trip 1: Cost = 225
Tickets used: 1
Case 2, Trip 1: Cost = 100
Tickets used: 2
Case 2, Trip 2: Cost = 300
Tickets used: 3 1
Problem B
Remember the A La Mode!
Input File: alamode.in
Hugh Samston owns the “You Want It, Hugh Got It” catering service, which has been asked to supply desserts for
the participants in this year’s ICPC World Finals. Hugh will provide pie slices topped with ice cream at the various
social functions scheduled throughout the week. As with any other dedicated entrepreneur, Hugh would like to offer
the best service possible, so he has ordered a wide variety of pies and ice creams to satisfy even the most eclectic
tastes.
Hugh plans to serve each pie slice with a single scoop of ice cream, leaving the exact combination up to the whim of
the customer. But of course, as with any other dedicated entrepreneur, Hugh would also like to make as much profit
as possible from this enterprise. He knows ahead of time how much profit he can make on each combination of pie
slice and ice cream scoop, as well as which combinations of pie and ice cream should never be put together
(example: Peppermint Banana Chunk ice cream on Key Lime pie).
Given this information, along with the number of slices and scoops he has of each variety of pie and ice cream,
Hugh figures he can determine both the minimum and maximum profits he can expect. Since he hopes to be the
caterer at subsequent World Finals, he would like a general program to solve this and future problems.
Input
Input will consist of multiple problem instances. Each problem instance will start with a line containing two integers
P (P ≤ 50) and I (I ≤ 50), indicating the number of types of pie and ice cream, respectively. The next line will
contain P integers indicating the number of slices available for each of the pie types. The line after that will contain I
integers indicating the number of scoops available for each of the ice cream types. The total number of pie slices
will always equal the total number of ice cream scoops available, and it is assumed that all pie slices and ice cream
scoops will be used.
Each problem instance will end with P lines each containing I floating point numbers indicating the profit for each
pie/ice cream combination: the first value indicates the profit if a slice of pie type 0 is topped with a scoop of ice
cream type 0; the next value indicates the profit if a slice of pie type 0 is topped with a scoop of ice cream type 1,
and so on. A profit value of -1 indicates that no combinations of that pie type and ice cream type should ever be
sold. All other integers (number of slices for each type of pie and number of scoops for each type of ice cream) will
be less than or equal to 100 and the profit on each one of the pie/ice cream combinations (other than -1) will be
larger than 0 and less than or equal to 10, with at most two digits after the decimal point.
The last problem instance is followed by a line containing two zeroes.
Output
For each problem instance, output the problem number (starting at 1) followed by the minimum and maximum
profits, using the format shown in the sample output. Display all numbers with two fractional digits. All problem
instances are guaranteed to have at least one solution using all of the pie slices and ice cream scoops.
Sample Input Output for the Sample Input
2 3
40 50
27 30 33
1.11 1.27 0.70
-1 2 0.34
4 4
10 10 10 10
10 10 10 10
1.01 -1 -1 -1
-1 1.01 -1 -1
-1 -1 1.01 -1
-1 -1 -1 1.01
0 0
Problem 1: 91.70 to 105.87
Problem 2: 40.40 to 40.40
剩余19页未读,继续阅读
imam_2000
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0