Usaco Nov10 Gold

Part of USACO Nov10

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

Problem 1: Cow Photographs [Travis, 2010]

Farmer John wants to take a picture of his entire herd of N (1 <=
N <= 100,000) cows conveniently numbered 1..N so he can show off
to his friends.

On picture day, the cows run to form a single line in some arbitrary
order with position i containing cow c_i (1 <= c_i <= N). Farmer
John has his own ideas about how the cows should line up.

FJ thinks cow i may stand only to the left of cow i+1 (for all i,
1 <= i <= N-1) and that cow N may only stand to the left of Cow 1.
Of course, no cow will stand to the left of the first (leftmost)
cow in the line.

The cows are hungry for the promised post-photo dinner, so Farmer
John wants to take the picture as quickly as possible. Cows are not
great at following directions, so he will only choose a pair of
adjacent cows and have them switch places once per minute. How
quickly is Farmer John able to get them into some acceptable order?

Consider a set of 5 cows whose initial lineup looks like this:

Left           Right
3  5  4  2  1

He can first swap the second pair of cows:

3  4  5  2 1

and then swap the rightmost pair:

3  4  5  1  2

to yield an acceptable lineup that required but two minutes of cow
swapping.

PROBLEM NAME: cowpic

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains the number of the i-th cow in line:
c_i

SAMPLE INPUT (file cowpic.in):

5
3
5
4
2
1

OUTPUT FORMAT:

* Line 1: The minimum amount of time, in minutes, that it takes Farmer
John to get the cows into some appropriate order.

SAMPLE OUTPUT (file cowpic.out):

2

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

Problem 2: Buying Feed [Tom Conerly, 2009]

Farmer John needs to travel to town to pick up K (1 <= K <= 10,000)
pounds of feed. Driving a mile with K pounds of feed costs FJ K*K
cents; driving D miles with K pounds of feed in his truck costs FJ
D*K*K cents.

FJ can purchase feed from any of N (1 <= N <= 500) stores (conveniently
numbered 1..N) that sell feed. Each store is located on a segment
of the X axis whose length is E (1 <= E <= 500) miles. Store i is
at location X_i (0 < X_i < E) on the number line and can sell FJ
as much as F_i (1 <= F_i <= 10,000) pounds of feed at a cost of C_i
(1 <= C_i <= 10,000,000) cents per pound. Surprisingly, a given
point on the X axis might have more than one store.

FJ starts driving at location 0 on this number line and can drive
only in the positive direction, ultimately arriving at location E
with at least K pounds of feed. He can stop at any of the feed
stores along the way and buy any amount of feed up to the the store's
limit.

What is the minimum amount FJ must pay to buy and transport the K
pounds of feed? FJ knows he can purchase enough feed.

Consider this example where FJ needs two pounds of feed which he
must purchase from some of the three stores at locations 1, 3, and
4 on a number line whose range is 0..5:

0   1   2   3   4   5  X
+---|---+---|---|---+
1       1   1      Available pounds of feed
1       2   2      Cents per pound

It is most economical for FJ to buy one pound of feed from both the
second and third stores. He must pay two cents to buy each pound
of feed for a total cost of 4. FJ's driving from location 0 to
location 3 costs nothing, since he is carrying no feed. When FJ
travels from 3 to 4 he moves 1 mile with 1 pound of feed, so he
must pay 1*1*1 = 1 cents.

When FJ travels from 4 to 5 he moves one mile with 2 pounds of feed,
so he must pay 1*2*2 = 4 cents.

His feed cost is 2 + 2 cents; his travel cost is 1 + 4 cents. The
total cost is 2 + 2 + 1 + 4 = 9 cents.

TIME LIMIT: 2.5 seconds

PROBLEM NAME: feed

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains three space-separated integers: X_i,
F_i, and C_i

SAMPLE INPUT (file feed.in):

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

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum cost for FJ to buy and
transport the feed

SAMPLE OUTPUT (file feed.out):

9

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

Problem 3: Visiting Cows [Neal Wu, 2008]

After many weeks of hard work, Bessie is finally getting a vacation!
Being the most social cow in the herd, she wishes to visit her N
(1 <= N <= 50,000) cow friends conveniently numbered 1..N. The cows
have set up quite an unusual road network with exactly N-1 roads
connecting pairs of cows C1 and C2 (1 <= C1 <= N; 1 <= C2 <= N; C1
!= C2) in such a way that there exists a unique path of roads between
any two cows.

FJ wants Bessie to come back to the farm soon; thus, he has instructed
Bessie that if two cows are directly connected by a road, she may
not visit them both. Of course, Bessie would like her vacation to
be as long as possible, so she would like to determine the maximum
number of cows she can visit.

PROBLEM NAME: vacation

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N: Each line describes a single road with two
space-separated integers: C1 and C2

SAMPLE INPUT (file vacation.in):

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

INPUT DETAILS:

Bessie knows 7 cows. Cows 6 and 2 are directly connected by a road,
as are cows 3 and 4, cows 2 and 3, etc. The illustration below depicts the

1--2--3--4
|
5--6--7

OUTPUT FORMAT:

* Line 1: A single integer representing the maximum number of cows
that Bessie can visit.

SAMPLE OUTPUT (file vacation.out):

4

OUTPUT DETAILS:

Bessie can visit four cows. The best combinations include two cows
on the top row and two on the bottom. She can't visit cow 6 since
that would preclude visiting cows 5 and 7; thus she visits 5 and
7. She can also visit two cows on the top row: {1,3}, {1,4}, or
{2,4}.

**********************************************************************
page revision: 1, last edited: 08 Jul 2011 02:31