1996 USACO Qualifying Round


Welcome to the 1996 Qualifying Round of the USA Computing Olympiad.
Enclosedyou will find the five problems for this round. To qualify for
the USACO you must correctly solve at least three of the problems.

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 16. 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 at any time on February
9, 1996.

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 16, students must demonstrate their solutions
to a teacher or coordinator who will compare the output of the test
cases with the answers provided. If there is uncertainty 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 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 in consultation with the student. 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. We may examine these programs if it becomes necessary in our
selection of the finalists. If more than one student is entering,
submit as many as will fit in folders (directories) 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 Competition Round:




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.

Please fill out and return the form at the bottom of this page for all students
who qualify.

What languages may be used? The official languages that will be used at IOI
'96 in Hungary 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++. For the qualifying round you may
use your local 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,
1996. Graduating seniors are considered to be in secondary school. Only
residents of the United States are eligible to compete in the USACO.



FEBRUARY 9 -16

Q1. FACTORIALS

The factorial of an integer n, written n!, is the product of all the integers
from 1 through n inclusive. The factorial quickly becomes very large: 13! is
too large to store in a 32-bit integer on most computers, and 70! is too
large for most floating-point variables. Your task is to find the rightmost
non-zero digit of n!. For example, 5! = 1 * 2 * 3 * 4 * 5 = 120, so the
rightmost non-zero digit of 5! is 2. Also, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 =
5040, so the rightmost non-zero digit of 7! is 4.

Input:

An integer n, between 1 and 1000 inclusive.

Output:

The rightmost non-zero digit of n!

Test Case 1
Input:
5

Output:
2

Test Case 2
Input:
789

Output:
4

Test Case 3
Input:
1000

Output:
2

This program my be tested by entering in input from the keyboard.


Q2. TRANSFORMATIONS

A square pattern of black and white tiles is transformed into another square.
Write a program that will recognize the minimum transformation that has been
applied to the original pattern given the following list of possible
transformations:

90 Degree Rotation: The pattern was rotated to the right 90 degrees.
180 Degree Rotation: The pattern was rotated to the right 180 degrees.
270 Degree Rotation: The pattern was rotated to the right 270 degrees.
Vertical Reflection: The pattern was reflected vertically.
(See test case 4)
Combination: The pattern was reflected vertically and then subjected to one
of the rotations.
No Change: The original pattern was not changed.
Invalid Transformation: The new pattern was not obtained by any of the
above methods.

Input

The input file will consist of a number n (between 1 and 10 inclusive),
which is the size of the square, followed by n lines of the original
pattern, and then, after a blank line, the n lines of the transformed
pattern. A white square will be indicated by a period; and black
squares by an X.

Output

The output from your program should be a phrase describing the
transformation that changed the original pattern to the new pattern.
If more than one transformation is possible, then your program should
show the transformation corresponding to the minimal amount of work
necessary to convert the original pattern to the new pattern. For
the purposes of evaluating the amount of work needed, rotations are
considered less work than reflections, and smaller rotations are less
work than larger ones.

Note that only the above possibilities should be considered -- there
is no such thing as a 360 Rotation, nor is there a horizontal
reflection. Also remember that if a single rotation is not sufficient,
your program should consider a reflection followed by a rotation.


Test Case 1

Input:
5
X...X
.X...
...X.
..X.X
....X

....X
...X.
.X...
..X..
XX..X

Output:
ROTATED 90 DEGREES.

Test Case 2

Input:
6
....XX
...X..
XX..X.
..X...
...X..
..X..X

X....X
X.X...
.X..X.
...X.X
..X...
..X...

Output:
ROTATED 270 DEGREES.

Test Case 3

Input:
2
X.
.X

X.
.X

Output:
NOT TRANSFORMED.

Test Case 4

Input:
4
..X.
XX..
....
...X

...X
....
XX..
..X.

Output

REFLECTED.

Test Case 5
Input:
5
X....
.X...
.X...
...X.
....X


