Usaco Jan10 Gold

Part of USACO Jan10

**********************************************************************
                           GOLD PROBLEMS
**********************************************************************
                  Three problems numbered 1 through 3
**********************************************************************

Problem 1: Taking Turns [John Pardon, 2009]

Farmer John has invented a new way of feeding his cows. He lays out
N (1 <= N <= 700,000) hay bales conveniently numbered 1..N in a
long line in the barn. Hay bale i has weight W_i (1 <= W_i <=
2,000,000,000). A sequence of six weights might look something like:

        17 5 9 10 3 8 

A pair of cows named Bessie and Dessie walks down this line after
examining all the haybales to learn their weights. Bessie is the
first chooser. They take turns picking haybales to eat as they walk
(once a haybale is skipped, they cannot return to it). For instance,
if cows Bessie and Dessie go down the line, a possible scenario is:

* Bessie picks the weight 17 haybale
* Dessie skips the weight 5 haybale and picks the weight 9 haybale
* Bessie picks the weight 10 haybale
* Dessie skips the weight 3 haybale and picks the weight 8 haybale

Diagrammatically:

Bessie   |      |
        17 5 9 10 3 8 
Dessie       |      |

This scenario only shows a single skipped bale; either cow can skip
as many as she pleases when it's her turn.

Each cow wishes to maximize the total weight of hay she herself
consumes (and each knows that the other cow has this goal).
Furthermore, a cow will choose to eat the first bale of hay that
maximimizes her total weight consumed.

Given a sequence of hay weights, determine the amount of hay that
a pair of cows will eat as they go down the line of hay.

PROBLEM NAME: hayturn

INPUT FORMAT:

* Line 1: A single integer: N

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

SAMPLE INPUT (file hayturn.in):

6
17
5
9
10
3
8

OUTPUT FORMAT:

* Line 1: Two space-separated integers, the total weight of hay
        consumed by Bessie and Dessie respectively

SAMPLE OUTPUT (file hayturn.out):

27 17

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

Problem 2: Shipping Around an Island [John Pardon, 2009]

Farmer John decided to start his own cruise ship line! He has but
one ship, but is hoping for big growth. He recently acquired a map
of the area of ocean where his cruise ship will operate. It looks
something like the diagram below, with height H (3 <= H <= 1000)
and width W (3 <= W <= 1000).

       ...................
       ...................
       .....A.............
       .....A..x..........
       ..x..A.....AAAA....
       .....A.....A..A....
       .....AAAAAAAA.A....
       ........A.....A....
       .xx...AAA...x.A....
       ......A............
       ...AAAAAAAAAAAAA...
       ...................

In this map, '.' denotes water; 'A' is an element of the main island;
and 'x' are other islands.

Farmer John has decided his cruise ship will loop around the main
island. However, due to trade restrictions, the path his ship takes
is NOT allowed to go around any OTHER islands. For instance, the
following path of length 50 is not allowed because it encloses the
island denoted by 'x'.

       ...................
       ....+--+...........
       ....|A.|...........
       ....|A.|x.+-----+..
       ..x.|A.+--+AAAA.|..
       ....|A.....A..A.|..
       ....|AAAAAAAA.A.|..
       ....|...A.....A.|..
       .xx.|.AAA...x.A.|..    <--- route circumnavigates 'x' -- illegal!
       ..+-+.A.........|..
       ..|AAAAAAAAAAAAA|..
       ..+-------------+..

Given a map, help Farmer John determine the shortest path his cruise
ship can take to go around the main island without going around any
other islands.

Two cells are considered connected if they lie vertically or
horizontally across from one another (not diagonally). It is
guaranteed that the main island is connected and that a solution
exists.

Note that FJ's path may visit the same square more than once, for
instance there are three squares that are visited more than once
in FJ's optimal path (of length 62) for the example:

       ...................
       ....+--+...........
       ....|A.|...........
       ....|A.|x.+----+...
       ..x.|A.+--+AAAA|...
       ....|A.....A..A|...
       ....|AAAAAAAA.A|...
       ....|...A..+-+A|...
       .xx.|.AAA..|x|A|...
       ..+-+.A....+-+-++..
       ..|AAAAAAAAAAAAA|..
       ..+-------------+..

The above diagram is somewhat unclear because of the path overlapping
itself.  Drawn in two stages, FJ's optimal path is:

       ...................            ...................
       ...................            ....+--+...........
       .....A.............            ....|A.|...........
       .....A..x..........            ....|A.|x.+----+...
       ..x..A.....AAAA....            ..x.|A.+--+AAAA|...
       .....A.....A..A....  and then  ....|A.....A..A|...
       .....AAAAAAAA.A....            ....|AAAAAAAA.A|...
       ....V...A..+>.A....            ....V...A...>+A|...
       .xx.|.AAA..|x.A....            .xx...AAA...x|A|...
       ..+-+.A....+----+..            .....A.......+-+...
       ..|AAAAAAAAAAAAA|..            ...AAAAAAAAAAAAA...
       ..+-------------+..            ...................

PROBLEM NAME: island

INPUT FORMAT:

* Line 1: Two space-separated integers: H and W

* Lines 2..H+1: Line i+1 contains contains W characters that are the
        elements of map row i (all '.' or 'x' or 'A')

SAMPLE INPUT (file island.in):

12 19
...................
...................
.....A.............
.....A..x..........
..x..A.....AAAA....
.....A.....A..A....
.....AAAAAAAA.A....
........A.....A....
.xx...AAA...x.A....
......A............
...AAAAAAAAAAAAA...
...................

OUTPUT FORMAT:

* Line 1: The minimum length of a path that Farmer John's cruise ship
        can take

SAMPLE OUTPUT (file island.out):

62

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

Problem 3: Cow Telephones [John Pardon, 2009]

The cows have set up a telephone network, which for the purposes
of this problem can be considered to be an unrooted tree of unspecified
degree with N (1 <= N <= 100,000) vertices conveniently numbered
1..N. Each vertex represents a telephone switchboard, and each edge
represents a telephone wire between two switchboards. Edge i is
specified by two integers A_i and B_i the are the two vertices
joined by edge i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i).

Some switchboards have only one telephone wire connecting them to
another switchboard; these are the leaves of the tree, each of which
is a telephone booth located in a cow field.

For two cows to communicate, their conversation passes along the
unique shortest path between the two vertices where the cows are
located. A switchboard can accomodate only up to K (1 <= K <= 10)
simultaneous conversations, and there can be at most one conversation
going through a given wire at any one time.

Given that there is a cow at each leaf of the tree, what is the
maximum number of pairs of cows that can simultaneously hold
conversations? A cow can, of course, participate in at most one
conversation.

Consider this six-node telephone tree with K=1:

       1   5          C1   C5
       |   |          ||   ||
       2---4   -->    |2---4|
       |   |          ||   ||
       3   6          C3   C6

There are four cows, located at vertices 1, 3, 5 and 6. If cow 1
talks to cow 3, and cow 5 talks to cow 6, then they do not exceed
the maximum number of conversations per switchboard, so for this
example the answer is 2 (for two pairs of cows talking simultaneously).

PROBLEM NAME: telephone

INPUT FORMAT:

* Line 1: Two space separated integers: N and K

* Lines 2..N: Line i+1 contains two space-separated integers: A_i and
        B_i

SAMPLE INPUT (file telephone.in):

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

OUTPUT FORMAT:

* Line 1: The number of pairs of cows that can simultaneously hold
        conversations

SAMPLE OUTPUT (file telephone.out):

2

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