Consortium for Computing at Small Colleges Northeast Region
2001 Undergraduate Programming Contest
Sponsored by
Microsoft Corporation
Middlebury
College, Vermont
Friday, April 20,
2001
Guidelines and notes
1. The contest will begin after the welcoming remarks conclude (some time between 9:00am and 9:30am) and will run continuously until 12:30pm. Breakfast will be served available at about 8:00am, and lunch will be available at about 12:00noon.
2. Each team will consist of up to three undergraduate students currently enrolled at the same academic institution.
3. Each team will be randomly assigned a single Linux workstation in either the Warner 501 lab or the Warner 507 lab. Teams may use C, C++, or Java to write solutions to the problems.
4. The contest will consist of 5 programming problems. The winner is determined based on the number of problems solved, i.e., accepted by the judges. If more than one team correctly solves the same number of problems, placement will be determined by the total time to complete them, i.e., the sum of the net solution time of each solved problem, which is the time of correct submission minus the contest starting time.
5. Teams may use any printed materials during the contest but may not use any electronic devices (e.g., calculators or PDAs) or any materials stored electronically.
6. Teams may print out code using the “lpr <filename>” command. Your source code should include a comment at the beginning indicating your school’s name and laboratory location (room 501 or 507). Your printouts will be delivered to you.
7. Submitted “solutions” will be judged as accepted or rejected. Teams may re-submit “solutions” to the same problem multiple times (within reason) without penalty.
8. A public scoreboard will be maintained. To maintain competition and suspense, however, it will not be updated during the last 45 minutes of the contest.
9. Contestants may not communicate with faculty advisors or other teams during the contest. All questions should be directed to the contest officials. For any disputes, the decision of the judges will be final.
10. In your home directory, you should create subdirectories named “1”, “2”, “3”, “4”, and “5”, and work on each problem in its respective subdirectory.
11. For each problem, you may assume that the input is both legal and properly formatted. Hence, no error checking is required.
- Target
Painting
Suppose we have a target board consisting of one or more concentric circles (see the sample below). We plan to paint the innermost circle blue, the ring immediately around it white, the next outer ring blue, the next outer ring white, and so on. We need to know how much paint to buy. Conveniently, each can of paint is enough to cover π square inches of target board. You will be given the radius of each circle, beginning with the center circle and continuing outwards. Each radius will be a positive integer value, and the last circle’s radius will always be 25. Write a program named target to prompt for this information from the user and to compute the number of cans of blue paint and white paint needed. Format the answer as shown below.
Input: A sequence of one or more positive integers that denote the radii of increasingly larger concentric circles. A radius of 25 also indicates end of input.
Output: Two lines, the first indicating how many cans of blue paint are needed, and the second indicating how many cans of white paint are needed.
Sample runs:
$ target
?
1
?
3
?
6
?
10
?
15
?
20
?
25
378
blue cans
247
white cans
$ target
?
25
625
blue cans
0
white cans
- Counting
1’s base B
Write a program countones that determines the number of 1's
in a base-B representation of a number N, and outputs this number also in base
B. For example, for B=2 and N=17, N
base B is 10001. This number contains
two 1's, which – again in base 2 – is 10.
For B=3 and N=20, N base B is 202, which contains no 1's, thus the
output is 0. Your output should have no
leading zeros unless the number 0 itself is output.
Input: Two
command-line arguments: the base B, and the number N. Assume that 2 £ B £ 10, and N ³ 0.
Output: Two
lines: on the first line, N represented at base B; on the second line, the
number of 1's in this representation, again represented at base B.
Sample runs:
$ countones 2 17
10001
10
$ countones 3 20
202
0
$ countones 4
341
11111
11
- A
Number Game
Write a program named numbergame that determines the optimal sequence of moves for Player 1 in a two-player game. The game starts with a list of 2n numbers, each in the range from 0 to 999, inclusive. Starting with Player 1, each player alternately chooses either the number currently at the beginning or currently at the end of the list and removes it from the list. The game ends when all numbers have been chosen, i.e., the list is empty. Each player’s score consists of the sum of all numbers that that player removed from the list. Besides the list of numbers, your program will also be given a string of n characters, each of which is either B, which denotes “choose from beginning”, or E, which denotes “choose from end.” This string corresponds to the complete sequence of moves that Player 2 has already decided to make, i.e., if the ith character in this string is B, then Player 2 plans to choose the number at the beginning of the list on Player 2’s ith turn. Using those same two characters, your program should output the sequence of moves that maximizes Player 1’s score, as well as the score itself.
Input: A command line argument consisting of a string of n characters (n can be from 1 to 30), each of which is B or E (this is Player 2’s preset sequence of moves), followed by 2n command line arguments that denote the list of numbers from beginning to end.
Output: A string of n characters, each of which is B or E, that denotes Player 1’s optimal strategy, followed by the score achieved by Player 1 using that strategy.
Sample runs:
$ numbergame
BE 4 9 3 2
EB
11
$ numbergame
BEBE 5 80 500 0 800 3 1 17
EBBB
1397
- Avalanche!
Write a program named avalanche that models the following game, which uses the board illustrated below. The game consists of six vertical chutes (columns), labeled A through F, into which marbles can be dropped. Each pair of adjacent columns is joined by a seesaw-like device called a flip. Three flips are in the top row, joining columns A and B, C and D, and E and F, and two flips are in the bottom row, joining columns B and C, and D and E. Each flip can be flipped either to the left or to the right. Initially, all flips are flipped to the right, as shown. When a marble is dropped into an empty flip, either it will get caught, or it will change the orientation of the flip. If a marble is dropped into a flip that already holds another marble, it will release that marble and itself drop through. Four of the eight possible scenarios are illustrated below (the other four are simply mirror images):
Input: A single command-line argument representing the sequence of dropped marbles as a string consisting only of the uppercase letters A through F.
Output: A string indicating which chute each marble exits, with a hyphen (“-”) for each marble still held at the end of the game. This string should have the same order as the input (not necessarily the order in which marbles are released!).
Sample runs:
$ avalanche
AEACA
A-ACB
$ avalanche
FEDA
F--A
- Train
Travel
Write a program named trains that determines the best path to travel from one train station to another. Assume we have a train system in which each station is assigned a unique number from 1 to 999, and each train route, which consists of a sequence of adjacent stations, is assigned a unique letter from A to Z. All trains travel in both directions, i.e., from the first station on the route to the last and vice versa. Given a start station and end station, along with a list of the train routes in the system, your program should determine the length of the best path from the start station to the end station. You can assume that the system is completely connected so that there is always some way to get from one station to any other. The best path is defined as follows: If there is a path on which we do not have to change trains, that is the best path. If there are two such paths, the one with the fewest stations is best. If there is no direct path, then the one using the fewest trains is best. If two paths use the same number of trains, then the path visiting the fewest stations overall is best (each station along the path is only counted once).
Input: Your program should read a list of lines from standard input. The first line will contain the number of the start station and the number of the end station. The second line (and each subsequent line) will describe a train route; it will specify an uppercase letter denoting the route, followed by a list of adjacent station numbers that make up the route.
Output: The properties of the optimal path from the start station to the end station, in particular the number of different trains necessary, and the total number of stations visited, formatted as shown below.
Sample runs: (the files schedule1.txt and schedule2.txt describe 2 train systems)
$ more
schedule1.txt
1
4
C
3 5 6 7 8 10
A
1 2 3 5 9 12
P
4 22 19 13 6
$ trains
< schedule1.txt
trains
= 3
stations
= 9
Explanation (not part of output): Take train A from 1 to 5 Take train C from 5 to 6 Take train P from 6 to 4
$ more
schedule2.txt
1
4
C
3 5 6 7 8 10
A
1 2 3 5 9 12
P 4
22 19 13 6
Z
15 12 16 17 18 21 4
$ trains
< schedule2.txt
trains
= 2
Explanation (not part of output): Take train A from 1 to 12 Take train Z from 12 to 4
stations = 11