SRU High School Computer Programming Contest

February 17, 2004

Official Problem Set

General Directions:

You may assume that all data is valid.
You must program for all valid special cases.
Do not open any files for reading or writing. Read from stdin and write to stdout. RockTest will automatically redirect your data file into stdin.
Only output counts unless the problem specifically says otherwise.
Upper-division teams may solve only upper-division problems, until you have solved all upper-division problems.

Lower-Division Problems

1. counting

Given two whole integers, count from one to the other, printing the numbers. You may assume that the two integers are in ascending order. There will be one space (or comma if you use BASIC or Python) between integers in the data file. Print the numbers on one line, separated by single spaces. You may assume that there will not be more than 80 characters of output.

Test data:

3 8

Output from test data:

3 4 5 6 7 8

2. Equations

Given an integer equation of the form a op b = c, where a, b, and c are integers and op is +, -, *, or /, verify whether the equation is true. The first line in the data will indicate how many of equations there are; the subsequent lines are the data, one equation per line. Your output must be in the form used in the output for the test data below.

Test data:

10 + 12 = 14

12 / 2 = 6

2 / 5 = 2

3 * 4 = 12

4 - 6 = -2

Output from test data:

10 + 12 = 14 false

12 / 2 = 6 true

2 / 5 = 2 false

3 * 4 = 12 true

4 - 6 = -2 true

3. Hcabdlog

Goldbach's conjecture states that any even number larger than 2 can

be expressed as the sum of two primes. But what about the reverse:

can a prime number be expressed as the sum of two even numbers?

Given two positive even integers, where the second is larger than the first,

compute and print the number of prime numbers in that inclusive

interval that can be expressed as the sum of two even numbers. The

data file will have two numbers per line; print one line of output

for each line of input.

Test data:

74 88

22 1906

Output from test data:

4. Lottery

Assume a lottery winner must choose between two payment schedules. Either schedule covers 20 years. The amount paid at the beginning of each year is listed in the schedule (even if it is zero). All payments are made at the beginning of the year, hence interest starts accruing immediately. The final payment cannot be made later than the beginning

of the 20th year and the total amount accrued using both schemes will be compared immediately after receiving any payment for the 20th year.

The interest rate expected for each year will be listed at the beginning of the line representing that year in the schedule. Suppose you can get 3.5% interest on savings the first year, 3.3% the second year, etc., and that Schedule A calls for a $1000 payment the first year and second years, etc., and that Schedule B calls for a $10,000 payment the first year and no payment the second year, etc. Then, the first two lines

of input would look like:

APR SchedApayment SchedBpayment <--for explanation only. Not in data file.

3.5 1000 10000

3.3 1000 0

etc.

Interest rates stated are Annual Percentage Rates. That is, you may assume

that interest compounds annually at the value indicated for that year. In the

example above, 3.5 represents 3.5%, and the other values are all dollar

amounts. Note: the interest rate in the 20th year is not needed, since no

interest will accrue that year.

Determine the value of both payment schedules at the beginning of the 20th

year. Using the format shown in the test-data output, print the value of Schedule A

and the value of Schedule B. Test data is shown space-separated. It may be comma-separated for BASIC and Python programmers.

Test data:

10 1000 10000

10 1000 0

0 1000 0

1 1000 0

5 1000 0

5 1000 10000

5 1000 0

Output from test data:

Schedule A yields: $32707.27

Schedule B yields: $41695.53

Upper-Division Problems

5. Sort Fractions

Given a line of proper fractions, print the fractions in ascending order. Repeat for each line of data.

Each fraction is written in the form <numerator>/<denominator>, and fractions are separated by one space. No input line will be more than 80 characters long. There will be a minimum of two fractions per line of input. Print one line of output for each line of

input. Python and BASIC programmers may assume a comma-separated data file.

Test data:

7/8 1/2 5/9 123/132

15/16 1/9

1/2 1/3 1/4 1/5 1/6 1/7 1/8 1/9 1/10

Output for test data:

1/2 5/9 7/8 123/132

1/9 15/16

1/10 1/9 1/8 1/7 1/6 1/5 1/4 1/3 1/2

6. Quadratic

Given a set of x-y coordinates, find and print the quadratic equation, of the curve to which they all belong. You may assume that each such quadratic equation has integer coefficients, 100>|A|>=|B|>=|C|, and that at least one coefficient is non-zero.

Each line of data represents a distinct quadratic equation, and takes the form

x1 y1 x2 y2 x3 y3 (or x1,y1,x2,y2,x3,y3 for Python and BASIC programmers). Each output line should be of the form y = Ax^ + Bx + C, where A, B, and C represent the actual integer coefficients. Do not print multiple signs, e.g., if the equation is

y = 17x^2 -3x -1, do not print y = 17x^2 +-3x +-1. Do not print a zero term, unless it is the only term. Leave exactly one space between terms and around the "=" sign. Read and process data lines until end-of-file.

Test data:

4 41 -1 6 10 281

-5 100 0 0 5 100

-6 -96 -2 -8 -1 -1

Output for test data:

y = 3x^2 -2x +1

y = 4x^2

y = -3x^2 -2x

7. Aibohphobia

Given a collection of subject nouns, verbs, adjectives, and direct-object

nouns, find all of the palindromes that can be built from them of the

form <subject noun> <verb> <adjective> <direct-object noun>. For purposes

