Usaco Jan08 Silver

Part of USACO Jan08

                           SILVER PROBLEMS
                  Three problems numbered 6 through 8

Problem 6: Cow Contest [Neal Wu, 2007]

N (1 <= N <= 100) cows, conveniently numbered 1..N, are participating
in a programming contest. As we all know, some cows code better
than others. Each cow has a certain constant skill rating that is
unique among the competitors.

The contest is conducted in several head-to-head rounds, each between
two cows. If cow A has a greater skill level than cow B (1 <= A <=
N; 1 <= B <= N; A != B), then cow A will always beat cow B.

Farmer John is trying to rank the cows by skill level. Given a list
the results of M (1 <= M <= 4,500) two-cow rounds, determine the
number of cows whose ranks can be precisely determined from the
results. It is guaranteed that the results of the rounds will not
be contradictory.



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

* Lines 2..M+1: Each line contains two space-separated integers that
        describe the competitors and results (the first integer, A, is
        the winner) of a single round of competition: A and B


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


* Line 1: A single integer representing the number of cows whose ranks
        can be determined

SAMPLE OUTPUT (file contest.out):



Cow 2 loses to cows 1, 3, and 4. Thus, cow 2 is no better than any
of the cows 1, 3, and 4. Cow 5 loses to cow 2, so cow 2 is better
than cow 5.  Thus, cow 2 must be fourth, and cow 5 must be fifth.
The ranks of the other cows cannot be determined.


Problem 7: Running [Neal Wu, 2007]

The cows are trying to become better athletes, so Bessie is running
on a track for exactly N (1 <= N <= 10,000) minutes. During each
minute, she can choose to either run or rest for the whole minute.

The ultimate distance Bessie runs, though, depends on her 'exhaustion
factor', which starts at 0. When she chooses to run in minute i,
she will run exactly a distance of D_i (1 <= D_i <= 1,000) and her
exhaustion factor will increase by 1 -- but must never be allowed
to exceed M (1 <= M <= 500).  If she chooses to rest, her exhaustion
factor will decrease by 1 for each minute she rests. She cannot
commence running again until her exhaustion factor reaches 0. At
that point, she can choose to run or rest.

At the end of the N minute workout, Bessie's exaustion factor must
be exactly 0, or she will not have enough energy left for the rest
of the day.

Find the maximal distance Bessie can run.



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

* Lines 2..N+1: Line i+1 contains the single integer: D_i


5 2


* Line 1: A single integer representing the largest distance Bessie
        can run while satisfying the conditions.

SAMPLE OUTPUT (file cowrun.out):



Bessie runs during the first minute (distance=5), rests during the
second minute, runs for the third (distance=4), and rests for the
fourth and fifth. Note that Bessie cannot run on the fifth minute
because she would not end with a rest factor of 0.


Problem 8: Telephone Lines [Paul Christiano, 2007]

Farmer John wants to set up a telephone line at his farm. Unfortunately,
the phone company is uncooperative, so he needs to pay for some of
the cables required to connect his farm to the phone system.

There are N (1 <= N <= 1,000) forlorn telephone poles conveniently
numbered 1..N that are scattered around Farmer John's property; no
cables connect any them.  A total of P (1 <= P <= 10,000) pairs of
poles can be connected by a cable; the rest are too far apart.

The i-th cable can connect the two distinct poles A_i and B_i, with
length L_i (1 <= L_i <= 1,000,000) units if used. The input data
set never names any {A_i,B_i} pair more than once. Pole 1 is already
connected to the phone system, and pole N is at the farm. Poles 1
and N need to be connected by a path of cables; the rest of the
poles might be used or might not be used.

As it turns out, the phone company is willing to provide Farmer
John with K (0 <= K < N) lengths of cable for free. Beyond that he
will have to pay a price equal to the length of the longest remaining
cable he requires (each pair of poles is connected with a separate
cable), or 0 if he does not need any additional cables.

Determine the minimum amount that Farmer John must pay.

PROBLEM NAME: phoneline


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

* Lines 2..P+1: Line i+1 contains the three space-separated integers:
        A_i, B_i, and L_i


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


There are 5 poles. Pole 1 cannot be connected directly to poles 4 or 5.
Pole 5 cannot be connected directly to poles 1 or 3. All other pairs can be
connected. The phone company will provide one free cable.


* Line 1: A single integer, the minimum amount Farmer John can pay. If
        it is impossible to connect the farm to the phone company,
        print -1.

SAMPLE OUTPUT (file phoneline.out):



If pole 1 is connected to pole 3, pole 3 to pole 2, and pole 2 to pole 5
then Farmer John requires cables of length 4, 3, and 9. The phone company
will provide the cable of length 9, so the longest cable needed has length 4.

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