Usaco Open12 Bronze

Part of USACO Open12

**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Three problems numbered 1 through 4
**********************************************************************

Problem 1: Cows in a Row [Brian Dean, 2012]

Farmer John's N cows (1 <= N <= 1000) are lined up in a row.  Each cow is
identified by an integer "breed ID"; the breed ID of the ith cow in the
lineup is B(i).

FJ thinks that his line of cows will look much more impressive if there is
a large contiguous block of cows that all have the same breed ID.  In order
to create such a block, FJ decides remove from his lineup all the cows
having a particular breed ID of his choosing.  Please help FJ figure out
the length of the largest consecutive block of cows with the same breed ID
that he can create by removing all the cows having some breed ID of his
choosing.

PROBLEM NAME: cowrow

INPUT FORMAT:

* Line 1: The integer N.

* Lines 2..1+N: Line i+1 contains B(i), an integer in the range
        0...1,000,000.

SAMPLE INPUT (file cowrow.in):

9
2
7
3
7
7
3
7
5
7

INPUT DETAILS:

There are 9 cows in the lineup, with breed IDs 2, 7, 3, 7, 7, 3, 7, 5, 7.

OUTPUT FORMAT:

* Line 1: The largest size of a contiguous block of cows with
        identical breed IDs that FJ can create.

SAMPLE OUTPUT (file cowrow.out):

4

OUTPUT DETAILS:

By removing all cows with breed ID 3, the lineup reduces to 2, 7, 7, 7, 7,
5, 7.  In this new lineup, there is a contiguous block of 4 cows with the
same breed ID (7).

**********************************************************************

Problem 2: Three Lines [Brian Dean, 2012]

Farmer John wants to monitor his N cows (1 <= N <= 50,000) using a new
surveillance system he has purchased.  

The ith cow is located at position (x_i, y_i) with integer coordinates (in
the range 0...1,000,000,000); no two cows occupy the same position.  FJ's
surveillance system contains three special cameras, each of which is
capable of observing all the cows along either a vertical or horizontal
line.  Please determine if it is possible for FJ to set up these three
cameras so that he can monitor all N cows.  That is, please determine if
the N locations of the cows can all be simultaneously "covered" by some set
of three lines, each of which is oriented either horizontally or vertically.

[Note: programs that do nothing more than make random guesses about the
output may be disqualified, receiving a score of zero points]

PROBLEM NAME: 3lines

INPUT FORMAT:

* Line 1: The integer N.

* Lines 2..1+N: Line i+1 contains the space-separated integer x_i and
        y_i giving the location of cow i.

SAMPLE INPUT (file 3lines.in):

6
1 7
0 0
1 2
2 0
1 4
3 4

INPUT DETAILS:

There are 6 cows, at positions (1,7), (0,0), (1,2), (2,0), (1,4), and (3,4).

OUTPUT FORMAT:

* Line 1: Please output 1 if it is possible to monitor all N cows with
        three cameras, or 0 if not.

SAMPLE OUTPUT (file 3lines.out):

1

OUTPUT DETAILS:

The lines y=0, x=1, and y=4 are each either horizontal or vertical, and
collectively they contain all N of the cow locations.

**********************************************************************

Problem 3: Islands [Brian Dean, 2012]

Whenever it rains, Farmer John's field always ends up flooding.  However,
since the field isn't perfectly level, it fills up with water in a
non-uniform fashion, leaving a number of "islands" separated by expanses of
water.

FJ's field is described as a one-dimensional landscape specified by N (1 <=
N <= 100,000) consecutive height values H(1)...H(n).  Assuming that the
landscape is surrounded by tall fences of effectively infinite height,
consider what happens during a rainstorm: the lowest regions are covered by
water first, giving a number of disjoint "islands", which eventually will
all be covered up as the water continues to rise. The instant the water
level become equal to the height of a piece of land, that piece of land is
considered to be underwater.

fig_islands.png
An example is shown above: on the left, we have added just over 1 unit of
water, which leaves 4 islands (the maximum we will ever see). Later on,
after adding a total of 7 units of water, we reach the figure on the right
with only two islands exposed. Please compute the maximum number of islands
we will ever see at a single point in time during the storm, as the water
rises all the way to the point where the entire field is underwater.

PROBLEM NAME: islands

INPUT FORMAT:

* Line 1: The integer N.

* Lines 2..1+N: Line i+1 contains the height H(i).  (1 <= H(i) <=
        1,000,000,000)

SAMPLE INPUT (file islands.in):

8
3
5
2
3
1
4
2
3

INPUT DETAILS:

The sample input matches the figure above.

OUTPUT FORMAT:

* Line 1: A single integer giving the maximum number of islands that
        appear at any one point in time over the course of the
        rainstorm.

SAMPLE OUTPUT (file islands.out):

4

**********************************************************************

Problem 4: Unlocking Blocks [Brian Dean, 2012]

A little-known fact about cows is that they love puzzles! For Bessie's
birthday, Farmer John gives her an interesting mechanical puzzle for her to
solve.  The puzzle consists of three solid objects, each of which is built
from 1x1 unit squares glued together.  Each of these objects is a
"connected" shape,  in the sense that you can get from one square on the
object to any other square on the object by stepping north, south, east, or
west, through squares on the object.

An object can be moved by repeatedly sliding it either north, south, east,
or west one unit.  The goal of the puzzle is to move the objects so that
they are separated -- where their bounding boxes are disjoint from
each-other.  Given the shapes and locations of the three objects, your task
is to help Bessie decide if they can be separated or not. A configuration
that is non-separable is said to be locked.

fig_unlock.png
[Note: programs that do nothing more than make random guesses about the
output may be disqualified, receiving a score of zero points]

PROBLEM NAME: unlock

INPUT FORMAT:

* Line 1: Three space-separated integers: N1, N2, and N3, describing
        respectively the number of unit squares making up objects 1,
        2, and 3.

* Lines 2..1+N1: Each of these lines describes the (x,y) location of
        the south-west corner of single square that is part of object
        1.  All coordinates lie in the range 0..9.

* Lines 2+N1..1+N1+N2: Each of these lines describes the (x,y)
        location of the south-west corner of single square that is
        part of object 2.  All coordinates lie in the range 0..9.

* Lines 2+N1+N2..1+N1+N2+N3: Each of these lines describes the (x,y)
        location of the south-west corner of single square that is
        part of object 3.  All coordinates lie in the range 0..9.

SAMPLE INPUT (file unlock.in):

12 3 5
0 0
1 0
2 0
3 0
3 1
0 1
0 2
0 3
0 4
1 4
2 4
3 4
2 1
2 2
1 2
2 3
3 3
4 3
4 4
4 2

INPUT DETAILS:

Object 1 is made from 12 squares, object 2 is made from 3 squares, and
object 3 is made from 5 squares.  The shapes of the objects are those in
the figure above.

OUTPUT FORMAT:

* Line 1: Output 1 if the objects can be separated from each-other, or
        0 if they are locked.

SAMPLE OUTPUT (file unlock.out):

1

**********************************************************************
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License