of this problem, a palindrome is a sentence which is spelled the same

forwards and backwards, ignoring spacing and punctuation.

The data file will consist of four lines: a line of subject nouns, a

line of verbs, a line of adjectives and a line of direct-object nouns.

The number of words on a line may vary, i.e., some words may be used in more than

one palindrome. It does not matter which palindrome you print first, second, etc.,

but print one palindrome per line. Don't forget the space between words and the

period at the end of each sentence. Output must be capitalized the same as the input. BASIC and Python users' data files have commas between the words.

Test data:

Del Emil Ma

saw has

sled slime ham

Output from test data:

Del saw a sled.

Emil saw a slime.

Ma has a ham.

8. Mines

Given the playing board at one point in the game "Minesweeper", determine the necessary locations for mines. For each space on the board which has unknown neighbors, determine each of the unknown neighbors only from information available in the current space and its seven neighbors ("local knowledge"). Each mine or free space found may make it possible to find another mine or free space; keep searching the entire board until no new mines or free spaces can be found.

The board is represented by nine lines of nine characters each. The 9x9 play area contains characters with the following meanings:

Character Meaning

M already determined to be a mine location - assume to be correct.

. a hidden location on the board. This location has not been selected yet.

0 already selected and there are no neighboring mines.

1 already selected and there is 1 neighboring mine.

2 already selected and there are 2 neighboring mines.

3 already selected and there are 3 neighboring mines.

et cetera

Read a board configuration.

Determine which locations must hide a mine, using local knowledge only. Determine which locations must be free of mines, using local knowledge only. Print the board indicating all new mine locations with the '@' character, and all free locations with the 'F' character.

What you should not do:

You may be able to infer information about a particular location using the data at multiple neighboring sites. Do not do this. Each decision made by your program will be based solely on the information available at the current location and that location's 8 immediate neighbors. (Note that cells on the borders have fewer neighbors.

Example from lower-left of display:

|.... |...@

|113. |113.

|001. |001.

----- -----

When considering the cell marked 3, the location of the mine shown can be inferred, but only from knowledge gained from neighboring sites. Hence, your program would NOT mark the location shown.

There is exactly one set of data. There is no comma-separated data for BASIC and Python programmers; all will use the same data format.

Test data:

1..........

...........

1111.......

00012......

000012212..

000000002M.

00001110111

00001.10000

00001110000

00000000000

Output from test data:

1F.........

F@FFF......

1111@F.....

00012@@FFF.

000012212@.

000000002MF

00001110111

00001@10000

00001110000

00000000000

9. Color Map

Assume a NxM video screen (N times M pixels). Images on the screen are represented as follows:

First, the integer number of rows, N, and the integer number of columns, M, separated by a blank (or comma) on the first data line, with 0 < N < 24 and 0 < M < 80.

Second, a color map consisting solely of a list of characters, in order, all on one line, that represents the values to be entered into the image's color map. There will be at most 100 such characters. The data on this line is not comma-separated, even for BASIC and Python users.

Beginning with the top row (raster scan line) we list pairs

numPixelsInSpan colorMapIndex

where the color table index gives the value of this pixel and the number of pixels in the span tells how many pixels will have this same value. Row 1 is assumed to wrap around to row 2, etc.

The values that make up a data pair will be separated by one space (or a comma). Data pairs will be separated by a newline. Each data set will end with a marker or sentinel value: 0

An example of a minimal valid data set would be:

20 60

1200 1

(This means 20 rows, 60 columns; the first (and, in this case, only) "color" is "#"; there are 1200 copies of color 1 in the first (and only) span in the image; and there are no more pixels in the image.)

Files that contain the number 0 for a span, but have more data are assumed to be of an older type. This is not a corrupt file. All data following the sentinel on the line is simply ignored. If a span value (other than 0) appears on a line, there will be an additional color index to read.

Continue reading and processing data sets until end-of-file. Skip a line between output sets.

Test data:

5 55

/>(-*)OX=\

14 1

1 2

1 3

40 1

1 4

11 1

2 2

37 5

1 4

2 1

1 4

1 6

1 7

1 8

1 9

1 8

1 9

1 8

1 9

1 8

1 9

1 8

1 4

1 6

1 3

38 10

1 11

2 1

1 4

11 1

2 11

39 5

1 7

14 1

1 11

1 3

39 1

Output from test data:

( //-------------------------------------(

(*)OXOXOXOXO(*>======================================\

( \\---------------------------------------)

10. IQ

Consider the "IQ" test game with 14 pins and 15 locations (equilateral triangle). Pins can move only parallel to one of the sides, must jump a pin and end in an empty location. The jumped pin is removed from the board. Normally, the object of the game is, after jumping pins until you cannot make another legal move, to have as few pins as possible (one!) left on the board.

In your program, you are to determine how many start locations (the initial empty location) allow you to end up with exactly one pin in location 5. Your output should consist of a line containing only that number.

2--3

/ \/\

4--5--6

/ \/ \/ \

7--8--9--10

/ \/ \/ \/ \

11-12-13-14-15

This problem requires an algorithmic solution. Merely printing the answer will

not be considered correct.

There is no data for this problem. However, RockTest REQUIRES a datafile. Create an empty data file for this problem or RockTest will not be able to handle your program.

The output should be an integer, the number of

Test data:

Output for test data (not necessarily correct):