Problem Set 2002 ACM High School Programming Contest DO NOT LOOK AT THE PROBLEMS UNTIL YOU ARE TOLD TO DO SO BY THE CHIEF JUDGE!! REMEMBER: All input comes from the keyboard, and all output goes to the screen. In all problems, you should output ONLY what is specified. Do not output debugging information, and do not prompt for input. You should turn in an executable file called "programN", where N is the problem number. Do NOT turn in source code. Problem 1 --- Fiddling With Small Change ---------------------------------------- Foreign visitors to the Games will wind up with pockets full of U.S. coins after spending a few weeks in Utah. To make it easy for visitors to convert their coins into paper money, the organizers of the Games are planning to install Automatic Change Machines (ACMs) all around Salt Lake City. You have been hired to write part of the software for the ACMs. Your task is to write a program that determines the total value of a group of U.S. coins. Write a program that reads one line of input from the keyboard: this line will contain EXACTLY FOUR number-letter pairs. An example input to your program is: 5 q 0 d 2 n 7 p This line describes a group of U.S. coins: in this case, 5 quarters, 0 dimes, 2 nickels, and 7 pennies. Each number in the input line will be an integer between 0 and 100, inclusive. Each letter will be one of the following: 'q' for quarters, 'd' for dimes, 'n' for nickels, and 'p' for pennies. The letters may come in ANY ORDER. For instance, there is no guarantee that 'q' will come before 'd' in the input line. REPEATS ARE POSSIBLE, but exactly 4 number-letter pairs (no more, no less) will always be input. 1 d 2 d 3 d 4 d is valid, but 1 d 2 d 3 d is not valid because there are only 3 pairs. The numbers and letters in the input line are separated from each other by one or more space characters. The input line will end with a newline character ('\n'). Your program must compute the total value of the coins in dollars and cents, and then output a single line in the following form: D dollars and C cents where D is the number of whole dollars and C is the number of remaining cents. Print the line exactly as described, even if D or C (or both) is zero. The value of C must be at least 0 and not more than 99. Your program must print the line exactly as described, then print a newline character (`\n') and exit. YOUR PROGRAM MUST NOT PRINT ANY OTHER OUTPUT. SEE EXAMPLES ON NEXT PAGE... Example 1: Input: 5 q 0 d 2 n 7 p Output: 1 dollars and 42 cents Example 2: Input: 1 d 7 q 32 p 5 d Output: 2 dollars and 67 cents Example 3: Input: 0 p 0 q 0 d 0 d Output: 0 dollars and 0 cents Example 4: Input: 100 p 2 q 100 n 5 d Output: 7 dollars and 0 cents Example 5: Input: 80 q 0 d 2 p 1 n Output: 20 dollars and 7 cents Problem 2 --- Calculating Times for Teams ----------------------------------------- The IOC has decided to add a team slalom competition to the list of alpine skiing events. The times of the four athletes on each team will be added, and the team with the lowest total time will be the winner. To assure the accuracy of each calculation of total times, the IOC asked you to write an Automated Computation Module (ACM) to add to their scoring software system. This will input the race time of each competitor, calculate the totals for all the teams, and output the first, second, and third place teams. There will be at least 3, but no more than 26 teams. The times will be provided to you in a somewhat random order. Input to your ACM will be in the form of individual lines with the following format: A letter indicating a team (a..z), a space, and a time represented as minutes:seconds (Example: a 12:34.037) This represents the time for one member of team a. The above input may repeat from 12 to 104 times. There will be exactly 4 times for each team. At the end of the input will be a line with a single character, an asterisk (*). Your program should output the 1st, 2nd, and 3rd place winners in the following format: Gold: Team X minutes:seconds Silver: Team Y minutes:seconds Bronze: Team Z minutes:seconds You should correctly report the team that wins the race, as well as printing their total time in minutes and seconds. You are guaranteed that there will be three teams that complete the race, and that the winners will be clear (no ties). SEE EXAMPLES ON NEXT PAGE... Example 1: Input: a 13:52.001 a 19:29.002 a 10:34.003 a 20:50.004 f 10:35.005 f 19:35.006 f 10:17.007 f 21:45.008 d 11:13.009 d 20:27.010 d 11:18.011 d 20:57.012 e 11:01.013 e 21:28.014 e 10:21.015 e 19:25.014 b 14:01.013 b 20:57.012 b 11:21.011 b 20:35.010 c 11:42.009 c 21:19.008 c 11:44.007 c 23:34.006 * Output: Gold: Team f 62:12.026 Silver: Team e 62:15.056 Bronze: Team d 63:55.042 Example 2: Input: s 22:18.010 w 26:43.010 w 22:12.010 s 25:36.010 v 26:21.010 v 30:31.010 s 26:02.010 v 21:49.010 w 25:35.010 w 29:23.010 v 27:22.010 s 30:24.010 * Output: Gold: Team w 103:53.040 Silver: Team s 104:20.040 Bronze: Team v 106:3.040 Problem 3 --- Scoring a Curling Match ------------------------------------- Curling is a highly competitive, strategic sport. You have been asked by the American Curling Medalists (ACM), an association of former winners of the Curling World Championships, to help the people who will do the officiating at the Olympics. Your task is to write a program that will accurately and definitively determine the score for one game of curling. (Your program will be used over the course of the games, so accuracy is very important.) In the sport of curling, two teams throw eight heavy granite stones towards a single target at the other end of an ice sheet. The stones glide down the ice and either come to rest near the target, or they knock an opponent's stone out of play. The center point of the target is called the tee. Scoring is done as follows: Only stones six feet or closer to the tee are scored. If neither team has a stone within six feet, no score is awarded. Otherwise: One team may have at least one stone closer to the tee than the other team. This is the scoring team, the other team does not score. The scoring team gets one point for every stone that is closer to the tee than any of the opponent's stones. It is possible that stones may be the same distance from the tee. Stones of opposing teams are considered tied if they are within 0.001 feet of the same distance to the tee. No point are awarded for these stones. Your task is to write a program for ACM to determine the score for one game of curling. Your program will be provided with measurements (in feet) provided by a super-accurate laser scanner. The input will consist of the following items, each on a separate line: + Coordinates of the tee, specified as floating point numbers (x, y), + The number of stones still in play for the red team (0..8), + One coordinate pair (x, y) for each red team stone, + The number of stones still in play for the blue team (0..8), + One coordinate pair (x, y) for each blue team stone. Your output should be only one of the following three messages: Red scored N points. Blue scored N points. The game ended with no score. The N above should accurately reflect the resulting score for the scoring team. If no stones are within 6 feet of the tee, or if the closest stone for each team is the same distance from the tee, your program should output the third message. You should print a return character after the message. If your program outputs more than one message, or if your program outputs any other information (including prompts or debugging text), it will be judged incorrect. SEE EXAMPLES ON NEXT PAGE... Example 1: Input: -10 0 0 2 -2 -6 -10 0 Output: Blue scored 1 points. Example 2: Input: 3 3 2 0 7 3 15 1 6 -1 Output: The game ended with no score. Example 3: Input: 5.0 7.0 3 4.0 7.0 1.0 10.0 0.0 19.0 1 5.0 12.5 Output: Red Scored 2 points. Problem 4 --- Hidden Countries ------------------------------ Security around the Games is extremely tight --- not just physical security, but electronic security as well. To help spot potential threats, the organizers of the Games have asked you to write a program that looks for hidden country names in electronic mail --- an Automated Checker of Messages (ACM). For example, consider this sentence: Can a ``dandy'' coach help an amateur reach the Games? If you look carefully, you will find two hidden country names as shown below: CAN A ``DAndy'' coach helP AN AMAteur reach the Games? The first six letters of the sentence spell CANADA. Later, the letters spell PANAMA. A country name ``appears'' in a message when the LETTERS of the country name appear IN ORDER and CONSECUTIVELY as a substring of the LETTERS of the message. All non-letter characters in the name and message are disregarded when searching for a match. Letter case is also ignored. Your program must find names such as those hidden in the above example. Write a program that reads the following input: + A number, indicating how many country names will be input to your program. This number will be between 1 and 10, inclusive. + The names of the countries to be searched for. Each country name will contain between 1 and 30 characters, inclusive. A country name may contain letters (upper- and lower-case), numbers, spaces, and punctuation, but will always contain at least one letter. + A line of text, which is the message to be scanned for hidden names. This line will contain between 1 and 100 characters, inclusive. It may contain letters, numbers, spaces, and punctuation, but will always contain at least one letter. Each of these items will be given on a separate input line. Your program must output the country names that ''appear'' in the message, as defined above. Your program must output the names in the left-to-right order in which they appear in the message. Also: + Each name must be output as it was entered in the list of country names, with proper capitalization, punctuation, and spaces. DO NOT output the name as it appears in the message. + A single country name may appear more than once in a message. If this happens, the name should be output once for each time it appears. + Two or more names may overlap in the message, but you may assume that no two names will start at the same point in the message. In other words, you may assume that no country name is a letterwise-prefix of another. If one or more country names are found, your program must output the names as described above, with each name on a separate output line. If no names are found, your program must output the word "NONE", followed by a newline. Your program must exit after printing its output. SEE EXAMPLES ON NEXT PAGE... Example 1: Input: 3 America Canada Panama Can a ``dandy'' coach help an amateur reach the Games? Output: Canada Panama Example 2: Input: 3 Spain China Sweden Each in a lane! An inch in a tight race! Output: China China Example 3: Input: 3 China S. Korea United States ``Ask... or... each in a unit,'' Ed states. Output: S. Korea China United States Example 4: Input: 3 Yugoslavia Slovakia Turkey A turkey wrecked by Yugo in Slavia... I mean, in Slovakia! Output: Turkey Slovakia Example 5: Input: 4 Finland India Tibet Tonga Patti bet on Gabbi Fin (#10) landing a medal. Output: Tibet Tonga Finland Example 6: Input: 3 Togo Latvia Kenya Can Ada and Ken (yawn!) go to your flat, Vi, at Bracken Yard? Output: Kenya Latvia Kenya Example 7: Input: 1 Chile Has Chi-Chi tried the Chili? It takes away the chill, easily! Output: NONE Problem 5 - Blue Fences Everywhere! ----------------------------------- The one thing that most characterizes an outdoor Olympic venue is fences. Miles and miles of blue mesh fences. There are fences to keep unauthorized people off the field of play. Fences to keep members of the press in specific areas where they are allowed to interview athletes after events. Fences to mark paths where spectators must walk to get to their viewing spots. Bottom line is that each venue is A Confusing Maze (ACM) of fences. Most events have short breaks when spectators could visit a concession stand. The first problem at such times is to find that concession. The second is to decide whether or not you have time to get there and back before the competition resumes. With that in mind, you decide to write a program on your pocket computer that will input a map of an Olympic venue and output the length of the shortest path from you to the concession. To simplify your task, you decide that your program will input the venue map as a 2-dimensional array of points, each of which represents a point on the ground. Also, it will only calculate the sum of horizontal (x) and vertical (y) components of the shortest path, without considering diagonals. You may assume for this program that no venue is more than 25 points wide and 25 points high. Input Format: x_size_of_venue y_size_of_venue Row 1 Row 2 . . . Row N The input array will have the following values: '.' = open area 'Y' = your location 'C' = concession location 'x' = fence The coordinate of the upper left point in the array is 0,0. Your program should output only one line. It should output only the integer distance of the shortest path from you to the concession , OR if there is no way to get there without crossing a fence, it should output the following: Can't get there Remember, you may not move diagonally! You do NOT need to print out the path. SEE EXAMPLES ON NEXT PAGE... Example #1: Input: 22 3 xxxxxxxxxxxxxxxxxxxxxxx x.Y.................C.x xxxxxxxxxxxxxxxxxxxxxxx Output: 18 Example #2: Input: 24 7 xxxxxxxxxxxxxxxxxxxxxxxx x.......x.x..x........Cx x.xxxxxxx.x.xxxxxx.xx.xx x.........x.Y......xx.xx x...xxxxxxx..xx..xxxxxxx x............x.........x xxxxxxxxxxxxxxxxxxxxxxxx Output: 12 Example #3: Input: 17 6 xxxxxxxxxxxxxxxxx x.Y.x..C.xx.xxxxx x...x.......xxxxx x...xxxxxxxxx...x x...............x xxxxxxxxxxxxxxxxx Output: Can't get there