Usaco Open10 Bronze

Part of USACO Open10

**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Four problems numbered 11 through 14
**********************************************************************

Problem 11: Cow Pals [Traditional, 2010]

Bessie and all the other cows have an RFID serial number tag in
their ear so FJ can mechanically tally them. Many cows have a
'cowpal' whose serial number is equal to the sum of the divisors
(that are not the number itself) of their own serial number. Some
cows don't have a cowpal because no cow's serial number matches
their divisor sum.

Some cows have a superpal. Cows are superpals when their serial
numbers make each of them a pal of the other. Cows that are superpals
of themselves are shunned; do not consider them!

Given a serial number S (6 <= S <= 18,000), find the first cow with
serial number at least S who has a super pal.

By way of example, consider serial number 220 whose divisors are 1, 2, 4,
5, 10, 11, 20, 22, 44, 55, and 110. Their sum is 284. Similarly, the
divisors of 284 are 1, 2, 4, 71, and 142. Their sum is 220.

PROBLEM NAME: cowpals

INPUT FORMAT:

* Line 1: A single integer: S

SAMPLE INPUT (file cowpals.in):

206

OUTPUT FORMAT:

* Line 1: A single line with two space-separated integers that are the
        serial number of the first superpal whose serial number is no
        smaller than S and the serial number of her pal.

SAMPLE OUTPUT (file cowpals.out):

220 284

**********************************************************************

Problem 12: Mountain Watching [Jeffrey Wang, 2009]

One day, Bessie was gazing off into the distance at the beautiful 
Wisconsin mountains when she wondered to herself: which is the 
widest one?

She decided to take N (1 <= N <= 10,000) height measurements H_i
(1 <= H_i <= 1,000,000,000) sequentially along the horizon using
her new Acme Long Distance Geoaltimeter. 

A mountain is defined to be a consecutive sequence of H_i values
which increases (or stays the same) and then decreases (or stays     
the same), e.g., 2, 3, 3, 5, 4, 4, 1. It is possible for a mountain
on the edge of her field of vision only to increase or only to      
decrease in height, as well.

The width of a mountain is the number of measurements it encompasses.
Help Bessie identify the widest mountain.

Here's a simple example of a typical horizon:

           *******                   *
          *********                 ***
          **********               *****
          ***********           *********               *
*      *****************       ***********             *** *
**    *******************     *************   * *     *******      *
**********************************************************************
?ddsssuussuussssssddddssddssssuuuuuuuuddddddssududssssuuudduddsssssuds
3211112333677777776543332111112344456765432111212111112343232111111211
aaaaa                     cccccccccccccccccccc eeeeeee    ggggggggg
  bbbbbbbbbbbbbbbbbbbbbbbbbbbb             ddddd ffffffffff  hhhhhhhhh

The mountains are marked 'a', 'b', etc.  Obviously, mountain b is
widest with width 28.

Hint: Sometimes it's easiest to find a mountain's width by knowing
where its highest parts are.

PROBLEM NAME: mount

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single integer: H_i

SAMPLE INPUT (file mount.in):

7
3
2
3
5
4
1
6

INPUT DETAILS:

The height measurements are 3, 2, 3, 5, 4, 1, 6.

OUTPUT FORMAT:

* Line 1: A single line with a single integer that is the width of the
        widest mountain.

SAMPLE OUTPUT (file mount.out):

5

OUTPUT DETAILS:

The widest mountain consists of the measurements 2, 3, 5, 4, 1. Other
mountains include 3, 2 and 1, 6

**********************************************************************

Problem 13: Relay race [Jelle van den Hooff, 2010]

The N (1 <= N <= 1,000) cows conveniently numbered 1..N are competing
in a unique relay race during which multiple cows can run simultaneously.

Before time t=0, each cow is positioned at the starting line, waiting
for her turn to run one lap around a circular track whose finish
line is the same as the starting line.

At time t=0, cow 1 starts running around the track and re-crosses
the starting line exactly L_1 seconds later. In general, cow i's
time to run a lap is L_i (1 <= L_i <= 1,000). As soon as she
re-crosses the starting line, she signals M_1 other cows numbered
A_1j to start instantly. Generally, cow i signals M_i cows (0 <=
M_i <= N) named A_ij (1 <= j <= M_i) to start running. Sooner or
later, every cow is signaled at least once. Sometimes M_i might be
0 and no A_ij's exist.

Each of the signaled cows starts running and performs the signaling
procedure when recrossing the starting line. Multiple cows might
signal the same cow, but every cow wants to run only one lap, so
signals after the first one it receives are ignored.

Farmer John wants you to determine the total race time (i.e., how
long it takes for the final cow to complete her lap).

