Usaco Mar11 Silver

Part of USACO Mar11

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

Problem 6: Meeting Place [Damon Doucet, 2011]

Bessie and Jonell are great friends. Since Farmer John scrambles
where the cows graze every day, they are sometimes quite far from
each other and can't talk.

The pastures and paths on FJ's farm form a 'tree' structure.  Each
pasture has exactly one distinct path to any other pasture, and
each pasture (except pasture #1, the 'root') also has a single
parent node.

Bessie and Jonell have decided that they will always meet at the
closest pasture that that is both an ancestor of Jonell's pasture
and of Bessie's pasture.

FJ created a map of his N (1 <= N <= 1,000) pastures (conveniently
numbered 1..N) that tells the parent P_i (1 <= P_i <= N) of each
pasture except pasture 1, which has no parent.

FJ has released his daily grazing schedule for the next M (1 <= M
<= 1,000) days, so Bessie and Jonell are deciding where they should
meet each day for gossip. On day k, Bessie is in pasture B_k (1 <=
B_k <= N) and Jonell is in pasture J_k (1 <= J_k <= N).

Given a map and schedule, help Bessie and Jonell find their meeting
places.

Consider, for example, the following farm layout:

Pasture      Parent Pasture
[1]           ---------    ----------------
/ | \              1              ---
/  |  \             2               1
[2] [3] [6]           3               1
/        | \          4               2
/         |  \         5               8
[4]        [8]  [9]      6               1
/   \          7               8
/     \         8               6
[5]     [7]       9               6

Here are the meeting places that Bessie and Jonell would choose
given a six day schedule of their initial grazing locations:

Bessie      Jonell       Meeting Place
--------    --------     ---------------
2           7               1
4           2               2
1           1               1
4           1               1
7           5               8
9           5               6

PROBLEM NAME: meetplace

INPUT FORMAT:

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

* Lines 2..N: Line i contains a single integer that describes the
parent of pasture i:  P_i

* Lines N+1..N+M: Line k+N describes Bessie and Jonell's respective
pastures with two space-separated integers: B_k and J_k

SAMPLE INPUT (file meetplace.in):

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

OUTPUT FORMAT:

* Lines 1..M: Line j contains the meeting place Bessie and Jonell
would use for line j+N of the input

SAMPLE OUTPUT (file meetplace.out):

1
2
3
1
8
6

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

Problem 7: Package Delivery [Damon Doucet, 2011]

Farmer John must deliver a package to Farmer Dan, and is preparing
to make his journey. To keep the peace, he gives a tasty treat to
every cow that he meets along his way and, of course, FJ is so
frugal that he would like to encounter as few cows as possible.

FJ has plotted a map of N (1 <= N <= 50,000) barns, connected by M
(1 <= M <= 50,000) bi-directional cow paths, each with C_i (0 <=
C_i <= 1,000) cows ambling along it. A cow path connects two distinct
barns, A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i). Two
barns may be directly connected by more than one path. He is currently
located at barn 1, and Farmer Dan is located at barn N.

Consider the following map:

[2]---
/ |    \
/1 |     \ 6
/   |      \
[1]   0|    --[3]
\   |   /     \2
4\  |  /4      [6]
\ | /       /1
[4]-----[5]
3

The best path for Farmer John to take is to go from 1 -> 2 -> 4 ->
5 -> 6, because it will cost him 1 + 0 + 3 + 1 = 5 treats.

Given FJ's map, what is the minimal number of treats that he should
bring with him, given that he will feed each distinct cow he meets
exactly one treat? He does not care about the length of his journey.

PROBLEM NAME: packdel

INPUT FORMAT:

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

* Lines 2..M+1: Three space-separated integers: A_i, B_i, and C_i

SAMPLE INPUT (file packdel.in):

6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4

OUTPUT FORMAT:

* Line 1: The minimum number of treats that FJ must bring

SAMPLE OUTPUT (file packdel.out):

5

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

Problem 8: Bovine Bridge Battle [Richard Ho, 2007]

Each of Farmer John's N (4 <= N <= 1,000) cows is patiently waiting
in the main pasture with cow i at point with integer coordinates
(X_i, Y_i) (-1,000,000,000 <= X_i <= 1,000,000,000; -1,000,000,000
<= Y_i <= 1,000,000,000).

The cows wish to form into groups of four in order to play Bridge,
their new favorite card game. Each group must satisfy an important
constraint: four cows are allowed to team up if and only if there
exists some point X somewhere in the plane (and not coincident with
any of the four points of the potential group of four) such that
rotating any of the group's cows 180 degrees about that point X
gives the position of some other cow in the group.

can form a Bridge group.

By way of example, suppose eight cows are standing at eight points:

|
f*
|             a = (-3, 1)    e = (-1, 1)
b*     |             b = (-2, 2)    f = ( 0, 3)
a      e  |             c = (-3, 0)    g = ( 2, 0)
*     *  |             d = (-2, 0)    h = ( 3, 0)
c  d     |     g  h
---------*--*-----+-----*--*---------
|

Then the three legal sets of four cows are {a, b, e, d} (they rotate
around point (-2, 1)), {b, c, e, f} (around the point (-1.5, 1.5)),
and {c, d, g, h} (around (0,0)).

The supplied locations of the cows given are all distinct, although
they are supplied in no particular order. Furthermore, the answer
will fit into a signed 32-bit integer.

PROBLEM NAME: rotsym

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: X_i
and Y_i

SAMPLE INPUT (file rotsym.in):

8
-3 0
-2 0
-1 1
0 3
2 0
-3 1
3 0
-2 2

OUTPUT FORMAT:

* Line 1: A single integer that is the number of sets of 4 cows that
form valid groups for bridge.

SAMPLE OUTPUT (file rotsym.out):

3

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