Usaco2008

Mirrored from [1]. Source from the old USACO website is currently unavailable.

OPEN08

Problem 1: The Ultimate Battle [Christos Tzamos, 2007]

Bessie and Canmuu are battling each other on a rectagular W x H (1
<= W <= 5,000; 1 <= H <= 5,000) field. Bessie is initially
positioned at coordinates (x1,y1) (1 <= x1 <= W; 1 <= y1 <= H);
Canmuu is positioned in different row and column at coordinates
(x2,y2) (1 <= x2 <= W; 1 <= y2 <= H; x1 != x2; y1 != y2). The
Ultimate Battle's winner is the first player who plasters the other
with a pie in the face.

While both players can see each other at all times, they can only
plaster their opponent with a pie in the face when the opponent
passes through (or stops on) the row or column occupied by the
pie-thrower.

Bessie starts first and they alternate turns. During each turn, a
player can move as many steps in any one of the four rectilinear
directions (up, down, left, right) as they wish -- without exceeding
the limits of the yard, of course.

Bessie asks for your help to beat Canmuu. Write a program to tell
her where to move for each of her turns.

This task is "interactive". Your program must first read six integers
from the input file and then interact with the grader as follows:

   At each of Bessie's turns, the program calculates and outputs
   the Bessie's new location. The new location must be a valid move,
   i.e., Bessie's new coordinate must differ from old one either
   in the x or y coordinate but not both. If she moves through one
   of Canmuu's x or y coordinates, the game terminates automatically
   with a moose victory (and a "wrong answer" for you).

   If Canmuu cannot make a move without losing, the grader will
   terminate your program automatically and award Bessie the victory.
   Otherwise, your program should read in Canmuu's move in two
   integers, the new coordinates of the methodical moose.

You may assume that Bessie will always start in a situation where a
victory is possible. You may also assume that Canmuu is no fool.

NOTE: Read the six integers from file pieface.in; read Canmuu's
moves from the standard input (i.e., console).

---------------- Reactive Programs ----------------------

In order to 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 (we hope) the skeleton of input/output statements you will
need:

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

public class pieface {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new
                                          InputStreamReader(System.in));
    /* write ... */
        System.out.println(...);
        System.out.flush();

    /* read a reply */
        response = in.readLine();
        ...

PROBLEM NAME: pieface

INPUT FORMAT:

* Line 1: Six space-separated integers: W, H, x1, y1, x2, and y2

SAMPLE INPUT (file pieface.in):

3 3 1 1 2 3

OUTPUT FORMAT:

* Line All: Each output line contains a pair of space-separated
        integers that represent Bessie's new location.

SAMPLE OUTPUT (file pieface.out):

Do not use the file 'pieface.out'. See below for sample interactions.

OUTPUT DETAILS:

Here is a possible winning interaction:

> 1 2       Bessie moves up by 1 to 1,2
< 3 3       Canmuu moves to 1 to the right to 3,3
> 2 2       Bessie moves to 2,2 by going one to the right
At which point Canmuu could no longer make a move without getting
a pie in the face.

3 . C .      . C .       . . C      . . C
2 . . .  =>  B . .  =>   B . .  =>  . B . => Canmuu must pass Bessie's row
1 B . .      . . .       . . .      . . .    or column on his next move
  1 2 3      1 2 3       1 2 3      1 2 3

Problem 2: Crisis on the Farm [Thomas Williamson, 2004]

Farmer John and his herd of exotic dancing bovines have been
practicing for his new moosical, "The Street Cow Named Desire". At
one point in the middle of rehearsal, his cows are stacked on top
of each other in N (1 <= N <= 1,000) sets of 30, one cow standing
on the back of the other (they are quite amazing cows). Thus, the
pasture is dotted with both these stacks of 30 cows and also, in
separate locations, M (1 <= M <= 1,000) haystacks. Below is a sample
of one way they might be laid out:

                8 .........
                7 ....CH.H.         C = stack of 30 cows
                6 .........
                5 .........         H = haystack
                4 ..C.HH...
                3 .........
                2 .....C.HH
                1 .........
                  123456789

As the musical's conductor, Farmer John has four whistles with
various tones. One whistle commands the cow at the bottom of each
stack to move (along with all the stacked cows) one unit north,
another indicates a move to the south, one indicates a move to the
east, and a fourth to order a move to the west.

Any time the stack of cows enters a grid location with a haystack,
the cow on the top of the stack (even if the stack has height one)
will jump onto the haystack while the remaining cows move into the
same location as the haystack. Thus, if the bottom cow encounters
30 haystacks (perhaps different haystacks, perhaps not), the stack
of 30 cows is exhausted with all the cows standing on top of haystacks
(or standing on cows on haystacks). The sturdy haystacks can each
support an unlimited number of cows.

