USACO Qualifying Round February 7-14, 1997 Qualifying Round February 7-14, 1997 (Problems Enclosed) A round mailed to school coordinators for students who wish to qualify for the National Championship. Not required by those who have demonstrated their ability in the two previous Internet championships. National Championship April 9, 1997 (At local school) This competition will determine the U. S. National Champion. It will also be used to help the USACO committee select the finalists for the USACO finals. USACO Finals June 9-17, 1997 (At University of Wisconsin-Parkside) USACO Olympiad Training Camp and Final Round, Kenosha,Wisconsin. Approximately 16 participants are invited to attend by the USACO committee. Four participants will be chosen to represent USA at 1997 IOI in South Africa. Getting Online This year you can get the problems via e-mail instead of on paper! To receive these problems, subscribe to our problem-of-the-week list maintained at: hs-computing@delos.com To subscribe, send a message to:majordomo@delos.com In the body of the message write: subscribe hs-computing In addition to receiving the qualifying problems on February 7, you will also receive the regular challenge-of-the-week (COW). The best way to prepare for the USACO is to work on these COWs. Rules Enclosed you will find the four problems for the 1997 USACO Qualifying Round. To qualify for the USACO, you must correctly solve at least two of the problems. If you entered the Fall or Winter Championships held on the Internet, you need to score 140 points to be qualified. If you are a student, your mission is to solve as many of these problems as possible during the period from February 7 to February 14. If you are a local teacher or coordinator, you should distribute these problems to all interested students on February 7. Here are the guidelines: Students may begin working on the problems on February 7. Students may work on them at any location (even at home), but they should work on them individually. Students should not use any previously written code or other aids not built into the operating system or the programming language. A language manual, written or on-line is allowed. On or before February 14, students must demonstrate their solutions to a teacher or coordinator who will compare the output of the test cases with the answers provided. If the coordinator is not certain how to enter the test cases, have the student do it. It is OK to have the student prepare the input files for testing his or her program. That way, there can be no excuse for not being able to read the test files. To be judged correct, all programs must give the correct answer to each test case within one minute. Unless the program is correct for all test cases, it should not be judged as correct. Some programs will fail because they are too slow, even if they give the correct answers. All judgments in the Qualifying Round are left to the local teacher or coordinator in consultation with the student. However, a copy of all source code created by each student who qualifies and enters the National Championship Round must be submitted on disk along with his or her entry. We may examine these programs if it becomes necessary in our selection of the finalists. If you have more than one student entering, you may submit as many as will fit in folders on one disk. Please label the disk with the names of the students. Reaching any of the following three levels qualifies a student for the National Championship. Bronze Two problems solved. Silver Three problems solved. Gold Four problems solved. The purpose of this round is to let students discover whether they have the skills necessary to be successful in the competition round. If they do not follow the rules, they will only be fooling themselves, since the next round is more difficult and will be conducted in a controlled environment. What languages may be used? The official languages that will be used at IOI '97 in South Africa are Borland's Turbo Pascal, and Turbo C/C++; . Thus, the languages that will be used at the USACO training camp at the University of Wisconsin-Parkside will be Pascal or C/C++. What is the age limit? In accordance with IOI rules, all students must be in secondary school (grades 9-12) and be 19 years of age or younger on July 1, 1997. Graduating seniors are considered to be in secondary school. Only residents of the United States are eligible to compete in the USACO. 1997 QUALIFYING PROBLEMS Q1. PRIME PALINDROMES The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes between two numbers a and b. You may assume that a and b are between 1 and 32,000. Test your program with a,b = 1, 1000 and a,b =1000, 32000 Test Case 1 a,b = 1,1000 PRIME PALINDROMES BETWEEN 1 AND 1000 2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929 Test Case 2 a,b = 10000, 32000 PRIME PALINDROMES BETWEEN 10000 AND 32000 10301 10501 10601 11311 11411 12421 12721 12821 13331 13831 13931 14341 14741 15451 15551 16061 16361 16561 16661 17471 17971 18181 18481 19391 19891 19991 30103 30203 30403 30703 30803 31013 31513 Q2. MAKING CHANGE Write a program than will compute how many ways to make change for a given amount of money. The money system consists of the coins A, B, C, and D where 5 A = 1 B 2 B = 1 C 2 C = 1 D All money is expressed in terms of A. Thus, 23 in this system means 23 A. Your job is to write a program that will compute all the ways to make change for any amount of A. Print your results as shown in the sample run. Test your program with 23 and 36. Test Case 1 Enter an amount in A? 23 Number A B C D 1 23 0 0 0 2 18 1 0 0 3 13 2 0 0 4 8 3 0 0 5 3 4 0 0 6 13 0 1 0 7 8 1 1 0 8 3 2 1 0 9 3 0 2 0 10 3 0 0 1 There are 10 ways to make change for 23 A using A, B, C and D. Test Case 2 Enter amount in A: 36 Number A B C D 1 36 0 0 0 2 31 1 0 0 3 26 2 0 0 4 21 3 0 0 5 16 4 0 0 6 11 5 0 0 7 6 6 0 0 8 1 7 0 0 9 26 0 1 0 10 21 1 1 0 11 16 2 1 0 12 11 3 1 0 13 6 4 1 0 14 1 5 1 0 15 16 0 2 0 16 11 1 2 0 17 6 2 2 0 18 1 3 2 0 19 6 0 3 0 20 1 1 3 0 21 16 0 0 1 22 11 1 0 1 23 6 2 0 1 24 1 3 0 1 25 6 0 1 1 26 1 1 1 1 There are 26 ways to make change for 36 A using A,B,C, and D. Q3 FRIDAY THE 13TH Is Friday the 13th really an unusual event? That is, does the 13th of the month land on a Friday less often than on any other day of the week? To answer this question, write a program that will compute the frequency that the 13th of each month lands on Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday over a given period of N years. The time period to test will be from January 1, 1900 to December 31, 1900+N-1 for any number of years N. There are few facts you need to know before you can solve this problem: 1. January 1, 1900 was on a Monday. 2. Thirty days has September, April, June, and November, all the rest have 31 except for February which has 28 except in leap years when it has 29. 3. Every year evenly divisible by 4 is a leap year (1992 = 4*498 so 1992 will be a leap year, but the year 1990 is not a leap year) 4. Rule 3 does not hold for century years. Century years divisible by 400 are leap years, all other are not. Thus the century years 1700, 1800, 1900 and 2100 are not leap years, but 2000 is a leap year. Test your program for N=20 and N=400. Note: To make it fair for everyone, you may not use any built-in date functions in your computer language. Test Case 1 Enter the number of years N? 20 FROM JAN 1, 1900 TO DECEMBER 31, 1919 THE 13TH OF THE MONTH LANDS ON DAY # OF TIMES SUNDAY 33 MONDAY 34 TUESDAY 33 WEDNESDAY 35 THURSDAY 35 FRIDAY 34 SATURDAY 36 Test Case 2 From Jan 1, 1900 to Dec 31, 2299 the 13th of the month lands on DAY # 0F TIMES SUNDAY 687 MONDAY 685 TUESDAY 685 WEDNESDAY 687 THURSDAY 684 FRIDAY 688 SATURDAY 684 (If a solution increments day by day instead of month by month it will take 30 times longer to examine 400 years and might run too long.) Q4. N SAILORS AND A MONKEY N sailors and a monkey are on an island. One evening, the sailors round up all the coconuts on the island and put them in one large bin. They decide to wait until morning to divide up the coconuts, so they go to bed. During the night, the first sailor gets up, separates the coconuts into N equal piles with one left over, which he gives to the monkey. He decides to hide one of the piles for himself, and he puts the remaining N-1 piles back in the bin. He then returns to his hammock, content that at least he got his share. But he is not alone. During the night, each sailor gets up and does exactly the same thing: gives one coconut to the monkey and takes 1/Nth of the coconuts left for himself. In the morning the N sailors come together again and divide the remaining coconuts in the bin into N equal piles with one coconut left over for the monkey. What is the least number of coconuts that they could have begun with for all this to happen? Print out the number of coconuts that each sailor collected, the number that went to the monkey, and the total number of coconuts the sailors gathered together in the first place. Test your program for N=5 and N=6. Test Case 1 Number of sailors = 5 Sailor Coconuts 1 4147 2 3522 3 3022 4 2622 5 2302 Monkey 6 ========================= Total 15621 Test Case 2 Number of sailors = 6 Sailor Coconuts 1 62279 2 54503 3 48023 4 42623 5 38123 6 34373 Monkey 7 ========================= Total 279931 Qualifying Round Report Form (Please Print) Name of Student ___________________________________ Name of Coordinator _______________________________ Name of School ____________________________________ Address of School _________________________________ City, State, Zip of School ___________________,________,_________ e-mail address of Coordinator_____________________________ e-mail address of Student ______________________________ WWW (URL) of school ________________________________________ Please enter X for all test cases that ran correctly. Q1. PRIME PALINDROMES Test Case: 1 __ 2 __ Q2. MAKING CHANGE Test Case: 1 __ 2__ Q3. FRIDAY THE 13TH Test Case: 1 __ 2 __ Q4. N SAILORS AND A MONKEY Test Case: 1 __ 2 __ Number of problems solved (all test cases correct) = ____ Signed _____________________, Date _________________ LocalCoordinator **Deadline for this report to be at USACO is February 24, 1997.** Internet Competitions Entered: Fall Championship Score : ____________ Winter Championship Score : ____________ Disk Each student who qualifies (solves two or more problems) and wants to enter the National Championship round, must submit their disk of qualifying round programs to the local coordinator who must return them to the USACO along with the above qualifying round report. Place the work of each student in a separate folder. (More than one student's work may be submitted on a disk, if this is more convenient.) Please indicate MAC or IBM format on the disk label. Also print the names of the students on the disk label. Mail to: Don Piele Director USACO University of Wisconsin-Parkside 900 Wood Rd Kenosha, WI 54141-2000 If you are short of time, you can send in the qualifying round report via fax or e-mail and send the disk via regular mail (which can arrive after Feb. 24, 1997) However, I would rather have a hard copy if at all possible. Fax to:414-595-2056 or e-mail to: piele@cs.uwp.edu **Deadline for this report to arrive at USACO is February 24, 1997.** 1997 USACO National Championship Instructions to the LOCAL COORDINATOR The Competition Round will be held at your local site on Wednesday, April 9, 1997. This is a five hour event that must be monitored by you. The instructions and problems will be mailed to you on March 27. Please call if your materials have not arrived by the April 7. Unlike the previous Internet competitions, no questions will be answered by the committee during the contest. If you have any questions please call: Don Piele, 414-634-0868, or e-mail, piele@cs.uwp.edu or Rob Kolstad at kolstad@BSDI.COM. Good Luck! Don Piele USACO Director