Usaco Jan08 Gold

Part of USACO Jan08

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

Problem 1: Haybale Guessing [Brian Dean, 2003]

The cows, who always have an inferiority complex about their
intelligence, have a new guessing game to sharpen their brains.

A designated 'Hay Cow' hides behind the barn and creates N (1 <= N
<= 1,000,000) uniquely-sized stacks (conveniently numbered 1..N)
of hay bales, each with 1..1,000,000,000 bales of hay.

The other cows then ask the Hay Cow a series of Q (1 <= Q <= 25,000)
questions about the the stacks, all having the same form:

What is the smallest number of bales of any stack in the range
of stack numbers Ql..Qh (1 <= Ql <= N; Ql <= Qh <= N)?

The Hay Cow answers each of these queries with a single integer A
whose truthfulness is not guaranteed.

Help the other cows determine if the answers given by the Hay Cow

PROBLEM NAME: bales

INPUT FORMAT:

* Line 1: Two space-separated integers: N and Q

* Lines 2..Q+1: Each line contains three space-separated integers that
represent a single query and its reply: Ql, Qh, and A

SAMPLE INPUT (file bales.in):

20 4
1 10 7
5 19 7
3 12 8
11 15 12

INPUT DETAILS:

The minimum number of bales in stacks 1..10 is 7, the minimum number
of bales in stacks 5..19 is 7, the minimum number of bales in stacks
3..12 is 8, and the minimum number of bales in stacks 11..15 is 12.

OUTPUT FORMAT:

* Line 1: Print the single integer 0 if there are no inconsistencies
among the replies (i.e., if there exists a valid realization
of the hay stacks that agrees with all Q queries).  Otherwise,
print the index from 1..Q of the earliest query whose answer
is inconsistent with the answers to the queries before it.

SAMPLE OUTPUT (file bales.out):

3

OUTPUT DETAILS:

Query 3 ("3 12 8") is the first that is inconsistent with those
before it. From queries 1 and 2 and the fact that all hay stacks
have a distinct number of bales, we deduce that one of stacks 5..10
must contain exactly 7 bales.  However, this stack contradicts the

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

Problem 2: Artificial Lake [Matt McCutchen, 2006]

The oppressively hot summer days have raised the cows' clamoring
to its highest level. Farmer John has finally decided to build an
artificial lake. For his engineering studies, he is modeling the
lake as a two-dimensional landscape consisting of a contiguous
sequence of N soon-to-be-submerged levels (1 <= N <= 100,000)
conveniently numbered 1..N from left to right.

Each level i is described by two integers, its width W_i (1 <= W_i
<= 1,000) and height (like a relative elevation) H_i (1 <= H_i <=
1,000,000). The heights of FJ's levels are unique. An infinitely
tall barrier encloses the lake's model on the left and right. One
example lake profile is shown below.

*             *  :
*             *  :
*             *  8
*    ***      *  7
*    ***      *  6
*    ***      *  5
*    **********  4 <- height
*    **********  3
***************  2
***************  1
Level    |  1 |2|  3   |

In FJ's model, he starts filling his lake at sunrise by flowing
water into the bottom of the lowest elevation at a rate of 1 square
unit of water per minute. The water falls directly downward until
it hits something, and then it flows and spreads as room-temperature
water always does.  As in all good models, assume that falling and
flowing happen instantly. Determine the time at which each elevation's
becomes submerged by a single unit of water.

WATER              WATER OVERFLOWS
|                       |
* |          *      *     |      *      *            *
* V          *      *     V      *      *            *
*            *      *    ....    *      *~~~~~~~~~~~~*
*    **      *      *~~~~** :    *      *~~~~**~~~~~~*
*    **      *      *~~~~** :    *      *~~~~**~~~~~~*
*    **      *      *~~~~**~~~~~~*      *~~~~**~~~~~~*
*    *********      *~~~~*********      *~~~~*********
*~~~~*********      *~~~~*********      *~~~~*********
**************      **************      **************
**************      **************      **************

After 4 mins        After 26 mins       After 50 mins
Lvl 1 submerged     Lvl 3 submerged     Lvl 2 submerged

Warning: The answer will not always fit in 32 bits.

PROBLEM NAME: alake

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 describes level i with two space-separated
integers: W_i and H_i

SAMPLE INPUT (file alake.in):

3
4 2
2 7
6 4

INPUT DETAILS:

Three levels just as in the example above.  Water will fill the
first level because it is the lowest.

OUTPUT FORMAT:

* Lines 1..N: Line i contains a single integer that is the number of
minutes that since sunrise when level #i is covered by water
of height 1.

SAMPLE OUTPUT (file alake.out):

4
50
26

OUTPUT DETAILS:

As in the illustrations above.

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

Problem 3: Cell Phone Network [Jeffrey Wang, 2007]

Farmer John has decided to give each of his cows a cell phone in
hopes to encourage their social interaction. This, however, requires
him to set up cell phone towers on his N (1 <= N <= 10,000) pastures
(conveniently numbered 1..N) so they can all communicate.

Exactly N-1 pairs of pastures are adjacent, and for any two pastures
A and B (1 <= A <= N; 1 <= B <= N; A != B) there is a sequence of
adjacent pastures such that A is the first pasture in the sequence
and B is the last. Farmer John can only place cell phone towers in
the pastures, and each tower has enough range to provide service
to the pasture it is on and all pastures adjacent to the pasture
with the cell tower.

Help him determine the minimum number of towers he must install to
provide cell phone service to each pasture.

PROBLEM NAME: tower

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N: Each line specifies a pair of adjacent pastures with two
space-separated integers: A and B

SAMPLE INPUT (file tower.in):

5
1 3
5 2
4 3
3 5

INPUT DETAILS:

Farmer John has 5 pastures: pastures 1 and 3 are adjacent, as are pastures
5 and 2, pastures 4 and 3, and pastures 3 and 5. Geometrically, the
farm looks like this (or some similar configuration)
4  2
|  |
1--3--5

OUTPUT FORMAT:

* Line 1: A single integer indicating the minimum number of towers to
install

SAMPLE OUTPUT (file tower.out):

2

OUTPUT DETAILS:

The towers can be placed at pastures 2 and 3 or pastures 3 and 5.

**********************************************************************```
```
page revision: 1, last edited: 08 Jul 2011 02:43