Usaco Mar09 Gold

Part of USACO Mar09

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

Problem 1: Moon Mooing [Long Fan, 2008]

A full moon casts some sort of spell on the cows and, like their
cousins the wolves and coyotes, they bay at the moon -- mooing

Each 'moo' lasts a certain amount of time. A short 'moo' might last
time 1; a longer one might last time 24 or even 1,000,000,000 or
longer (cows can really moo when they want to). No 'moo' will last
more than or equal to 2^63.

It should come as no surprise that the cows have a pattern to their
moos.  Bessie will choose an integer c (1 <= c <= 100) that is the
initial length of a moo.

After Bessie moos for length c, the cows calculate times for
subsequent moos. They apply two formulae to each moo time to yield
even more moo times. The two formulae are:
f1(c)=a1*c/d1+b1 (integer divide, of course) and
f2(c)=a2*c/d2+b2.

They then successively use the two new times created by evaluating
f1(c) and f2(c) to create even more mooing times. They keep a sorted
list of all the possible mooing times (discarding duplicates).

They are allowed to moo a total of N times (1 <= N <= 4,000,000).
Please determine the length of the longest moo before they must
quit.

The constants in the formulae have these constraints: 1 <= d1 < a1;
d1 < a1 <= 20; 0 <= b1 <= 20; 1 <= d2 < a2; d2 < a2 <= 20; 0 <= b2
<= 20.

Consider an example where c=3 and N=10. The constants are:
a1=4    b1=3     d1=3
a2=17   b2=8     d2=2

The first mooing time is 3, given by the value of c. The total list
of mooing times is:
1. c=3             ->  3       6. f2(3)=17*3/2+8  -> 33
2. f1(3)=4*3/3+3   ->  7       7. f1(28)=4*28/3+3 -> 40
3. f1(7)=4*7/3+3   -> 12       8. f1(33)=4*33/3+3 -> 47
4. f1(12)=4*12/3+3 -> 19       9. f1(40)=4*40/3+3 -> 56
5. f1(19)=4*19/3+3 -> 28      10. f1(47)=4*47/3+3 -> 65

The tenth time is 65, which would be the proper answer for this set
of inputs.

Partial feedback will be provided on the first 50 submissions.

MEMORY LIMIT: 64MB

PROBLEM NAME: baying

INPUT FORMAT:

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

* Line 2: Three space-separated integers: a1, b1, and d1

* Line 3: Three space-separated integers: a2, b2, and d2

SAMPLE INPUT (file baying.in):

3 10
4 3 3
17 8 2

OUTPUT FORMAT:

* Line 1: A single line which contains a single integer which is the
length of the Nth moo

SAMPLE OUTPUT (file baying.out):

65

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

Problem 2: Cleaning Up [Paul Christiano, 2007]

In the good old days, Farmer John served a boring cuisine comprising
but a single type of cow food to his N (1 <= N <= 40000) prize dairy
cows. Times change. Today he serves the herd a total of M (1 <= M
<= N) different types of food (conveniently numbered 1..M).

The cows are picky. Cow i has a single food preference P_i (1 <=
P_i <= M) and will eat only that favorite food.

Each day at feeding time FJ converts the barn into a tastefully lit
cafeteria. The cows line up outside to enter the cafeteria in order
of their previously-mentioned convenient index number.

Unfortunately, with so many types of food, cleaning up afterwards
is very time-consuming. If Farmer John is serving K different types
of food, it takes him K*K units of time to clean the barn.

To save time, FJ serves the cows in contiguous groups from the line.
After each group, he cleans up the barn and sets out the food for
the next group (of course, he only sets out food that cows in the
any given group will eat). Determine the minimum amount of total
time FJ must spend cleaning the barn. Each group consists of the
next contiguous group of cows from the line; each cow belongs to
exactly one group; and the barn must be cleaned up after every
group, including the last one.

PROBLEM NAME: cleanup

INPUT FORMAT:

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

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

SAMPLE INPUT (file cleanup.in):

13 4
1
2
1
3
2
2
3
4
3
4
3
1
4

INPUT DETAILS:

There are four types of food and thirteen cows in line. The first
cow prefers type 1, the second type 2, the third type 1, etc.

OUTPUT FORMAT:

* Line 1: A single integer: the minimum amount of time FJ must spend
cleaning the  barn.

SAMPLE OUTPUT (file cleanup.out):

11

OUTPUT DETAILS:

The first four groups contain one cow each. The fifth group contains
two cows who prefer food #2 (requiring one unit of time). The sixth
group contains cows preferring foods 3, 4, 3, 4, 3 (and requires
four units of time to clean). The last two groups contain one cow
each. The total time is 11.

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

Problem 3: Earthquake Damage 2 [Hal Burch, Richard Peng, 2008]

Wisconsin has had an earthquake that has struck Farmer John's farm!
The earthquake has damaged some of the pastures so that they are
unpassable. Remarkably, none of the cowpaths was damaged.

As usual, the farm is modeled as a set of P (1 <= P <= 3,000)
pastures conveniently numbered 1..P which are connected by a set
of C (1 <= C <= 20,000) non-directional cowpaths conveniently
numbered 1..C. Cowpath i connects pastures a_i and b_i (1 <= a_i
<= P; 1 <= b_i <= P). Cowpaths might connect a_i to itself or perhaps
might connect two pastures more than once.  The barn is located in
pasture 1.

A total of N (1 <= N <= P) cows (in different pastures) sequentially
contacts Farmer John via moobile phone with an integer message
report_j (2 <= report_j <= P) that indicates that pasture report_j
is undamaged but that the calling cow is unable to return to the
barn from pasture report_j because she could not find a path that
does not go through damaged pastures.

After all the cows report in, determine the minimum number of
pastures that are damaged.

PROBLEM NAME: damage2

INPUT FORMAT:

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

* Lines 2..C+1: Line i+1 describes cowpath i with two integers: a_i
and b_i

* Lines C+2..C+N+1: Line C+1+j contains a single integer: report_j

SAMPLE INPUT (file damage2.in):

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

OUTPUT FORMAT:

* Line 1: One number, the minimum number of damaged pastures.

SAMPLE OUTPUT (file damage2.out):

1

OUTPUT DETAILS:

Only pasture 2 being damaged gives such a scenario.

**********************************************************************```
```
page revision: 0, last edited: 06 Jun 2009 21:39