Usaco Dec11 Bronze

Part of USACO Dec11

``````**********************************************************************
BRONZE PROBLEMS
**********************************************************************
Three problems numbered 1 through 3
**********************************************************************

Problem 1: Hay Bales [Brian Dean, 2011]

The cows are at it again!  Farmer John has carefully arranged N (1 <= N <=
10,000) piles of hay bales, each of the same height.  When he isn't
looking, however, the cows move some of the hay bales between piles, so
their heights are no longer necessarily the same.  Given the new heights of
bales he needs to move in order to restore all the piles to their original,
equal heights.

PROBLEM NAME: haybales

INPUT FORMAT:

* Line 1: The number of piles, N (1 <= N <= 10,000).

* Lines 2..1+N: Each line contains the number of hay bales in a single
pile (an integer in the range 1...10,000).

SAMPLE INPUT (file haybales.in):

4
2
10
7
1

INPUT DETAILS:

There are 4 piles, of heights 2, 10, 7, and 1.

OUTPUT FORMAT:

* Line 1: An integer giving the minimum number of hay bales that need
to be moved to restore the piles to having equal heights.

SAMPLE OUTPUT (file haybales.out):

7

OUTPUT DETAILS:

By moving 7 hay bales (3 from pile 2 to pile 1, 2 from pile 2 to pile 4, 2
from pile 3 to pile 4), we can make all piles have height 5.

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

Problem 2: Cow Photography (Bronze) [Brian Dean, 2011]

The cows are in a particularly mischievous mood today!  All Farmer John
wants to do is take a photograph of the cows standing in a line, but they
keep moving right before he has a chance to snap the picture.

Specifically, FJ's N (1 <= N <= 20,000) cows are tagged with ID numbers
1...N.  FJ wants to take a picture of the cows standing in a line in a
very specific ordering, represented by the contents of an array A[1...N],
where A[j] gives the ID number of the jth cow in the ordering.  He arranges
the cows in this order, but just before he can press the button on his
camera to snap the picture, up to one cow moves to a new position in the
lineup. More precisely, either no cows move, or one cow vacates her current
position in the lineup and then re-inserts herself at a new position in the
lineup.  Frustrated but not deterred, FJ again arranges his cows according
to the ordering in A, but again, right before he can snap a picture, up to
one cow (different from the first) moves to a new position in the lineup.

The process above repeats for a total of five photographs before FJ gives
up.  Given the contents of each photograph, see if you can reconstruct the
original intended ordering A.  Each photograph shows an ordering of the
cows in which up to one cow has moved to a new location, starting from the
initial ordering in A.  Moreover, if a cow opts to move herself to a new
location in one of the photographs, then she does not actively move in any
of the other photographs (although she can end up at a different position
due to other cows moving, of course).

PROBLEM NAME: photo

INPUT FORMAT:

* Line 1: The number of cows, N (1 <= N <= 20,000).

* Lines 2..5N+1: The next 5N lines describe five orderings, each one a
block of N contiguous lines.  Each line contains the ID of a
cow, an integer in the range 1..N.

SAMPLE INPUT (file photo.in):

5
1
2
3
4
5
2
1
3
4
5
3
1
2
4
5
4
1
2
3
5
5
1
2
3
4

INPUT DETAILS:

There are 5 cows, with IDs 1, 2, 3, 4, and 5.  In each of the 5
photos, a different cow moves to the front of the line (although the cows
could have moved anywhere else, if they wanted).

OUTPUT FORMAT:

* Lines 1..N: The intended ordering A, one ID per line.

SAMPLE OUTPUT (file photo.out):

1
2
3
4
5

OUTPUT DETAILS:

The correct original ordering A[1..5] is 1,2,3,4,5.

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

Problem 3: Escaping the Farm [Brian Dean and Kalki Seksaria, 2011]

The cows have decided on a daring plan to escape from the clutches of
Farmer John.  They have managed to procure a small inflatable raft, and
during the cover of night, a group of cows will board the raft and row
across the river bordering the farm.  The plan seems perfect, until the
cows realize that their small inflatable raft may not be able to hold
much weight!

The N cows (1 <= N <= 20) have weights w_1 ... w_N.  To figure out if a
group of cows is light enough to avoid sinking the raft, the cows add up
all of the weights in the group.  Unfortunately, cows are notoriously bad at
arithmetic, and if the addition of the weights of the cows in a group
causes any carries to occur (using standard base 10 addition), then the
cows give up and conclude that group must weigh too much to use the raft.
Any group whose weights can be added without any carries is assumed to be
light enough to fit on the raft.

believe can fit on the raft (that is, the largest group whose weights can
be added together with no carries).

PROBLEM NAME: escape

INPUT FORMAT:

* Line 1: The number of cows, N (1 <= N <= 20).

* Lines 2..N+1: Each line contains the weight of one cow, an integer
in the range 1...100,000,000.

SAMPLE INPUT (file escape.in):

5
522
6
84
7311
19

INPUT DETAILS:

There are 5 cows, with weights 522, 6, 84, 7311, and 19.

OUTPUT FORMAT:

* Line 1: The number of cows in the largest group whose weights can be

SAMPLE OUTPUT (file escape.out):

3

OUTPUT DETAILS:

The three weights 522, 6, and 7311, can be added together with no carries:

522
6
+ 7311
------
7839

**********************************************************************```
```
page revision: 0, last edited: 18 Dec 2011 19:03