If you are a student, your mission is to solve as many of these problems as possible during the period from February 9 to February 15. If you are a local teacher or coordinator, you should distribute these problems to all interested students on February 9. Here are the guidelines:
* Students may begin working on the problems on February 9. * Students may work on them at any location (even at home), but they should work on them individually. * Students should not use any reference materials, previous programs, or other aids, except a language manual. * On or before February 15, students must demonstrate their solutions to a teacher or coordinator who will compare the output of the test cases with the answers provided on the answer sheet enclosed. (Please keep the test cases and the answer sheet secret until the last student has been judged.) If you are not certain how to enter the test cases, have the student do it for you. * To be judged correct, all programs must give the correct answer to a test case within three minutes. Unless the program is correct for all test cases, it should not be judged 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. However, a copy of all source code created by each student who qualifies and enters the Competition Round must be submitted on disk along with his or her entry. * Reaching any of the following three levels qualifies a student for the Competition Round. Also, a certificate of achievement will be awarded to each qualified student as follows: 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 way environment.
Please fill out and return the form on the back of this page for all students who qualify.
1. Ordered Fractions
Consider the set of all reduced fractions (rational numbers)
between 0 and 1 inclusive with denominators less than or
equal to N.
Here is the set when N = 5:
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
Write a program that, given an integer N between 1 and 100
inclusive, prints the fractions in order of increasing
magnitude. You should also print the total number of
fractions.
SAMPLE RUN
Enter the maximum denominator: 5
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
There were 11 fractions.
TEST CASES:
Test your program for
N = 23, 54, 99.
2. Number Triangles
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Fig. 1
Figure 1 shows a number triangle. Write a program that
calculates the highest sum of numbers passed on a route that
starts at the top and ends somewhere on the base. Each step
can go either diagonally down to the left or diagonally down
to the right.
In the sample shown in Fig. 1, the route from 7 to 3 to 8 to
7 to 5 produces the highest sum: 30.
TECHNICAL CONSTRAINTS:
1. Put your input file for each test case in a text file
named NUMBER.IN.
2. The number of rows in the triangle is > 1 but <= 100.
3. The numbers in the triangle are all integers between 0 and
99 inclusive.
SAMPLE RUN
NUMBER.IN appears as follows: The first number is the number
of rows in the triangle followed by the numbers in each row.
Thus the triangle in Fig 1 should be stored in NUMBER.IN as
follows:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
The answer is:
30
TEST CASE:
A test case will be supplied by your teacher or coordinator.
3. SuperPrime Rib
Butchering Farmer John's cows always yields the best prime
rib. You can tell prime ribs by looking at the digits
lovingly stamped across them, one by one, by FJ and the USDA.
Farmer John ensures that a purchaser of his prime ribs gets
really prime ribs because when sliced from the right, the
numbers on the ribs continue to stay prime right down to the
last rib, e.g.:
7 3 3 1
The set of ribs 7331 is prime; the three ribs 733 are prime;
the two ribs 73 are prime, and, of course, the last rib, 7,
is prime. The number 7331 is called a superprime of length
4.
Write a program that accepts a number N of ribs and prints
all the superprimes of that length.
TECHNICAL CONSTRAINTS:
1. The number 1 (by itself) is not a prime number.
2. The number of ribs N satisfies 1ēNē8.
3. Exit if the number of ribs is entered as 0.
Sample Run
Number of ribs N: 4
2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797
5939 7193 7331 7333 7393
TEST CASES:
N = 7, 8
4. Betsy's Tour
A square township has been divided up into N^2 square plots.
The Farm is located in the upper left plot and the Market is
located in the lower left plot. Betsy takes her tour of the
township going from Farm to Market by walking through every
plot exactly once. Shown below is one possible tour for Betsy
when N=3.
Write a program that will count how many unique tours Betsy
can take in going from Farm to Market for any value of N