Climbing A Mountain A mountain climbers club has P members, numbered from 1 to P. Every member climbs at the same speed and there is no difference in speed between climbing up and down. Climber number i consumes C(i) units of SUPPLIES per day and can carry at most S(i) such units. All C(i) and S(i) are integer numbers. 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 Contestant Information Sheet Name______________________________ Age___________ Birthday___________ Home Address_____________________________ Grade ___________ City ________________________ State ________ Zip ___________ Home Phone ______________________ School ___________________________ Computer Language _____________ City ______________________________ Disk Format IBM ______ MAC ___ School Phone _________________________ Home Phone ________________________ To The Contestant: A contestant must attend the USACO training camp at the University of Wisconsin-Parkside from June 13 to June 20 to be eligible to earn a spot on the USA Team to the International Olympiad in Informatics in Argentina, October 13-23, 1993. Only those who can attend the International Olympiad will be invited to the USACO training camp. All expenses will be paid for both events. If you are able to attend both the training camp and the Internation Olympiad in Informatics please sign below. Date_____________ Signed __________________________________ To The Local Contest Coordinator: We need your signiture that verifies that the rules were followed and that the program submitted was written within the five hour limit by the contestant named above. Date program was written______________ Start Time:_________ End Time: Location_____________________ Date___________________ Signed ____________________________________