.X...
..X..
..X..
....X
X....

Output:
IMPROPER TRANSFORMATION.

Test Case 6
Input:
4
.X..
.X.X
....
..X.

..X.
X...
..XX
....

Output: REFLECTED AND ROTATED 270 DEGREES


Q3. GREEDY GIFT GIVERS

You are to determine, for a group of gift-giving friends, how much more each
person gives than they receive (and vice versa for those that view gift giving
with cynicism). In this problem, each person sets aside some money for
gift-giving and divides this money evenly among all those to whom gifts are
given. However, in any group of friends, some people are more giving than
others (or at least may have more acquaintances) and some people have more
money than others.

Given a group of friends, the money each person in the group spends on gifts,
and a (sub)list of friends to whom each person gives gifts: write a program
that determines how much more (or less) each person in the group gives than
they receive.

Input File Structure:

The input is a group of gift-givers which consists of several lines:

* The number of people in the group,
* A list of the names of each person in the group,
* A line for each person in the group consisting of
* The name of the person
* The amount of money spent on gifts
* The number of people to whom gifts are given
* The names of those to whom gifts are given.

All names are lower-case letters; there are no more than 10 people
in a group; no name is more than 12 characters in length. Money is
a non-negative integer less than or equal to 2000.

Output

The name of each person in the group should be printed on a line
followed by the net gain (or loss) received (or spent), (money in - money out)
by the person.
Names in a group should be printed in the same order in which they
first appear in the input.

All gifts are integers. Each person gives the same integer amount of
money to each friend to whom any money is given, and gives as much
as possible. Any money not given is kept and is not part of a person's
``net worth'' printed in the output.

Test Case 1

Input:
5
dave laura owen vick amr
dave 200 3 laura owen vick
owen 500 1 dave
amr 150 2 vick owen
laura 0 2 amr vick
vick 0 0

Output:

dave 302
laura 66
owen -359
vick 141
amr -150

Test Case 2

Input:
3
liz steve dave
liz 30 1 steve
steve 55 2 liz dave
dave 0 2 steve liz

Output:
liz -3
steve -24
dave 27

Test Case 3

input:
10
russ megan nick pete jerry jerome barbara superbhacker john jess
russ 2000 7 nick megan pete jerry barbara jerome jess
john 500 4 jess russ megan superbhacker
superbhacker 1000 3 jerry jerome barbara
jerry 660 2 russ pete
nick 0 0
jerome 0 3 jerry barbara superbhacker
barbara 1200 3 jerry jerome nick
megan 253 2 russ john
jess 450 3 john megan superbhacker
pete 1999 6 russ nick jerry jerome barbara superbhacker

output:
russ -1081
megan 308
nick 1018
pete -1383
jerry 691
jerome 1351
barbara -249
superbhacker -391
john -224
jess -40



Q4. RAUCOUS ROCKERS

You just inherited the rights to n previously unreleased songs recorded by
the popular group Raucous Rockers. You plan to release a set of m compact
disks with a selection of these songs. Each disk can hold a maximum of t
minutes of music, and a song can not overlap from one disk to another.

Since you are a classical music fan and have no way to judge the artistic
merits of these songs, you decide on the following criteria for making the
selection:

a) The songs on the set of disks must appear in the order of the
dates that they were written.

b) The total number of songs included will be maximized.

Input

The first line contains the values of n, t, and m (integer numbers
=20). The next line contains a list of the lengths of n songs,
ordered by the date they were written. No one song will be too long
to fit on a disk, and it will not be possible to put all the songs
on the disks.

Output

The output will be an integer indicating the number of songs that,
following the above selection criteria will fit on m disks.

Test Case 1

Input:
10 5 3
5 5 5 5 5 5 5 5 5 5

Output:
3

In this example there are ten songs and three disks. Each disk can
hold 5 minutes worth of songs. In this case, all the songs last five
minutes, so obviously only three songs can be recorded.

Test Case 2

