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`
` ====================================================================`