Usaco Jan11 Bronze

Part of USACO Jan11

**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Four problems numbered 11 through 14
**********************************************************************

Problem 11: Symmetry [Jeffrey Wang, 2009]

Farmer John loves symmetry and is currently arranging his cows on
his field partitioned into an N x M (1 <= N <= 1,000,000,000; 1 <=
M <= 1,000,000,000) grid.

To preserve symmetry, Farmer John places cows in the following way.
He puts a cow in the very center grid-square of the field; if no
such grid-square exists, he simply stops. Then he partitions the field
into four equal-sized smaller fields (separated by the row and
column of the cow in the center) and arranges cows on each of those
fields as before. He repeats the partitioning for ever-smaller
fields until no center grid-square of a field exists or the field
can not be subdivided.

By way of example, if N = 7 and M = 15 then Farmer John will place a cow in
row 4, column 8 and arrange each of the resulting 3x7 fields. In each of
the 3x7 fields, Farmer John will place a cow in row 2, column 4 and arrange
each of the resulting 1x3 fields. The process is shown here (where C
denotes a cow):

...............    ...............    .......|.......    .C.|.C.|.C.|.C.
...............    ...............    ...C...|...C...    ---C---|---C---
...............    ...............    .......|.......    .C.|.C.|.C.|.C.
............... -> .......C....... -> -------C------- -> -------C-------
...............    ...............    .......|.......    .C.|.C.|.C.|.C.
...............    ...............    ...C...|...C...    ---C---|---C---
...............    ...............    .......|.......    .C.|.C.|.C.|.C.

21 cows are required for this field. On the other hand, if N = M =
5 then Farmer John will only need to place one cow since the resulting
2x2 fields do not have center grid-squares. Help Farmer John determine
how many cows he needs to arrange his field.

PROBLEM NAME: sym

INPUT FORMAT:

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

SAMPLE INPUT (file sym.in):

7 15

OUTPUT FORMAT:

* Line 1: The number of cows needed

SAMPLE OUTPUT (file sym.out):

21

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

Problem 12: Cleaning the Dishes [Sherry Wu et al., 2010]

Bessie and Canmuu are teaming up to wash the massive pile of N (1
<= N <= 10,000) dirty dishes left over after the CowMoose Festival.
Bessie is washing the dishes; Canmuu will dry them.

Each dish has a unique serial number in the range 1..N. At the
beginning, the dishes are stacked in order with #1 on the top and
#N on the bottom.

Bessie first washes some number of dishes D_i by taking one from
the top of the incoming pile, washing it, and then stacking it on
the other side of the sink (this reverses the order of those dishes).

Once she has finished washing those dishes, either she washes another
set of dishes or Canmuu comes back to dry D_i dishes while Bessie
goes off to eat her well-earned snack. He takes those dishes, one
by one, off the stack that Bessie left him, dries the dish, and
stacks it (again in reverse order) in the 'cleaned' stack.

Canmuu then either takes another set of dishes to dry or goes off
to get a snack while Bessie comes back to wash. They repeat these
operations until all of the dishes are washed and dried.

What is the final order (top to bottom) in which the clean, dry
dishes are stacked?

To illustrate, suppose that Bessie has a stack of 5 dishes to wash:

1 <-- top
2
3
4
5 <-- bottom

D_1 is 3, so Bessie takes three dishes from the top of the stack,
one by one, washes them, and stacks on the other side of the sink
for Canmuu to dry:

       Unwashed
       | Washed but not dried
       | | Washed & Dried
       | | |
TOP    1             
       2          2   
       3      ->  3      ->  3      ->    3   
       4          4          4 2        4 2 
BOTTOM 5 - -      5 1 -      5 1 -      5 1 -
    Initial      Dish 1     Dish 2     Dish 3

Canmuu dries two of these, one by one, and places them onto the clean stack:

TOP         3                   
          4 2    ->  4 2   ->  4   2
BOTTOM    5 1 -      5 1 3     5 1 3

Bessie washes the final two dishes:

TOP                              5
          4   2  ->    4 2 ->    4 2