Input:
5 6 4
4 3 4 4 5

Output:
4

Here there are 5 songs and 4 disks that can hold 6 minutes each.
However it is not possible to hold more than one song on any disk,
so only four songs can be recorded.

Test Case 3

Input:
10 5 3
3 5 1 2 3 5 4 1 1 5

Output:
6

In this example there are ten songs and three disks of five minutes
each. Let's label the songs:
3 5 1 2 3 5 4 1 1 5
a b c d e f g h i j
1 1 2 2 3 3
You can record three disks with songs {a, c}, {d, e}, and {g, h}
(there are other combinations that work as well). Total: 6 songs.


Test Case 4

Input:
2 1 1
1 1

Output:
1


Q5. ZERO SUM

Consider the sequence of digits from 1 through N (where N=9) in increasing
order

1 2 3 4 5 . . . N

and insert either a (+) for addition or a (-) for subtraction or a ( ) [blank]
to run the digits together. Now sum the result and see if you get zero.

Write a program that will find all sequences of length N that produce a ZERO
SUM.

Test Case 1

Input
7
Output
1 + 2 - 3 + 4 - 5 - 6 + 7 = 0
1 + 2 - 3 - 4 + 5 + 6 - 7 = 0
1 - 2 + 3 + 4 - 5 + 6 - 7 = 0
1 - 2 - 3 - 4 - 5 + 6 + 7 = 0
1 - 23 + 4 + 5 + 6 + 7 = 0
1 - 23 - 45 + 67 = 0

Test Case 2

Input
8

Output
1 + 2 + 3 + 4 - 5 - 6 - 7 + 8 = 0
1 + 2 + 3 - 4 + 5 - 6 + 7 - 8 = 0
1 + 2 - 3 + 4 + 5 + 6 - 7 - 8 = 0
1 + 2 - 3 - 4 - 5 - 6 + 7 + 8 = 0
1 + 23 - 45 + 6 + 7 + 8 = 0
1 - 2 + 3 - 4 - 5 + 6 - 7 + 8 = 0
1 - 2 - 3 + 4 + 5 - 6 - 7 + 8 = 0
1 - 2 - 3 + 4 - 5 + 6 + 7 - 8 = 0
1 - 23 - 4 + 5 + 6 + 7 + 8 = 0
12 - 34 -56 + 78 = 0

You may test this program by entering the integer from the keyboard.

(Use one report form for each student.)

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. FACTORIALS Test Case: 1 __ 2 __ 3 __

Q2.TRANSFORMATIONS Test Case: 1 __ 2__ 3 __ 4 __ 5 __ 6 __

Q3. GREEDY GIFT GIVERS Test Case: 1 __ 2 __ 3 __

Q4. RAUCOUS ROCKERS Test Case: 1 __ 2 __ 3 __ 4 __

Q5. ZERO SUM Test Case: 1 __ 2 __
Number of problems solved (all test cases correct) = ____
Signed ____________________________, Date _________________

**Deadline for this report to be at USACO is February 25, 1996.**

Disk:

Each student who qualifies (solves three or more problems) and wants to enter
the competition 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
(directory). (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 place 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.
25, 1996)

Fax to: 414-595-2056
or
e-mail to: piele@cs.uwp.edu


**Deadline for this report to arrive at USACO is February 25, 1996.**



Instructions to the Local Coordinator

The Competition Round will be held at your local site on Monday, March 11,
1995. This is a five hour event that must be monitored by you. The instructions
and problems will be mailed to you on paper on February 27. You will receive
the Competition Round problems via regular mail by March 6. Each student will
receive a sealed envelope so no one will see the problems until the competition
begins.

Please call if your materials have not arrived by the end of that day on
March 6.

If you have any questions please call: Don Piele, 414-634-0868, or e-mail,
piele@cs.uwp.edu. Another contact is Rob Kolstad at kolstad@BSDI.COM,
719-593-9445.

Good Luck!

Don Piele
USACO Director

Sponsor: USENIX