Consider a small race with 5 cows. The table below shows the Cow
ID (i), her time to run a single lap (L_i), the number of signals
cow i will perform when she finishes (M_i), and the (potentially
empty) list of cows to be signaled (A_ij):

            i   L_i  M_i   A_i*
            1    4    2    2 4
            2    3    3    1 3 4
            3    7    1    5
            4    4    2    3 5
            5    1    0

Starting cow 1 at time 0 leads to this timeline of events:

   TIME        Event
     0        Cow 1 starts running
     4        Cow 1 finishes; signals 2 and 4
     4        Cow 2 starts running (time to finish: +3 seconds -> 7)
     4        Cow 4 starts running (time to finish: +4 seconds -> 8)
     7        Cow 2 finishes; signals 1, 3, and 4
     7        Cows 1 and 4 ignore the duplicate signal
     7        Cow 3 starts (time to finish: +7 seconds -> 14)
     8        Cow 4 finishes; signals 3 and 5
     8        Cow 3 ignores the duplicate signal
     8        Cow 5 starts (time to finish: +1 seconds -> 9)
     9        Cow 5 finishes but has no other cows to signal
    14        Cow 3 finishes; signals 5
    14        Cow 5 ignores the duplicate signal
    14        All cows have finished

Thus, the race will last 14 seconds.

PROBLEM NAME: relayrace

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains multiple space-separated integers:
        L_i, M_i and then M_i integers A_ij

SAMPLE INPUT (file relayrace.in):

5
4 2 2 4
3 3 1 3 4
7 1 5
4 2 3 5
1 0

OUTPUT FORMAT:

* Line 1: A single integer, the time the last cow finishes

SAMPLE OUTPUT (file relayrace.out):

14

**********************************************************************

Problem 14: Cow Typing [Jelle van den Hooff, 2010]

The cows have discovered e-mail and have happily been receiving
messages from Farmer John. Responding, though, is quite a challenge
since cows (with their hooves) have difficulty using normal computer
keyboards. Luckily, Farmer John has created a snazzy cow input
system.

The system consists of four large buttons and a display. The buttons
are labeled 'previous', 'next', 'add' and 'print'. Instead of typing
letters, the cows select letters and then add these to form words.
Most people don't know that cows use only capital letters to send
email, but that's the way they do it.

FJ is a clever guy. He knows that the cows will only use words they
know (a list of which is found, one per line, in the file 'dict.txt').
No word is longer than 20 characters; the dictionary has fewer than
25,000 words. The actual dictionary can be downloaded for testing
from http://ace.delos.com/usaco/dict.txt .

The display contains two lines:

     * The word formed so far

     * A list of potential next letters for this word -- one letter
       is highlighted.

The cows use the 'next' and 'previous' keys to move the highlight
to the next letter or previous letter in the list (which is circular
so that the first letter in the list is the 'next' letter after the
last one and similarly for the 'previous' letter).

The list of potential next letters reduces the cows' effort, since
a word starting with 'B' will never have 'D' as its second letter,
thus removing one possibility the cows need to deal with.

When the word formed so far is empty, the list contains the first
letters of all possible words. By way of example, if a small
dictionary comprises just four words ('ACE', 'APPLE', 'BANANA', and
'PEAR'), the buttons cycle through 'A', 'B', and 'P' (starting with
'A').

When a cow presses 'add', the highlighted letter is added to the
end of the current word, and the list of potential next letters is
instantly updated. In the example from the previous paragraph, if
'A' is added as the first letter of the word formed so far, then
the list of potential next letters will become 'C' and 'P', with
the 'C' highlighted, since it's the letter earliest in the alphabet.

The 'print' button adds the word to the email, and the process is
started all over again.

Using the four word sample dictionary, the table below shows the
sequence to add the word apple (*A* means A is highlighted):

Action       WORD          Potential Letters
[initial]    _________     *A* B P
ADD          A________     *C* P
NEXT         A________     C *P*
ADD          AP_______     *P*
ADD          APP______     *L*
ADD          APPL_____     *E*
ADD          APPLE____     
PRINT        _________     *A* B P

Note that this set of operations takes 7 button presses, only 2
more than with a normal keyboard (one more if you have to type a
space)!

Farmer John doesn't want the cows to get tired and would like to
know how many presses are needed to send a simple e-mail containing
N (1 <= N <= 20) words.

PROBLEM NAME: typing

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Each line contains a single word to be printed.

SAMPLE INPUT (file typing.in):

5
HELLO
FARMER
HOW
ARE
YOU

INPUT DETAILS:

A message consisting of the 5 words "HELLO FARMER HOW ARE YOU"

OUTPUT FORMAT:

* Line 1: The output consists of a single number on a single line, the
        number of presses required to enter the message.

SAMPLE OUTPUT (file typing.out):

92

OUTPUT DETAILS:

A total of 92 presses: 27 for HELLO, 22 for FARMER,  16 for HOW, 17 for
ARE and 10 for YOU.

**********************************************************************
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License