BOTTOM    5 1 3      5 1 3     - 1 3

Finally, Canmuu dries the last three dishes, stacking them in the
resulting order below:

TOP                                          1
                                  4          4
          5    ->      5  ->      5  ->      5
          4 2        4 2          2          2
BOTTOM  - 1 3      - 1 3      - 1 3      - - 3

So the final order is: 1, 4, 5, 2, 3.

Each of the main input lines contains both a command, C_i (1 <= C_i
<= 2) where 1 indicates Bessie washing while 2 indicates Canmuu
drying, and the number of dishes D_i (1 <= D_i <= N) to be washed
or dried.

PROBLEM NAME: dishes

INPUT FORMAT:

* Line 1: A single integer indicating the number of dishes to wash and
        dry: N

* Lines 2..??: Each line contains a command and a count of dishes to
        process: C_i and D_i

SAMPLE INPUT (file dishes.in):

5
1 3
2 2
1 2
2 3

OUTPUT FORMAT:

* Lines 1..N: Line i contains the i-th cleaned dish, starting from the
        top

SAMPLE OUTPUT (file dishes.out):

1
4
5
2
3

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

Problem 13: Space Exploration [Andre Kessler, 2010]

Farmer John's cows have finally blasted off from earth and are now
floating around space in their Moocraft. The cows want to reach
their fiery kin on Jupiter's moon of Io, but to do this they must
first navigate through the dangerous asteroid belt.

Bessie is piloting the craft through this treacherous N x N (1 <=
N <= 1,000) sector of space. Asteroids in this sector comprise some
number of 1 x 1 squares of space-rock connected along their edges
(two squares sharing only a corner count as two distinct asteroids).
Please help Bessie maneuver through the field by counting the number
of distinct asteroids in the entire sector.

Consider the 10 x 10 space shown below on the left. The '*'s represent
asteroid chunks, and each '.' represents a .vast void of empty space. The
diagram on the right shows an arbitrary numbering applied to the asteroids.

               ...**.....           ...11.....
               .*........           .2........
               ......*...           ......3...
               ...*..*...           ...3..3...
               ..*****...           ..33333...
               ...*......           ...3......
               ....***...           ....444...
               .*..***...           .5..444...
               .....*...*          ......4...6
               ..*.......          ..7........

It's easy to see there are 7 asteroids in this sector.

PROBLEM NAME: space

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains row i of the asteroid field: N
        characters

SAMPLE INPUT (file space.in):

10
...**.....
.*........
......*...
...*..*...
..*****...
...*......
....***...
.*..***...
.....*...*
..*.......

OUTPUT FORMAT:

* Line 1: A single integer indicating the number of asteroids in the
        field.

SAMPLE OUTPUT (file space.out):

7

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

Problem 14: Crop Circles [Rob Kolstad, 2011]

Bessie and her fellow herd-mates have become extremely territorial.
The N (1 <= N <= 400) cows conveniently numbered 1..N have all
staked out a grazing spot in the pasture. Each cow i has a spot on
an integer grid (0 <= X_i <= 10,000; 0 <= Y_i <= 10,000) and an
integer radius R_i that indicates the circle she is staking out (1
<= R_i <= 500).

The cows are a bit greedy and sometimes stake out territory of their
herd-mates. For each cow, calculate the number of other cows whose
territory overlaps her territory.

By way of example, consider these six cows with indicated locations
and radii (don't confuse radius with diameter!):

1801example.gif
By visual inspection, we can see and count the overlaps, as shown.

NOTE: the test data will avoid pathological situations like tangents
where the circles just barely touch.

PROBLEM NAME: cropcir

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Three space-separated integers: X_i, Y_i, and R_i

SAMPLE INPUT (file cropcir.in):

6
7 7 7
16 14 7
11 13 2
10 17 3
29 8 5
15 7 4

OUTPUT FORMAT:

* Lines 1..N: Line i contains a single integer that is the number of
        other fields that overlap with cow i's field.

SAMPLE OUTPUT (file cropcir.out):

3
4
3
2
0
2

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