BE SURE TO READ THE CONTEST RULES FIRST!DO NOT PROCEED UNTIL YOU ARE READY TO BEGIN THE CONTEST!
YOU MUST WORK FOR 3 HOURS (MAX) WITH NO BREAKS!
DO NOT TALK TO ANYONE FOR ANY REASON DURING THE 3 HOURS.
Remember to submit your answers on Monday as this weekend's assignment.
Good luck!
DK
***************************************************************************
***************************************************************************
DO NOT READ BELOW HERE UNTIL YOU ARE READY TO START THE THREE HOUR CONTEST.
***************************************************************************
***************************************************************************
***************************************************************************
USA Computing Olympiad
Green Division
***************************************************************************
Four Problems Numbered 1 through 4
***************************************************************************
PROBLEM 1: Cow Dominoes [Korean training problem submitted by Joseph Lim]
The cows are playing dominoes with N (1 <=
N <= 40) domino tiles. Each
domino has two numbers in the range 0..9
arranged one on top of the other,
like this:
+---+
| 5 |
+---+
| 2 |
+---+
The figure below depicts three dominoes arranged
side-by-side along with
two base 10 integers that represent the arrangement:
+---+
+---+ +---+
| 5
| | 3 | | 4 | 5 * 100 + 3 * 10 + 4 * 1 = 534
+---+
+---+ +---+
| 2
| | 4 | | 1 | 2 * 100 + 4 * 10 + 1 * 1 = 241
+---+
+---+ +---+
Of course, any domino can be rotated 180 degrees,
swapping the top and
bottom numbers:
+---+ +---+
| 5 | | 2 |
+---+ -> +---+
| 2 | | 5 |
+---+ +---+
The particular game the cows are playing requires
laying down the N
dominoes (choosing the order and the rotation)
so that the sum of the two
base 10 representations is maximized.
For the example above, the maximum
sum is 775. Your job is to calculate that
maximum sum.
PROBLEM NAME: cowdom
INPUT FORMAT:
* Line 1: One line with a single integer: N
* Lines 2..N+1: Each line contains two integers describing a domino.
SAMPLE INPUT (file cowdom.in):
3
1 4
2 5
3 4
OUTPUT FORMAT:
One line with a single integer that is the
maximum possible sum of the base
10 representations of the dominoes laid out
side-by-side.
SAMPLE OUTPUT (file cowdom.out):
775
---------------------------------------------------------------------------
PROBLEM 2: Cow Plumbing [Kolstad, 2001]
The cows want to move water from the pond
to the barn, a distance of D (7
<= D <= 100,000). They have a
set of P (1 <= P <= 350) pipes, each with
positive integer length Li and positive integer
capacity Ci (both numbers
fit in 24 bits).
The pipes can be connected in series into
a run: the connected pipes have
the capacity that is the least of all pipes'
individual capacities. A run
must reach precisely D units (i.e., the sum
of the Li's for the pipes in
a run must be D).
Find the maximum amount of water that can
be moved from the pond to the
barn in one single run of pipe.
PROBLEM NAME: plumb
INPUT FORMAT:
* Line 1: One line with two integers: D and P
* Lines 2..N+1: Each line contains two integers
describing a pipe: Li
and Ci
SAMPLE INPUT (file plumb.in):
7 6
4 5
3 6
2 7
1 4
6 7
1 5
OUTPUT FORMAT:
One line with a single integer that is the maximum possible legal flow.
SAMPLE OUTPUT (file plumb.out):
5
---------------------------------------------------------------------------
PROBLEM 3: Dinner Time [Burch, 2001]
Farmer John has N (3 <= N <= 50000)
cows, each branded with a unique serial
number in the range 1..N. Each night,
they line up for dinner by forming
a line (queue) with the cows in a relatively
random order. Any given
ordering can be expressed as an N digit number
in base N.
Farmer John doesn't like random ordering.
He wants the cows to line up in
a way such that the number that represents
the ordering is minimized. The
cows, however, don't like do be told exactly
what to do all the time.
FJ and the cows have reached a compromise:
the cows will line up and then
rearrange themselves into a certain new order
that minimizes the ordering's
representation. The trick is that each
serial number in the new ordering
can differ by no more than 1 from the serial
number that used to occupy
that slot.
If 8 cows lined up like this:
8 5 7 3 6 4 2 1
Then the new ordering would be: 7 4 8 2 6
5 3 1
because:
* No slot in the second list contains a digit that differs from
the digit above by more than 1 (sometimes the difference is 0)
* This is the smallest number that can be obtained using the rules.
Your job is to tell FJ the new ordering of
cows so he can ensure they
are lined up properly.
PROBLEM NAME: dinner
INPUT FORMAT:
* Line 1: One line with a single integer: N
* Lines 2..N+1: Each line contains a single
integer that is the serial
number of a cow in the respective slot. The left-hand cow
is given first.
SAMPLE INPUT (file dinner.in):
8
8
5
7
3
6
4
2
1
OUTPUT FORMAT:
N lines, each with a single integer that tells
which cow belongs in the
respective slot. The first output line
should contain the serial
number of the cow in the left-hand slot (and
so on).
SAMPLE OUTPUT (file dinner.out):
7
4
8
2
6
5
3
1
---------------------------------------------------------------------------
PROBLEM 4: Cowese [Dan Adkins, 2001]
It is a little known fact that the cows love
word games. They have their
own cow crossword puzzles, cow word-find
grids, and all sorts of other cow
word games.
The cows need some computer assistance, though,
in order to design certain
word games. They have lists of N distinct
words (2 <= N <= 20,000) no
longer than 100 characters, all of which
are lower-case and contain only
the letters 'a'..'z'.
They need to find two words in the list that
share the longest prefix
(i.e., the first C characters of the words
match and C is the longest
length for all possible pairs of words).
The input datasets are guaranteed
to have at least one pair of words with a
shared prefix.
If more than two word pairs share prefixes
of the same maximal size, the
cows want to see the pair whose first word
is closest to the beginning of
the supplied list and whose other maximal-prefix
word is closest to the
beginning of the list.
PROBLEM NAME: prefix
INPUT FORMAT:
* Line 1: One line with a single integer: N
* Lines 2..N+1: Each line contains a single word.
SAMPLE INPUT (file prefix.in):
9
noon
is
lunch
for
most
noone
waits
until
two
OUTPUT FORMAT:
Two lines, each with a single word.
SAMPLE OUTPUT (file prefix.out):
noon
noone
***************************************************************************
***************************************************************************
USA Computing Olympiad
Orange Division
***************************************************************************
Five Problems Numbered 5 through 9
***********************************************************************
PROBLEM 5: [Traditional]
Powers of two are just so easy to calculate.
To find the Nth power of 2,
just multiply 2 by itself N times (where
2 to the 0th power is 1 and 2 to
the 1st power is 2). Thus, we have
a power table:
N 2 to
the Nth power
2
4
5
32
10
1024
Write a program that reads N (1 <= N <=
30) and prints 2 to the Nth power.
Do not use a table of precalculated numbers
in your program.
PROBLEM NAME: power
INPUT FORMAT:
A single line with integer N.
SAMPLE INPUT (file power.in):
10
OUTPUT FORMAT:
A single line with 2 to the Nth power.
SAMPLE OUTPUT (file power.out):
1024
----------------------------------------------------------------------
PROBLEM 6: Dictionary Numbers [Piele, 2001]
The number 79 becomes "seven nine" when translated
digit by digit into a
string of words. Likewise 80 becomes "eight
zero"
When sorted as numbers, 79 comes before 80.
But as a translated string,
the number "eight zero" comes before "seven
nine" in dictionary order.
Write a program that reads two whole numbers
M and N (1 <= M < N <= 999)
and finds the first and last numbers in dictionary
order of the numbers
in the range M..N inclusive
PROBLEM NAME: dictnum
INPUT FORMAT:
A single line with two integers: M and N
SAMPLE INPUT (file dictnum.in):
7 20
OUTPUT FORMAT:
A single line with two space-separated integers
that are the first and last
numbers when the numbers are sorted in dictionary
sequence.
SAMPLE OUTPUT (file dictnum.out):
8 20
---------------------------------------------------------------------------
PROBLEM 7: Hungry Cows [Brian Dean, 2001]
The cows are lined up at their feed trough,
which has individualized
feeding buckets numbered sequentially from
1 through N (1 <= N <= 2000).
Each night a lucky cow gets to eat from a
number of buckets according to
Farmer John's rules.
Farmer John posts a list of no more than B
bucket-sequences (a bucket
sequence is a pair of integers (a pair like
start-end where 1 <= start <=
end <= N and the sequence includes buckets
start through end, e.g., 1-3,
7-8, 3-4). FJ's rules allow the cow to choose
as many of the intervals as
she wishes, as long as no bucket is mentioned
more than once in the total
set of chosen intervals.
Of course, cows are like anyone else and want
as much feed as they can get.
Given a set of bucket-sequences, help the
lucky cow find the best sequence
which yields the greatest amount of feed.
In the example above, bucket-sequences 1-3
and 3-4 overlap; the wise cow
chooses the set of {1-3, 7-8} for a lavish
dinner of five buckets.
PROBLEM NAME: hunger
INPUT FORMAT:
* Line 1: One integer B (1 <= B <= 1000)
* Lines 2..B+1: Each line contains a two integer
bucket sequence with
the smaller bucket number first
SAMPLE INPUT (file hunger.in):
3
1 3
7 8
3 4
OUTPUT FORMAT:
A single line with a single integer that is
the greatest number of feed
buckets the lucky cow can eat.
SAMPLE OUTPUT (file hunger.out):
5
----------------------------------------------------------------------
PROBLEM 8: Cow Shuffle [Piele, 2001]
Each time cows shuffle a deck of 2N (1 <=
N <= 9,000) cards marked 1..2N
they do it as follows:
* Cut the deck exactly in half to form two
piles (A and B) of N cards each.
A is the top N cards and B is the
bottom N cards.
* Combine the cards back together into a single
pile by taking one card
from pile A and placing it face down
on a new pile and then one card from
pile B and placing it face down on
top of the first card, then one from
A and one from B and so on until all
the cards are perfectly shuffled
back into a single pile.
They repeat this cow shuffle again and again
until the cards are back in
their original order.
Given N, how many cow shuffles does it take
to return the cards to their
original order?
EXAMPLE:
Let N be 3; therefore, the the cards are {1,
2, 3, 4, 5, 6} and the
shuffles go like this:
orig shuf1 shuf2
shuf3 shuf4
1 6
1 6 1
2 3
5 4 2
3 -> 5 ->
4 -> 2 -> 3
4 2
3 5 4
5 4
2 3 5
6 1
6 1 6
So, four cow shuffles suffice to put the deck of three cards back in order.
PROBLEM NAME: shuffle
INPUT FORMAT:
A single line with the integer N
SAMPLE INPUT (file shuffle.in):
3
OUTPUT FORMAT:
A single line with the integer number of shuffles
required to return
2N cards to their original order.
SAMPLE OUTPUT (file shuffle.out):
4
----------------------------------------------------------------------
PROBLEM 9: Negative Powers [Traditional]
Negative powers of two are kind of easy to
calculate. To find the -Nth
power of 2, just find the Nth power of 2
(see Problem 5) and invert it: 2
to the -1st power is 0.5; 2 to the -10th
power is 0.0009765625). Thus, we
have a power table:
N 2 to
the -Nth power
2
0.5
5
0.03125
10 0.0009765625
Write a program that reads N (1 <= N <=
999) and prints 2 to the -Nth power.
Print the number with precisely one lead
0, the decimal point, and then
the rest of the digits. Do not print
trailing 0's.
PROBLEM NAME: neg
INPUT FORMAT:
A single line with integer N.
SAMPLE INPUT (file neg.in):
10
OUTPUT FORMAT:
A single line with 2 to the -Nth power in the format specified above.
SAMPLE OUTPUT (file neg.out):
0.0009765625
****************************************************************************
END OF CONTEST TEXT
****************************************************************************
====================================================================
/\ * Rob Kolstad
http://www.delos.com
* /\/ \
kolstad@delos.com
15235 Roller Coaster Road
/ \
\ +1 719-481-6542
Colorado Springs, CO 80921
====================================================================