Usaco Mar10 Gold

Part of USACO Mar10

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

Problem 1: Great Cow Gathering [Jeffrey Wang from a contest, 2010]

Bessie is planning the annual Great Cow Gathering for cows all
across the country and, of course, she would like to choose the
most convenient location for the gathering to take place.

Each cow lives in one of N (1 <= N <= 100,000) different barns
(conveniently numbered 1..N) which are connected by N-1 roads in
such a way that it is possible to get from any barn to any other
barn via the roads. Road i connects barns A_i and B_i (1 <= A_i <=
N; 1 <= B_i <= N) and has length L_i (1 <= L_i <= 1,000). The Great
Cow Gathering can be held at any one of these N barns. Moreover,
barn i has C_i (0 <= C_i <= 1,000) cows living in it.

When choosing the barn in which to hold the Cow Gathering, Bessie
wishes to maximize the convenience (which is to say minimize the
inconvenience) of the chosen location. The inconvenience of choosing
barn X for the gathering is the sum of the distances all of the
cows need to travel to reach barn X (i.e., if the distance from
barn i to barn X is 20, then the travel distance is C_i*20). Help
Bessie choose the most convenient location for the Great Cow
Gathering.

Consider a country with five barns with [various capacities] connected
by various roads of varying lengths. In this set of barns, neither
barn 3 nor barn 4 houses any cows.

      1     3     4     5
      @--1--@--3--@--3--@[2]
     [1]    |
            2
            |
            @[1]
            2

Bessie can hold the Gathering in any of five barns; here is the
table of inconveniences calculated for each possible location:

  Gather      ----- Inconvenience ------
  Location    B1  B2  B3  B4  B5   Total
     1         0   3   0   0  14    17
     2         3   0   0   0  16    19
     3         1   2   0   0  12    15
     4         4   5   0   0   6    15
     5         7   8   0   0   0    15

If Bessie holds the gathering in barn 1, then the inconveniences
from each barn are:
      Barn 1     0 -- no travel time there!
      Barn 2     3 -- total travel distance is 2+1=3  x 1 cow = 3
      Barn 3     0 -- no cows there!
      Barn 4     0 -- no cows there!
      Barn 5    14 -- total travel distance is 3+3+1=7 x 2 cows = 14
So the total inconvenience is 17.

The best possible convenience is 15, achievable at by holding the
Gathering at barns 3, 4, or 5.

PROBLEM NAME: gather

INPUT FORMAT:

* Line 1: A single integer: N

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

* Lines N+2..2*N: Line i+N+1 contains three integers: A_i, B_i, and
        L_i

SAMPLE INPUT (file gather.in):

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

OUTPUT FORMAT:

* Line 1: The minimum inconvenience possible

SAMPLE OUTPUT (file gather.out):

15

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

Problem 2: Barn Allocation [Jaehyun Park/Jeffrey Wang, 2010]

Farmer John recently opened up a new barn and is now accepting stall
allocation requests from the cows since some of the stalls have a
better view of the pastures.

The barn comprises N (1 <= N <= 100,000) stalls conveniently numbered
1..N; stall i has capacity C_i cows (1 <= C_i <= 100,000). Cow i
may request a contiguous interval of stalls (A_i, B_i) in which to
roam (1 <= A_i <= N; A_i <= B_i <= N), i.e., the cow would like to
wander among all the stalls in the range A_i..B_i (and the stalls
must always have the capacity for her to wander).

Given M (1 <= M <= 100,000) stall requests, determine the maximum
number of them that can be satisfied without exceeding stall
capacities.

Consider both a barn with 5 stalls that have the capacities shown
and a set cow requests:

Stall id:    1   2   3   4   5
           +---+---+---+---+---+
Capacity:  | 1 | 3 | 2 | 1 | 3 |  
           +---+---+---+---+---+
Cow 1       XXXXXXXXXXX             (1, 3)
Cow 2           XXXXXXXXXXXXXXX     (2, 5)
Cow 3           XXXXXXX             (2, 3)
Cow 4                   XXXXXXX     (4, 5)

FJ can't satisfy all four cows, since there are too many requests
for stalls 3 and 4.

Noting that Cow 2 requests an interval that includes stalls 3 and
4, we test the hypothesis that cows 1, 3, and 4 can have their
requested stalls. No capacity is exceeded, so the answer for this
set of data is 3 -- three cows (1, 3, and 4) can have their requests
satisfied.

MEMORY LIMIT: 32 MB

TIME LIMIT: 2 seconds

