Assume that a climber with a sufficient amount of supplies would need N days to reach the top of the mountain. The mountain may be too high, so that a single climber cannot carry all the necessary supplies. Therefore a GROUP of climbers starts at the same place and at the same time. A climber who descends prematurely before reaching the top gives his unneeded supplies to other climbers. No supplies may be stored for pick up later on and no climbers rest during the expedition.
The PROBLEM is to plan a schedule for the climbing club. At least one climber must reach the top of the mountain and all climbers of the selected group return to the starting point.
PROBLEM STATEMENT
Implement a program which does the following:
1. Read from the keyboard the integer number N of days needed to arrive at the top, the number P of climbers in the club, and (for all i from 1 to P) the numbers S(i) and C(i). You may assume that the inputs are integers. Reject inputs that make no sense.
2. Try to find a schedule for climbing the mountain. Determine a possible group a(1), ..., a(k) of climbers who should participate in the party and (for all j from 1 to k) the number M(j) of supplies which climber a(j) carries at the start. Note that there may not exist a schedule for all combinations of N and the S(i) and C(i).
3. Output the following information on the screen:
a) the number k of climbers actually participating in the party,
b) the total amount of supplies needed,
c) the climber numbers a(1), .., a(k),
d) for all a(j), j between 1 and k, the
initial amount M(j) of supplies to carry for climber a(j),
e) the day D(j) when climber a(j) starts descending.
4. A schedule is OPTIMAL if
a) the number of participating climbers is minimal and
b) among all groups satisfying condition a) the total of consumed
supplies is minimal.
Try to find a nearly optimal schedule.
TECHNICAL CONSTRAINTS
Constraint-1: Put your solution program into an ASCII text file named
"CLIMB.xxx". Extension .xxx is:
- .BAS for BASIC programs, .C for C programs,
- .LCN for LOGO programs, .PAS for PASCAL programs.
Constraint-2: Programs must reject inputs where N is less than 1 or
greater than 100. P must be not less than 1 and not
greater than 20.
SAMPLE RUNS
(Run #1)
Days to arrive to top: 4
Number of club members: 5
Maximal supply for climber 1 : 7
Daily consumption for climber 1 : 1
Maximal supply for climber 2 : 8
Daily consumption for climber 2 : 2
Maximal supply for climber 3 : 12
Daily consumption for climber 3 : 2
Maximal supply for climber 4 : 15
Daily consumption for climber 4 : 3
Maximal supply for climber 5 : 7
Daily consumption for climber 5 : 1
2 climbers needed, total amount of supplies is 10.
Climber(s) 1, 5 will go.
Climber 1 carries 7 and descends after 4 day(s)
Climber 5 carries 3 and descends after 1 day(s)
Plan another party (Y/N) Y
(Run #2)
Days to arrive to top: 2
Number of club members: 1
Maximal supply for climber 1 : 3
Daily consumption for climber 1 : 1
Climbing party impossible.
Plan another party (Y/N) N
Good bye
TRIAL DATA WITH SOLUTIONS.
(Run #3)
INPUT:
mountain height = 4
club size = 5
climber supply consumption
1 5 1
2 5 1
3 5 1
4 5 1
5 5 1
OUTPUT:
4 climbers needed, total amount of supplies is 20
Climber(s) 1, 2, 3, 4 will go
Climber 1 carries 5 and descends after 4 day(s)
Climber 2 carries 5 and descends after 3 day(s)
Climber 3 carries 5 and descends after 2 day(s)
Climber 4 carries 5 and descends after 1 day(s)
(Run #4)
INPUT:
mountain height = 4
club size = 4
climber supply consumption
1 8 2
2 5 1
3 15 3
4 9 2
OUTPUT:
Climbing party impossible!
WARNING: Successful execution of your program with these examples
does not necessarily guarantee that your program is correct !!!
POINTS
User dialogue as illustrated in Sample Runs................. 10 points
Find a solution for the special case where all C(i)=1 and
all S(i) are equal ...................................... 20 points
Find a solution for general case ........................... 20 points
Find a nearly optimal solution for general case ............ 30 points
Detect unsolvable situations ............................... 10 points
Technical constraints obeyed ............................... 10 points
----------------------------------------------------------------------
Total 100 points
TIME LIMIT:
Five hours is the time allowed to write the program and test it out with
the data found in the SAMPLE RUNS.TEST DATA After the five hour time limit, or when you are done with your program, your local contest coordinator will ask you to demonstrate your program with the input from the:
a) Sample Runs b) Trial Data with Solutions and c) Test Data.WHAT TO SUBMIT
Please fill out the Contestant Information Sheet and submit
On Paper:
1) A printed listing of your program.
2) A printed copy of your solutions to the input found in the
Sample Runs.
3) A printed copy of your solutions to the input found in the
Trial Data with Solutions.
4) A printed copy of your solutions to the input found in the
TEST DATA.
On Disk:
5) An ASCII copy on your program CLIMB.XXX.
6) An ASCII copy of your solutions in 2),3), and 4). *Optional*
On the disk please write:
USACO Competition Round
Name
Language
MAC or IBM
Mail the material from 1-6 so we receive it by Friday,March 26, 1993.
The results will be announce by Friday, April 9, 1993.
Mail to:
Dr. Donald Piele
USACO
UW-Parkside
900 Wood Rd.
Kenosha, WI 53141-2000
TEST DATA
(Run #5)
INPUT:
mountain height = 10
club size = 20
climber supply consumption
1 14 2
2 13 1
3 6 4
4 12 1
5 8 2
6 11 1
7 10 1
8 5 1
9 9 1
10 8 1
11 7 1
12 15 3
13 6 1
14 11 2
15 14 2
16 9 2
17 15 2
18 16 2
19 17 2
20 18 2
(Run #6)
INPUT:
mountain height = 4
club size = 4
climber supply consumption
1 5 1
2 9 2
3 15 3
4 8 2
(Run #7)
INPUT:
mountain height = 10
club size = 19
climber supply consumption
1 11 1
2 11 1
3 11 1
4 8 2
5 11 1
6 11 1
7 5 1
8 11 1
9 11 1
10 11 1
11 15 3
12 11 1
13 11 1
14 11 1
15 9 2
16 11 1
17 11 1
18 11 1
19 11 1
(Run #8)
INPUT:
mountain height = 4
club size = 5
climber supply consumption
1 6 1
2 6 1
3 6 1
4 6 1
5 16 2
(Run #9)
INPUT:
mountain height = 4
club size = 15
climber supply consumption
1 5 1
2 5 1
3 5 1
4 5 1
5 5 1
6 5 1
7 5 1
8 5 1
9 5 1
10 5 1
11 5 1
12 5 1
13 5 1
14 5 1
15 5 1
(Run #10)
INPUT:
mountain height = 2
club size = 1
climber supply consumption
1 3 1