Usaco Jan10 Silver

Part of USACO Jan10

``````**********************************************************************
SILVER PROBLEMS
**********************************************************************
Three problems numbered 6 through 8
**********************************************************************

Problem 6: Tea Time [Tom Conerly, 2009]

N (1 <= N <= 1000) cows, conveniently numbered 1..N all attend a
tea time every day. M (1 <= M <= 2,000) unique pairs of those cows
have already met before the first tea time. Pair i of these cows
who have met is specified by two differing integers A_i and B_i (1
<= A_i <= N; 1 <= B_i <= N). The input never indicates that cows
have met each other more than once.

At tea time, any cow i and cow j who have met a mutual friend cow
k will meet sometime during that tea time and thus expand their
circle of known cows.

Determine whether Q (1 <= Q <= 100) pairs of cows have met after
tea times are held for long enough that no new cow meetings are
occurring. Query j consists of a pair of different cows X_j and Y_j
(1 <= X_j <= N; 1 <= Y_j <= N).

For example, suppose that out of cows 1 through 5, we know that 2
has met 5, 2 has met 3, and 4 has met 5; see (a) below.

2---3           2---3            2---3
\              |\  |            |\ /|
1    \     -->  1  | \ |    -->  1  | X |
\            |  \|            |/ \|
4---5           4---5            4---5
(a)             (b)              (c)

In the first tea time, cow 2 meets cow 4, and cow 3 meets cow 5;
see (b) above. In the second tea time, cow 3 meets cow 4; see (c)
above.

PROBLEM NAME: ttime

INPUT FORMAT:

* Line 1: Three space-separated integers: N, M, and Q

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

* Lines M+2..M+Q+1: Line j+M+1 contains query j as two space-separated
integers: X_j and Y_j

SAMPLE INPUT (file ttime.in):

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

OUTPUT FORMAT:

* Lines 1..Q: Line j should be "Y" if the cows in the jth query have
met and "N" if they have not met.

SAMPLE OUTPUT (file ttime.out):

Y
Y
N

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

Problem 7: Buying Feed, II [Tom Conerly, 2009]

Farmer John needs to travel to town to pick up K (1 <= K <= 100)
pounds of feed. Driving D miles with K pounds of feed in his truck
costs D*K cents.

The county feed lot has N (1 <= N <= 100) stores (conveniently
numbered 1..N) that sell feed. Each store is located on a segment
of the X axis whose length is E (1 <= E <= 350). Store i is at
location X_i (0 < X_i < E) on the number line and can sell FJ as
much as F_i (1 <= F_i <= 100) pounds of feed at a cost of C_i (1
<= C_i <= 1,000,000) cents per pound. Amazingly, a given point on
the X axis might have more than one store.

FJ starts at location 0 on this number line and can drive only in
the positive direction, ultimately arriving at location E, with at
least K pounds of feed. He can stop at any of the feed stores along
the way and buy any amount of feed up to the the store's limit.

What is the minimum amount FJ has to pay to buy and transport the
K pounds of feed? FJ knows there is a solution.

Consider a sample where FJ needs two pounds of feed from three
stores (locations: 1, 3, and 4) on a number line whose range is
0..5:

0   1   2   3   4   5
+---|---+---|---|---+
1       1   1      Available pounds of feed
1       2   2      Cents per pound

It is best for FJ to buy one pound of feed from both the second and
third stores. He must pay two cents to buy each pound of feed for
a total cost of 4. When FJ travels from 3 to 4 he is moving 1 unit
of length and he has 1 pound of feed so he must pay 1*1 = 1 cents.

When FJ travels from 4 to 5 he is moving one unit and he has 2
pounds of feed so he must pay 1*2 = 2 cents.

The total cost is 4+1+2 = 7 cents.

PROBLEM NAME: feed2

INPUT FORMAT:

* Line 1: Three space-separated integers: K, E, and N

* Lines 2..N+1: Line i+1 contains three space-separated integers: X_i,
F_i, and C_i

SAMPLE INPUT (file feed2.in):

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

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum cost for FJ to buy and
transport the feed

SAMPLE OUTPUT (file feed2.out):

7

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

Problem 8: Cheese Towers [Tom Conerly, 2010]

Farmer John wants to save some blocks of his cows' delicious Wisconsin
cheese varieties in his cellar for the coming winter. He has room
for one tower of cheese in his cellar, and that tower's height can
be at most T (1 <= T <= 1,000). The cows have provided him with a
virtually unlimited number of blocks of each kind of N (1 <= N <=
100) different types of cheese (conveniently numbered 1..N). He'd
like to store (subject to the constraints of height) the most
valuable set of blocks he possibly can. The cows will sell the rest
to support the orphan calves association.

Each block of the i-th type of cheese has some value V_i (1 <= V_i
<= 1,000,000) and some height H_i (5 <= H_i <= T), which is always
a multiple of 5.

Cheese compresses. A block of cheese that has height greater than
or equal to K (1 <= K <= T) is considered "large" and will crush
any and all of the cheese blocks (even other large ones) located
below it in the tower. A crushed block of cheese doesn't lose any
value, but its height reduces to just 4/5 of its old height. Because
the height of a block of cheese is always a multiple of 5, the
height of a crushed block of cheese will always be an integer. A
block of cheese is either crushed or not crushed; having multiple
large blocks above it does not crush it more. Only tall blocks of
cheese crush other blocks; aggregate height of a tower does not
affect whether a block is crushed or not.

What is the total value of the best cheese tower FJ can construct?

Consider, for example, a cheese tower whose maximum height can be
53 to be build from three types of cheese blocks. Large blocks are
those that are greater than or equal to 25. Below is a chart of the
values and heights of the various cheese blocks he stacks:

Type    Value      Height
1      100         25
2       20          5
3       40         10

FJ constructs the following tower:

Type Height Value
top -> [1]   25    100
[2]    4     20   <- crushed by [1] above
[3]    8     40   <- crushed by [1] above
[3]    8     40   <- crushed by [1] above
bottom -> [3]    8     40   <- crushed by [1] above

The topmost cheese block is so large that the blocks below it are
crushed. The total height is:

25 + 4 + 8 + 8 + 8 = 53

The total height does not exceed 53 and thus is 'legal'. The total
value is:

100 + 20 + 40 + 40 + 40 = 240.

This is the best tower for this particular set of cheese blocks.

PROBLEM NAME: cheese

INPUT FORMAT:

* Line 1: Three space-separated integers: N, T, and K

* Lines 2..N+1: Line i+1 contains two space separated integers: V_i
and H_i

SAMPLE INPUT (file cheese.in):

3 53 25
100 25
20 5
40 10

OUTPUT FORMAT:

* Line 1: The value of the best tower FJ can build

SAMPLE OUTPUT (file cheese.out):

240

**********************************************************************```
```
page revision: 0, last edited: 15 Jan 2010 02:21