Usaco Nov10 Bronze

Part of USACO Nov10

```
**********************************************************************
BRONZE PROBLEMS
**********************************************************************
Three problems numbered 11 through 13
**********************************************************************
Problem 11: Daisy Chains in the Field [Sherry Wu, 2010]
Farmer John let his N (1 <= N <= 250) cows conveniently numbered
1..N play in the field. The cows decided to connect with each other
using cow-ropes, creating M (1 <= M <= N*(N-1)/2) pairwise connections.
Of course, no two cows had more than one rope directly connecting
them. The input shows pairs of cows c1 and c2 that are connected
(1 <= c1 <= N; 1 <= c2 <= N; c1 != c2).
FJ instructed the cows to be part of a chain which contained cow
#1. Help FJ find any misbehaving cows by determining, in ascending
order, the numbers of the cows not connected by one or more ropes
to cow 1 (cow 1 is always connected to herself, of course). If there
are no misbehaving cows, output 0.
To show how this works, consider six cows with four connections:
1---2 4---5
\ |
\ | 6
\|
3
Visually, we can see that cows 4, 5, and 6 are not connected to cow 1.
PROBLEM NAME: daisy
INPUT FORMAT:
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 shows two cows connected by rope i with two
space-separated integers: c1 and c2
SAMPLE INPUT (file daisy.in):
6 4
1 3
2 3
1 2
4 5
OUTPUT FORMAT:
* Lines 1..???: Each line contains a single integer
SAMPLE OUTPUT (file daisy.out):
4
5
6
**********************************************************************
Problem 12: Race Results [Agika, 2007]
The herd has run its first marathon! The N (1 <= N <= 5,000) times
have been posted in the form of Hours (0 <= Hours <= 99), Minutes
(0 <= Minutes <= 59), and Seconds (0 <= Seconds <= 59). Bessie must
sort them (by Hours, Minutes, and Seconds) into ascending order,
smallest times first.
Consider a simple example with times from a smaller herd of just 3
cows (note that cows do not run 26.2 miles so very quickly):
11:20:20
11:15:12
14:20:14
The proper sorting result is:
11:15:12
11:20:20
14:20:14
PROBLEM NAME: marathon
INPUT FORMAT:
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains cow i's time as three
space-separated integers: Hours, Minutes, Seconds
SAMPLE INPUT (file marathon.in):
3
11 20 20
11 15 12
14 20 14
OUTPUT FORMAT:
* Lines 1..N: Each line contains a cow's time as three space-separated
integers
SAMPLE OUTPUT (file marathon.out):
11 15 12
11 20 20
14 20 14
**********************************************************************
Problem 13: Math Practice [Brian Marshal, 2007]
One lovely afternoon, Bessie's friend Heidi was helping Bessie
review for her upcoming math exam.
Heidi presents two integers A (0 <= A <= 45) and B (1 <= B <= 9)
to Bessie who must respond with an integer E in the range 1..62.
E is the smallest integer in that range that is strictly greater
than A and also has B as the first digit of 2 raised to the E-th
power. If there is no answer, Bessie responds with 0.
Help Bessie correctly answer all of Heidi's questions by calculating
her responses.
By way of example, consider A=1 and B=6. Bessie might generate a table
like this:
E 2^E First digit of 2^E
2 4 4
3 8 8
4 16 1
5 32 3
6 64 6 <-- matches B
Thus, E=6 is the proper answer.
NOTE: The value of 2^44 does not fit in a normal 32-bit integer.
PROBLEM NAME: mathprac
INPUT FORMAT:
* Line 1: Two space-separated integers: A and B
SAMPLE INPUT (file mathprac.in):
1 6
OUTPUT FORMAT:
* Line 1: A single integer E calculated as above
SAMPLE OUTPUT (file mathprac.out):
6
**********************************************************************
```

page revision: 1, last edited: 08 Jul 2011 02:32