Sewickley Academy Programming Team:  November 2001 Contest
David Kosbie (Faculty Advisor)
Sewickley Academy

Link to Sewickley Academy Programming Team Home Page
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
   ====================================================================