Usaco Feb11 Bronze

Part of USACO Feb11

**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Three problems numbered 11 through 13
**********************************************************************

Problem 11: Cow Cotillion [Sherry Wu & Rob Kolstad, 2011]

The cow cotillion, a fancy dance every spring, requires the cows
(shown as ">") and bulls (shown as "<") to bow to each other during
a dance. Schematically, one properly bowing pair of cattle is shown
like this: "><". Sometimes another pair of cattle will sashay between
a pair of bowing cows: "> >< <".

In fact, sometimes a larger number of cows will mix it up on the
dance floor: "> >< < ><" (this includes a second set of bowing cows
on the right). Complex arrangements can be perfectly legal dance
formations:
              > > > >< < >< < >< >< >< <

              | | | -- | -- | -- -- -- |
              | | ------    |          |
              | -------------          |
              --------------------------

Farmer John notices that a stray heifer sometimes sneaks into a
group and unbalances it: "> >< < <><". This is strictly forbidden;
FJ wants to punish the interlopers.

FJ has copied down records of as many as 500 cows participating in
dance lines and wonders if the dance line is properly balanced
(i.e., all of the cattle can be paired off in at least one way as
properly bowing pair by pair). He copied only the direction each
cow was bowing without any extra spaces to help determine which cow
was bowing to which bull, strings like this rendition of the illegal
example from the previous paragraph: ">><<<><". He wants you to
write a program to tell him if the dance line is legal.

FJ has N (1 <= N <= 1,000) pattern recordings P_i comprising just
the characters '>' and '<' with varying length K_i (1 <= K_i <=
200).  Print "legal" for those patterns that include proper pairs
of bowing cows and "illegal" for those that don't.

PROBLEM NAME: dance2

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i contains an integer followed by a space and a
        string of K characters '>' and '<': K_i and P_i

SAMPLE INPUT (file dance2.in):

2
6 >><<><
4 ><<>

OUTPUT FORMAT:

* Lines 1..N: Line i contains either the word "legal" or "illegal"
        (without the quotes, of course) depending on whether the input
        has a legal bowing configuration.

SAMPLE OUTPUT (file dance2.out):

legal
illegal

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

Problem 12: Cow Treats [Rob Kolstad, 2010]

The cows celebrated another banner month for record milk production
and thus have each earned a special treat. They completely fill a
W x H rectangle formation (1 <= W <= 25; 1 <= H <= 25) awaiting
their treat.

Each cow has a unique figure of merit F_rc (1 <= F_rc <= 1,000,000)
which denotes her overall milk production performance. Farmer John
thinks it is only fair to prioritize the treats handed out, rewarding
the highest producing cows first. He plans to traverse the rectangular
formation one row at a time, starting at the beginning of row 1 and
giving out all row 1's treats before he starts on row 2 using the
same method.

