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