Usaco Feb10 Silver

Part of USACO Feb10

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

Problem 6: Chocolate Buying [Brian Hamrick, 2010]

Bessie and the herd love chocolate so Farmer John is buying them some.

The Bovine Chocolate Store features N (1 <= N <= 100,000) kinds of
chocolate in essentially unlimited quantities.  Each type i of
chocolate has price P_i (1 <= P_i <= 10^18) per piece and there are
C_i (1 <= C_i <= 10^18) cows that want that type of chocolate.

Farmer John has a budget of B (1 <= B <= 10^18) that he can spend
on chocolates for the cows. What is the maximum number of cows that
he can satisfy?  All cows only want one type of chocolate, and will
be satisfied only by that type.

Consider an example where FJ has 50 to spend on 5 different types of chocolate.
A total of eleven cows have various chocolate preferences:

    Chocolate_Type    Per_Chocolate_Cost    Cows_preferring_this_type
          1                   5                      3
          2                   1                      1
          3                  10                      4
          4                   7                      2
          5                  60                      1

Obviously, FJ can't purchase chocolate type 5, since he doesn't
have enough money. Even if it cost only 50, it's a counterproductive
purchase since only one cow would be satisfied.

Looking at the chocolates start at the less expensive ones, he can
  * purchase 1 chocolate of type #2 for 1 x  1 leaving 50- 1=49, then
  * purchase 3 chocolate of type #1 for 3 x  5 leaving 49-15=34, then
  * purchase 2 chocolate of type #4 for 2 x  7 leaving 34-14=20, then
  * purchase 2 chocolate of type #3 for 2 x 10 leaving 20-20= 0.

He would thus satisfy 1 + 3 + 2 + 2 = 8 cows.

PROBLEM NAME: cbuying

INPUT FORMAT:

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

* Lines 2..N+1: Line i contains two space separated integers defining
        chocolate type i: P_i and C_i

SAMPLE INPUT (file cbuying.in):

5 50
5 3
1 1
10 4
7 2
60 1

OUTPUT FORMAT:

* Line 1: A single integer that is the maximum number of cows that
        Farmer John can satisfy

SAMPLE OUTPUT (file cbuying.out):

8

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

Problem 7: Chocolate Giving [Brian Hamrick, 2010]

Farmer John is distributing chocolates at the barn for Valentine's
day, and B (1 <= B <= 25,000) of his bulls have a special cow in
mind to receive a chocolate gift.

Each of the bulls and cows is grazing alone in one of the farm's N
(2*B <= N <= 50,000) pastures conveniently numbered 1..N and connected
by M (N-1 <= M <= 100,000) bidirectional cowpaths of various lengths.
Some pastures might be directly connected by more than one cowpath.
Cowpath i connects pastures R_i and S_i (1 <= R_i <= N; 1 <= S_i
<= N) and has length L_i (1 <= L_i <= 2,000).

Bull i resides in pasture P_i (1 <= P_i <= N) and wishes to give a
chocolate to the cow in pasture Q_i (1 <= Q_i <= N).

Help the bulls find the shortest path from their current pasture
to the barn (which is located at pasture 1) and then onward to the
pasture where their special cow is grazing. The barn connects, one
way or another (potentially via other cowpaths and pastures) to
every pasture.

As an example, consider a farm with 6 pastures, 6 paths, and 3 bulls
(in pastures 2, 3, and 5) who wish to bestow chocolates on their
love-objects:

                      *1  <-- Bull wants chocolates for pasture 1 cow
             [4]--3--[5]  <-- [5] is the pasture ID
            /  |
           /   |
          4    2          <-- 2 is the cowpath length
         /     |               between [3] and [4]
      [1]--1--[3]*6
     /   \    /
    9     3  2
   /       \/
 [6]      [2]*4

* The Bull in pasture 2 can travel distance 3 (two different ways)
  to get to the barn then travel distance 2+1 to pastures [3] and
  [4] to gift his chocolate. That's 6 altogether.

* The Bull in pasture 5 can travel to pasture 4 (distance 3), then
  pastures 3 and 1 (total: 3 + 2 + 1 = 6) to bestow his chocolate
  offer.

* The Bull in pasture 3 can travel distance 1 to pasture 1 and then
  take his chocolate 9 more to pasture 6, a total distance of 10.

PROBLEM NAME: cgiving

INPUT FORMAT:

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

* Lines 2..M+1: Line i+1 describes cowpath i with three
        space-separated integers: R_i, S_i, and L_i

* Lines M+2..M+B+1: Line M+i+1 contains two space separated integers:
        P_i and Q_i

SAMPLE INPUT (file cgiving.in):

6 7 3
1 2 3
5 4 3
3 1 1
6 1 9
3 4 2
1 4 4
3 2 2
2 4
5 1
3 6

OUTPUT FORMAT:

* Lines 1..B: Line i should contain a single integer, the smallest
        distance that the bull in pasture P_i must travel to get
        chocolates from the barn and then award them to the cow of his
        dreams in pasture Q_i

SAMPLE OUTPUT (file cgiving.out):

6
6
10

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

Problem 8: Chocolate Eating [Brian Hamrick, 2010]

Bessie has received N (1 <= N <= 50,000) chocolates from the bulls,
but doesn't want to eat them too quickly, so she wants to plan out
her chocolate eating schedule for the next D (1 <= D <= 50,000)
days in order to maximize her minimum happiness level over the set
of those days.

Bessie's happiness level is an integer that starts at 0 and halves
(rounding down if necessary) over night as she sleeps. However,
when she eats chocolate i, her happiness level increases by integer
H_i (1 <= H_i <= 1,000,000). If she eats chocolates on a day, her
happiness for that day is considered the happiness level after she
eats the chocolates. Bessie insists that she eat the chocolates in
the order that she received them.

If more than one optimal solution exists, print any one of them.

Consider a sequence of 5 chocolates to be eaten over a period of 5
days; they respectively bring happiness (10, 40, 13, 22, 7).

If Bessie eats the first chocolate (10 happiness) on the first day
and then waits to eat the others, her happiness level is 10 after
the first day.

Here is the complete schedule which turns out to maximize her minimum
happiness:

  Day  Wakeup happiness   Happiness from eating   Bedtime happiness
   1            0                10+40                  50
   2           25                 ---                   25
   3           12                  13                   25
   4           12                  22                   34 
   5           17                   7                   24

The minimum bedtime happiness is 24, which turns out to be the best
Bessie can do.

PROBLEM NAME: ceating

INPUT FORMAT:

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

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

SAMPLE INPUT (file ceating.in):

5 5
10
40
13
22
7

OUTPUT FORMAT:

* Line 1: A single integer, the highest Bessie's minimum happiness can
        be over the next D days

* Lines 2..N+1: Line i+1 contains an integer that is the day on which
        Bessie eats chocolate i

SAMPLE OUTPUT (file ceating.out):

24
1
1
3
4
5

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