Farmer John glances across his pasture to Farmer Don's milking
facility to see, to his horror, a huge milk tank exploding and
unleashing a giant tidal wave of milk making its way toward the
performing cows! Since any cows on a haystack are safe, FJ must now
do what he can to save the lives of as many cows as possible using
what has turned from a simple dance routine into a lifesaving
technique.

Given the number of times K (1 <= K <= 30) farmer John can blow a
whistle until the wave of milk crashes over the pasture and also
the X_i, Y_i positions (1 <= X_i <= 1,000; 1 <= Y_i <= 1,000) of
the N stacks of cows and M haystacks (none of which currently has
any cows on it), report the greatest number of cows that can be
saved and find a sequence of whistle blows that does the job. The
sequence should be reported in terms of the four directions, 'E'
for east, 'N' for north, 'W' for west, 'S' for south.  Among all
such sequences, farmer John wants the lexicographically least.
Initial locations of cows and haystacks will not share the same
coordinates in the input file.

Cows can be moved to any location, including ones outside the
pasture.

PROBLEM NAME: crisis

INPUT FORMAT:

* Line 1: Three space-separated integers: N, M, and K

* Lines 2..N+1: Line i+1 describes the X,Y location of a stack of 30
        cows using two space-separated integers: X_i and Y_i

* Lines N+2..N+M+1: Line i+N+1 describes the X,Y location of a
        haystack using two space-separated integers: X_i and Y_i

SAMPLE INPUT (file crisis.in):

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

OUTPUT FORMAT:

* Line 1: A single integer that is the most number of cows that can be
        saved.

* Line 2: K characters, the lexicographically least sequence of
        commands FJ should issue to maximize the number of cows saved.

SAMPLE OUTPUT (file crisis.out):

6
EEE

OUTPUT DETAILS:

Use the 'east' whistle three times, at which point the milk floods
the area.  Each haystack ends up saving 1 cow.

Problem 3: Cow Neighborhoods [Richard Ho, 2006]

Those Who Know About Cows are aware of the way cows group into "Cow
Neighborhoods". They have observed Farmer John's N (1 <= N <=
100,000) cows (conveniently numbered 1..N) as they graze, each at
her own unique integer rectilinear coordinate, on a pasture whose
X and Y coordinates are in the range 1..1,000,000,000.

Two cows are neighbors if at least one of two criteria is met:

  1) If the cows are no further than some integer Manhattan distance
     C (1 <= C <= 1,000,000,000) apart, they are neighbors. [Manhattan
     distance is calculated as d = |x1-x2| + |y1-y2|.]

  2) If cow A is a neighbor of cow Z and cow B is a neighbor of cow
     Z, then cow A is a neighbor of cow B (the "transitive closure
     of neighbors").

Given the locations of the cows and the distance C, determine the
the number of neighborhoods and the number of cows in the largest
neighborhood.

By way of example, consider the pasture below. When C = 4, this
pasture has four neighborhoods: a big one on the left, two neighborhoods
of size 1 (the lonesome cows), and a huge neighborhood on the right
with 60 different cows.

.....................................*.................
....*...*..*.......................***.................
......*...........................****.................
..*....*..*.......................*...*.******.*.*.....
........................*.............***...***...*....
*..*..*...*..........................*..*...*..*...*...
.....................................*..*...*..*.......
.....................................*..*...*..*.......
...*................*..................................
.*..*............................*.*.*.*.*.*.*.*.*.*.*.
.*.....*..........................*.*.*.*.*.*.*.*.*.*.*
....*..................................................

The input file describes cow locations by integer X,Y coordinates,
where the lower left corner is (1,1) and cows close to that corner
appear at both (2,2) and (5,1) in the example above.

For a given pasture, determine both the number of cow neighborhoods
and the number of cows resident in the largest cow neighborhood.

The above picture is sample test case 2, which will be evaluated
for you upon submission.

Partial feedback for some test cases will be provided on the first
10 submissions.

Time Limit: 2 seconds

Memory Limit: 32MB

PROBLEM NAME: nabor

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 describes cow i's location with two
        space-separated integers: X_i and Y_i

SAMPLE INPUT (file nabor.in):

4 2
1 1
3 3
2 2
10 10

OUTPUT FORMAT:

* Line 1: A single line with a two space-separated integers: the
        number of cow neighborhoods and the size of the largest cow
        neighborhood.

SAMPLE OUTPUT (file nabor.out):

2 3

OUTPUT DETAILS:

There are 2 neighborhoods, one formed by the first three cows and
the other being the last cow. The largest neighborhood therefore
has size 3.