Usaco Nov10 Silver

Part of USACO Nov10

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

Problem 6: Banner [Nathan Pinsker, 2010]

Bessie is returning from a long trip abroad, and Farmer John wants
to erect a nice "Welcome Home" banner in her pasture for her arrival.
The banner will hang between two poles on a wire whose length is
in the range L1..L2 (1 <= L1 <= L2; L1 <= L2 <= 1,500).

The pasture's size is W x H (1 <= W <= 1,000; 1 <= H <= 1,000), and
Farmer John has installed a post at every point with integer
coordinates. Of these (W + 1) * (H + 1) points, Farmer John must
pick just two that will hold either end of the wire from which he
will hang the banner.

FJ wants no interference with his banner as it hangs and requires
that no post be directly under the tight wire he stretches between
the two chosen posts.

Farmer John needs your help to figure out how many possible ways
he can hang the banner. He knows the number is large and that a
32-bit integer might not be sufficient to compute the answer.

Consider the example pasture below, with W = 2 and H = 1:

       * * *
       * * *

The banner size is in the range 2..3. This pasture contains (2+1)
* (1+1) = 6 points and has (6 take 2) = (6*5)/(2*1) = 15 different
potential pairs of points between which the banner-holding wire
might stretch:

   (0,0)-(0,1)   (0,0)-(2,1)   (0,1)-(2,1)   (1,1)-(2,0)
   (0,0)-(1,0)   (0,1)-(1,0)   (1,0)-(1,1)   (1,1)-(2,1)
   (0,0)-(1,1)   (0,1)-(1,1)   (1,0)-(2,0)   (2,0)-(2,1)
   (0,0)-(2,0)   (0,1)-(2,0)   (1,0)-(2,1)

Of these pairs, only four have a length in the range 2..3:

                     Len                       Len
        (0,0)-(2,0) 2.00          (0,1)-(2,0) 2.24 
        (0,0)-(2,1) 2.24          (0,1)-(2,1) 2.00 

Of these four, the pairs (0,0)-(2,0) and (0,1)-(2,1) both have a
post directly on the line between the endpoints, and thus are
unsuitable.

So, just two pairs of points out of 15 are acceptable candidates for
hanging the banner wire.

PROBLEM NAME: banner

INPUT FORMAT:

* Line 1: Four space-separated integers: W, H, L1, and L2

SAMPLE INPUT (file banner.in):

2 1 2 3

OUTPUT FORMAT:

* Line 1: A single integer denoting the number of possible banners

SAMPLE OUTPUT (file banner.out):

2

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

Problem 7: Candy [Nathan Pinsker, 2010]

Farmer John knows that Bessie loves to eat candy. FJ has N (1 <= N
<= 40,000) candies that he wants to give Bessie over some number
of days. Each day, Farmer John gives Bessie a choice of how many
candies she chooses to eat that day by choosing the number from a
master list FJ supplies that has Nopt (1 <= Nopt <= 50) different options,
C_i (1 <= C_i <= N). She must take exactly C_i candies, no more,
no less.

Farmer John has also disclosed F (1 <= F <= 50) of his favorite
numbers, FN_i (1 <= FN_i <= N). Whenever the number of candies
remaining at the end of the day precisely matches one of these
favorite numbers, Bessie has the option to have him add exactly M
(1 <= M <= 100) more candies to the candy supply. Bessie might get
another option to add M candies several times if adding candies
creates another favorite number. In the best circumstances, Bessie
can obtain an infinite amount of candy!

When Bessie cannot choose some amount of candy to take (because
there is not enough), and the number of candies remaining is not
any of FJ's favorite numbers, she cannot have any more candy.

Unfortunately, Bessie cannot think ahead as far as she'd like to,
so she needs your help in order to eat as many candies as possible.

By way of example, consider this scenario:

    * Farmer John's basket initially contains 10 candies

    * Bessie can chose to eat either 3 or 5 candies each day

    * Farmer John will add 1 candy any time the remaining number
      of candies is 2 or 4

Bessie could use this set of choices to maximize the amount of candy
she can eat:

                  Initial      # Candies   Remaining     Bonus     Final
        Day      # Candies       Eaten      Candies     Candies   Candies

         1          10             3          7            0        7
         2           7             3          4            1        5
         3           5             3          2            1        3
         4           3             3          0            0        0

Total candies eaten = 3 + 3 + 3 + 3 = 12.

PROBLEM NAME: candy

INPUT FORMAT:

* Line 1: Four space-separated integers: N, Nopt, F, and M

* Lines 2..Nopt+1: Line i+1 contains a single integer: C_i

* Lines Nopt+2..Nopt+F+1: Line i+Nopt+1 contains a single integer:
        FN_i

SAMPLE INPUT (file candy.in):

10 2 2 1
3
5
4
2

OUTPUT FORMAT:

* Line 1: A single integer, denoting the maximum amount of candies
        Bessie can eat, or -1 if  Bessie can eat an infinite amount of
        candy.

SAMPLE OUTPUT (file candy.out):

12

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

Problem 8: Chocolate Milk [Nathan Pinsker, 2010]

Farmer John's milk production and shipping system is an intricate
one! He uses milking machines for his many cows to harvest the milk
that then flows into pipes.

Each of these pipes connects a milking machine to a joint, where
it might be joined by exactly one more pipe (the milk flowing through
both pipes merges). The milk then flows through additional pipes
(which all start and end at joints) until it reaches the long central
pipe connecting to the distribution room.

The milk then goes through a reverse process of splitting at various
joints until it is flows into milk tanks that are picked up and
taken to market.

Farmer John notices that there is at most one way for milk to travel
from one joint to any other joint. Furthermore, since Farmer John
is an efficient man by nature, he has made sure that milk will flow
through each and every pipe; in other words, no pipe is unneeded.

If we think of a milking machine, joint, or milk tank as a node,
there are N (2 <= N <= 100,000) nodes in total (and N-1 pipes
connecting them). The input describes each pipe as an ordered pair
of nodes, A_i (1 <= A_i <= N) and B_i (1 <= B_i <= N; A_i < B_i)
indicating milk flows from node A_i to node B_i. If there is no
pipe coming in to A_i, it is a milking machine. Likewise, if no
pipe goes out from B_i, it is a tank.

The demand of chocolate milk has skyrocketed in recent months, and
Farmer John wants to install a chocolate inserter at one of the
joints so he can create delicious chocolate milk for customers.

Being thrifty, Farmer John has only bought one chocolate inserter,
so he wants to place it at a joint through which all the milk passes.
He knows that such a joint exists.

Help Farmer John find all the possible places he can install the
chocolate inserter.  (Note that Farmer John cannot install the
chocolate inserter at the same location as a milking machine.)

As an example, consider a milking setup like this one:

           1 ----+
                 |
                 v
           2 --> 4 --> 6 ------------------> 7 --> 8
                       ^                     |
                       |                     |
           3 --> 5 ----+                     + --> 9

Visual inspection shows that the chocolate inserter can be installed
at either joint 6 or 7, as all milk flows through those joints.

PROBLEM NAME: chocmilk

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N: Line i+1 contains two space-separated integers that
        describe a pipe's connectivity: A_i and B_i

SAMPLE INPUT (file chocmilk.in):

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

OUTPUT FORMAT:

* Lines 1..??: Integers, one per line and in ascending order, each
        denoting a possible joint at which to install the chocolate
        inserter.

SAMPLE OUTPUT (file chocmilk.out):

6
7

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