http://ace.delos.com/ioigate
USACO 2006 Qualification Round 试题：
如果我有空，我会写题解的（其实这几道题都恒简单拉），也欢迎大家来探讨
**********************************************************************
GOLD PROBLEMS
**********************************************************************
Six problems numbered 1 through 6
**********************************************************************
Problem 1: Another Cow Number Game [Traditional, 2006]
The cows are playing a silly number game again. Bessie is tired of
losing and wants you to help her cheat. In this game, a cow supplies
a number N (1 <= N <= 1,000,000). This is move 0. If N is odd, then
the number N is multiplied by 3 and incremented by 1. If N is even,
the number N is divided by 2. Each time the number is multiplied or
divided, the score increases by one point. The game ends -- and the
score is finalized -- when N becomes 1.
Here's an example with N starting at 5:
N Next Value Comment Score
5 16 3*5+1 1
16 8 16/2 2
8 4 8/2 3
4 2 4/2 4
2 1 2/2 5
The final score is 5.
PROBLEM NAME: acng
INPUT FORMAT:
* Line 1: A single integer, N
SAMPLE INPUT (file acng.in):
112
OUTPUT FORMAT:
* Line 1: A single integer that is the score for this game when
starting at N
SAMPLE OUTPUT (file acng.out):
20
**********************************************************************
Problem 2: Guess My Number [Traditional, 2006]
--------> Our grader will not grade this problem in JAVA!
--------> This problem will be fixed early Saturday, with luck.
The cows are playing "High-Low", the guess-a-number game. The leader
thinks of a number in the range 1..N (10 <= N <= 1,000,000); others
try to guess it. Each time a guess is given, the leader tells the
guesser if her guess is high, low, or correct. Write a program to
play this game against a robotic leader.
This is an interactive task; your program will interact with a
grading program. Read all your input from the standard input (also
known as the console). Write all your output to standard output
(just like writing to the screen/console). See below for more special
instructions.
First, read N, then make your guess by printing it to the console.
Read back a reply that is a line with 'H', 'L', or 'OK'. Your program
should exit after receiving the 'OK'.
Your score depends on how quickly you guess the number. Optimal
solutions receive full credit; others receive less.
A typical exchange might go like this (the secret number is 7):
-> 10 [guess in the range 1..10]
<- 4 [You guess 4]
-> L [Guess is low]
<- 6 [You guess 6]
-> L [Guess is low]
<- 8 [You guess 8]
-> H [Guess is high]
<- 7 [You guess 7]
-> OK [Guess is correct!]
You must ensure that your program's output is not buffered inside your
program; you must 'flush' your output.
If you're using stdio.h, include the line
setbuf(stdout, 0);
near the top of your program.
If you're using C++ style I/O, flush each output line like this:
cout << line << "\n" << flush;
For Pascal, add the following statement after each writeln statement:
flush(stdout);
For Java, add the following after each output statement:
System.out.flush();
If your program 'times out' after you wrote a reply, it probably
is not properly flushing the output.
PROBLEM NAME: guess
INPUT FORMAT:
* Line 1: A single integer N
* Lines 2..?: Each line contains a short reply as detailed above.
SAMPLE INPUT (standard input):
10
...[See details above]...
OUTPUT FORMAT:
* Lines 1..??: Each output line is a guess as detailed above.
SAMPLE OUTPUT (standard output):
...[see above]...
**********************************************************************
Problem 3: Cows on Skates [Rob Kolstad, 2006]
Finally, after years of pleading, Farmer John relented and has purchased
roller skates for the entire herd of cows. A large bit of the farm is just
great for roller-skating, but several parcels have just way too many rocks
and are unpassable on skates.
The farm is conveniently reprssented as a grid of squares with R (1 <= R
<= 113) rows and C (1 <= C <= 77) columns. Bessie finds herself at square
(1,1) near feeding time and wants to get back to barn which is located at
square (R,C). She knows there is at least one way to do so by skating to
adjacent squares (but not on the diagonal) that don't contain rocks. Find
and display any path that Bessie can follow to get to the barn.
Consider R=5, C=8 farm layout below on the left, where '*' means "too many
rocks here". The right-hand map shows one possible path Bessie might use
to get to the barn in the lower right corner:
12345678 12345678
1 B.*...** 1 @@*@@@**
2 *.*.*.** 2 *@*@*@**
3 *...*... 3 *@@@*@@@
4 *.*.*.*. 4 *.*.*.*@
5 ....*.*B 5 ....*.*@
PROBLEM NAME: skate
INPUT FORMAT:
* Line 1: Two space-separated integers, respectively R and C
* Lines 2..R+1: Each line contains C characters (with no spaces).
Each character is either a '.' indicating that Bessie can
skate on that square or a '*' indicating that the square has
too many rocks.
SAMPLE INPUT (file skate.in):
5 8
..*...**
*.*.*.**
*...*...
*.*.*.*.
....*.*.
OUTPUT FORMAT:
* Lines 1..?: Each line contains two space-separated integers that are
the R,C coordinates of a square Bessie occupies. The first
line should be 1 1; the last line should be the integers R
and C. Intermediate lines show, square by square, the path
Bessie takes between squares 1,1 and R,C.
SAMPLE OUTPUT (file skate.out):
1 1
1 2
2 2
3 2
3 3
3 4
2 4
1 4
1 5
1 6
2 6
3 6
3 7
3 8
4 8
5 8
**********************************************************************
Problem 4: Cow Pie Treasures [Kolstad, 2006]
The cows have been busily baking pies that contain gold coins! Each
pie has some number Ni (1 <= Ni <= 25) of gold coins and is neatly
labeled on its crust with the number of gold coins inside.
The cows have placed the pies very precisely in an array of R rows
(1 <= R <= 100) and C columns (1 <= C <= 100) out in the pasture.
You have been placed in the pasture at the location (R=1,C=1) and
have gathered the gold coins in that pie. You must make your way
to the other side of the pasture, moving one column closer to the
end point (which is location (R,C)) with each move you make. As you
step to the new column, you may stay on the same row or change your
row by no more than 1 (i.e., from (r,c) you can move to (r-1,c+1),
(r, c+1), or (r+1,c+1). Of course, you would not want to leave the
field and fail to get some gold coins, and you must end up at (R,C).
Given a map of the pasture, what is the greatest number of gold
coins you can gather?
By way of example, consider this field of gold-bearing cow pies:
start-> 6 5 3 7 9 2 7
2 4 3 5 6 8 6
4 9 9 9 1 5 8 <-end
Here's one path:
start-> 6 5 3 7 9 2 7
\
2 4 3 5 6 8 6
\ / \
4 9 9-9 1 5-8 <-end
The path above yields 6+4+9+9+6+5+8 = 47 gold coins. The path below
is even better and yields 50 coins, which is the best possible:
start-> 6 5 3 7 9 2 7
\
2 4 3 5 6-8 6
\ / \
4 9 9-9 1 5 8 <-end
PROBLEM NAME: pie1
INPUT FORMAT:
* Line 1: Two space-separated integers, respectively R and C
* Lines 2..R+1: Each line contains C space-separated integers in the
obvious order
SAMPLE INPUT (file pie1.in):
3 7
6 5 3 7 9 2 7
2 4 3 5 6 8 6
4 9 9 9 1 5 8
OUTPUT FORMAT:
* Line 1: A single integer that is the maximum number of gold coins
that can be gathered
SAMPLE OUTPUT (file pie1.out):
50
**********************************************************************
Problem 5: Hungry Cows [Kolstad, 2006]
Each of Farmer John's N (1 <= N <= 5,000) cows has a unique positive
integer brand that fits nicely into 32 signed bits. He wishes the
cows would line up in numerical order for feeding, but they never
cooperate. To encourage good behavior, he allows a cow to eat only
if it is the first cow to be chosen to eat or if its number is
greater than the cow that ate before it.
Given a listing of the ordering of cow brands for the cows standing in
line, what is the largest number of cows that can be fed using FJ rules?
Consider this line of 11 cows:
2 5 18 3 4 7 10 9 11 8 15
One could feed cows 2, 3, 4, 7, 10 11, and 15 for a total of seven fed, the
largest number possible.
One could not feed cows 2, 5, 3, 10 15 since cow 3's brand is not greater
than its predecessor, 5.
PROBLEM NAME: lineup
INPUT FORMAT:
* Line 1: A single integer, N
* Lines 2..?: Each line except potentially the last contains 20
space-separated integers that are successively the brands of
the cows in line. The last line might have fewer than 20
integers if N is not an exact multiple of 20.
SAMPLE INPUT (file lineup.in):
11
2 5 18 3 4 7 10 9 11 8 15
OUTPUT FORMAT:
* Line 1: The length of the largest chain of cows where each brand is
greater than its predecessor.
SAMPLE OUTPUT (file lineup.out):
7
**********************************************************************
Problem 6: Building the Moat [Eric Price, 2006]
To repel the invading thirsty aardvarks, Farmer John wants to build
a moat around his farm. He owns N (8 <= N <= 5,000) watering holes,
and will be digging the moat in a straight line between pairs of
them. His moat should protect (i.e., surround) all his watering
holes; every watering hole must be on or inside the moat, and the
moat must form a closed loop.
Digging a moat is expensive work, and frugal FJ wants his moat to
have the minimum length possible. Find the length of the shortest
moat he can construct.
The unique holes are each located at integer coordinates in the
range (1..10,000,000, 1..10,000,000). FJ has noticed that no three
watering holes lie along the same line.
Consider this grid where the 20 '*'s represent watering holes:
...*-----------------*......
../..........*........\.....
./.....................\....
*......................*\...
|..........*........*....\..
|*........................\.
|..........................*
*..........................|
.\*........................|
..\.....................*..|
...\........*............*.|
....\..................*...*
.....\..*..........*....../.
......\................../..
.......*----------------*...
The enclosing lines are the shortest possible path that can enclose
this set of watering holes.
The line displacements, starting with the top line are: (18,0),
(6,-6), (0,-5), (-3,-3), (-17,0), (-7,7), (0,4), and (3,3). This
yields a distance of 70.8700576850888(...). Our output will print
only two decimal places, so the distance will be reported as 70.87.
PROBLEM NAME: moat
INPUT FORMAT:
* Line 1: A single integer, N
* Lines 2..N+1: Two space-separated integers, X_i and Y_i that specify
the location of a watering hole.
SAMPLE INPUT (file moat.in):
20
2 10
3 7
22 15
12 11
20 3
28 9
1 12
9 3
14 14
25 6
8 1
25 1
28 4
24 12
4 15
13 5
26 5
21 11
24 4
1 8
OUTPUT FORMAT:
* Line 1: A single number D, the shortest possible length of moat.
Print this number to two decimal places.
SAMPLE OUTPUT (file moat.out):
70.87