PROBLEM NAME: balloc

INPUT FORMAT:

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

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

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

SAMPLE INPUT (file balloc.in):

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

OUTPUT FORMAT:

* Line 1: The maximum number of requests that can be satisfied

SAMPLE OUTPUT (file balloc.out):

3

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

Problem 3: StarCowraft [Jaehyun Park/KOI 2007, 2010]

The beta version of StarCowraft II is ready! Farmer John and Bessie
are testing it, trying different strategies in one-on-one battles
against each other's armies. The goal in StarCowraft II is to defeat
your opponent's army in a battle.

Each player's army fights in a battle. An army comprises as many
as three different types of 'units' with respective strengths denoted
by constant positive real numbers unknown to the players: cattlebruisers
with strength S1, cow templars with strength S2, and ultracows with
strength S3. The only given bounding information is that no unit
is more than 100 times as strong as any another unit.

An army's total strength is the sum of the individual strengths of
each of its units. An army that has, among others units, 23
cattlebruisers would gain 23*S1 strength just from the cattlebruisers.

When two opposing armies fight in a battle, the army with a higher
total strength value wins.  If the armies have exactly equal strength
values, one of the players randomly wins.

Farmer John and Bessie played N (0 <= N <= 300) "test battles". In
the i-th test battle, FJ's army had J1_i cattlebruisers, J2_i cow
templars, and J3_i ultracows (0 <= J1_i + J2_i + J3_i <= 1,000).
Similarly, Bessie's army had B1_i cattlebruisers, B2_i cow templars,
and B3_i ultracows (0 <= B1_i + B2_i + B3_i <= 1,000). After their
armies fought against each other, FJ and Bessie recorded the winner
as a single 'victory letter' V_i: "J" if Farm John won the battle;
"B" if Bessie won.

Although these victory results are the only information that they
have, they hope to predict some of the results of additional battles
if they are given the unit compositions of two opposing armies. For
some battles, though, they know it might not be possible to determine
the winner with certainty.

Given the results of the N test battles that Farmer John and Bessie
already played, write a program that decides the winner (if possible)
for M (1 <= M <= 2,000) new battles.

The results reported for the test battles are correct; there exists
at least one set of strength values which are consistent with the
results.

For purposes of demonstrating the army strength evaluation functions,
consider these test battles fought in a game where we (but neither
FJ nor Bessie) know that S1=9.0, S2=7.0, and S3=4.0:

   ---- Farmer John ----    ------- Bessie ------    Battle
   J1  J2  J3 J_Strength    B1  B2  B3 B_Strength   Outcome
    6   5   4    105         5   4   7    101          J
    5   4   2     81         3   5   5     82          B
    9   0  10    121         8   2   7    114          J

These results connote the following deduced results for the reasons
shown:

   ---- Farmer John ----    ------- Bessie ------    Battle
   J1  J2  J3 J_Strength    B1  B2  B3 B_Strength   Outcome
    6   6   4    112         5   4   7    101          J
              FJ's army is even stronger than in test battle 1
    9   0  10    121         8   2   6    110          J
              Bessie's army is even weaker than in test battle 3

PROBLEM NAME: starc

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 describes a test battle with seven
        space-separated items -- a victory letter and six
        space-separated integer unit counts: V_i, J1_i, J2_i, J3_i,
        B1_i, B2_i, and B3_i

* Lines N+2..N+M+1: Line i+N+1 describes a "new battle" using six
        space-separated integers: J1_i, J2_i, J3_i, B1_i, B2_i, and
        B3_i

SAMPLE INPUT (file starc.in):

3 3
J 6 5 4 5 4 7
B 5 4 2 3 5 5
J 9 0 10 8 2 7
6 6 4 5 4 7
9 0 10 8 2 6
3 4 8 4 4 6

OUTPUT FORMAT:

* Lines 1..M: Line i contains the outcome of the i-th new battle: "J"
        if Farmer John definitely wins, "B" if Bessie definitely wins,
        and "U" (undecidable) if it is impossible to decide the winner
        with the given information.

SAMPLE OUTPUT (file starc.out):

J
J
U

OUTPUT DETAILS:

First two games correspond to the examples in the description. The
result of the last game cannot be determined with only the information
that Farmer John and Bessie currently have. Specifically, both S_1=9.0, 
S_2=7.0, S_3=4.0 and S_1=12.0, S_2=20.0, S_3=10.0 are consistent with the 
"test battles," but they give different results when plugged in the third 
"new battle."

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