He has asked the cows to reorganize themselves so that the cows
with better production are rewarded first. The cows, though, are
not so very good at organization. They can either swap a pair of
rows or swap a pair of columns of their formation. FJ has asked
them to do the best they can by moving the best cow to the upper
left corner (row 1, column 1), the next best cow to row 1, column
2 (if possible), and so on. Of course, the cows can not fully sort
themselves, but they can do their best by following this heuristic:

    * determine the order of FJ's treat awards:
            1    2   3  ...
            W+1 W+2 W+3 ...

    * find the highest rated cow; swap rows and columns until she
      is at row 1, column 1; never move her again

    * Then execute this rule until as many cows are placed as possible:

    Find the next highest rated cow. Swap rows and columns
    (without moving any higher-rated cow) to move her to the
    best possible spot that is still available (e.g., row 1,
    column 2 if it's available of row 2, column 1 if no slots
    can be achieved in row 1.

By way of example, consider this set of 3 x 4 cows:

         5  7  4  1
         9 99  2  6
         8  3 10 11

The cow with 99 is clearly the highest-rated and belows in the upper
left corner. Swap rows 1 and 2 then swap columns 1 and 2 (or do it
the other way around -- the answer is the same):

         99  9  2  6
          7  5  4  1
          3  8 10 11

The cow with 11 should be rewarded as soon as possible after the
highest-rated cow. She is current in slot (3,4), the last slot to
be rewarded. At this point, it's too late to swap her into the first
row or even the first column. Thus, she needs to move to (2,2) by
swapping columns 2 and 4 then swapping rows 2 and 3:

       Swap cols 2 and 4     Swap rows 2 and 3
         99   6  2  9          99   6  2  9
          7   1  4  5    ->     3  11 10  8
          3  11 10  8           7   1  4  5

The cow with 10 is rewarded directly after the cow with 11.  The
cow 9 is already rewarded. The cow with 8 is awarded just after the
cow with 10. The cow with 7 is rewarded directly after the cow with
8.  The cow with 6 is already rewarded. The cow with 5 would best
move to row 3, column 2 but the rows 1 and 2 are frozen as are all
the columns.  Thus, cows 1, 4, and 5 do not move, and the second
diagram above is the "best the cows can do".

Implement this algorithm for other rectangular arrays of cows.

PROBLEM NAME: treats

INPUT FORMAT:

* Line 1: Two space-separated integers: W and H

* Lines 2..H+1: Line i+1 contains W space-separated integers F_ic,
        where c ranges from 1 to W.

SAMPLE INPUT (file treats.in):

4 3
5 7 4 1
9 99 2 6
8 3 10 11

OUTPUT FORMAT:

* Lines 1..H: Line i contains W space-separated integers representing
        the i-th row of cows in the cows' final formation.

SAMPLE OUTPUT (file treats.out):

99 6 2 9
3 11 10 8
7 1 4 5

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

Problem 13: Hexagonal Pasture Network [Andre Kessler, 2011]

Farmer John recently acquired some new land to expand his farm. His
cows have taken a liking to the hexagonal structure of bee honeycombs,
and, ever willing to please his herd, Farmer John has set up a new
system of pastures and cowpaths in this format.

The full plot of pastures and cowpaths forms a hexagon with side
length K (2 <= K <= 50). Pastures are conveniently numbered
1..3*K*(K-1)+1 starting in the bottom left and ending in the upper
right using the pattern generalized from this illustration where K
= 3:

1183.hex1.gif
Each pasture is connected to all of its immediate neighbors. This
means that if a pasture is on the inside of the hexagon, it is
adjacent to exactly six other pastures. For example, in the diagram
above, pasture #10 is adjacent to pastures #5, #6, #11, #15, #14,
and #9. Pastures on the edge (but not on a corner) of the structure
are adjacent to exactly four other pastures (for example, pasture
#4 is adjacent to #1, #5, #9, and #8) while pastures at a corner
are adjacent to only three pastures (e.g., pasture #1 is connected
to pastures #2, #5, and #4). The length of any cowpath connecting
two pastures is 1 and the distance between two pastures is defined
to be the length of the shortest possible route between them.

Farmer John's Holstein cows have been munching on the grass in
pasture H (1 <= H <= 3*K*(K-1)+1) for several days now and have
grown fat and lazy. To force his cows to get some exercise, Farmer
John has laid down tasty cow treats in pastures exactly distance
of L (1 <= L <= 2*K-2) away from the cows. He guarantees the cows
that he has placed at least one treat, but he doesn't tell the cows
the pastures in which he's placed them.

Please help the cows avoid any unnecessary exercise by printing the
number of possible pastures which might hold the treats and a list
of those possible pastures in ascending order.

By way of example, suppose K = 3, the Holsteins are in pasture #1, and
Farmer John says he's placed some treats in pastures a distance of
2 away.  The possible locations of the treats are pastures #3, #6,
#10, #9, and #8, as shown below.

1183.hex2.gif
PROBLEM NAME: hexagon

INPUT FORMAT:

* Line 1: Three space-separated integers: K, H, and L

SAMPLE INPUT (file hexagon.in):

3 1 2

OUTPUT FORMAT:

* Line 1: A single integer: the number of pastures a distance of L
        away from pasture H

* Lines 2..N+1: Line i+1 contains the i-th such pasture, printed in
        ascending order

SAMPLE OUTPUT (file hexagon.out):

5
3
6
8
9
10

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