**********************************************************************
                           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. If N is initially 1,
the score is 0.

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]

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.

---------------- JAVA USERS ----------------------

Here is the skeleton of input/output statements you will need:

import java.io.*;
import java.util.*;

public class guess {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	/* read an integer: */
        int range = Integer.parseInt(in.readLine());

        String response;
	...

	/* write an integer: */
        System.out.println(guess);
        System.out.flush();
            
	/* read a reply */
        response = in.readLine();
        if (response.equals("H")) {
		...
	}
    ...

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
and C columns (1 <= R <= 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 in the order 2, 3, 4, 7, 10 11, and 15 for a total of
seven fed, the largest number possible.

One could not feed cows in the order 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..45,000, 1..45,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