Usaco Nov11 Silver

Part of USACO Nov11

**********************************************************************
SILVER PROBLEMS
**********************************************************************
Three problems numbered 1 through 3
**********************************************************************

Problem 1: Cow Beauty Pageant (Silver Level) [Brian Dean]

Hearing that the latest fashion trend was cows with three spots on their
hides, Farmer John has purchased an entire herd of three-spot cows.
Unfortunately, fashion trends tend to change quickly, and the most popular
current fashion is cows with only one spot!

FJ wants to make his herd more fashionable by painting each of his cows in
such a way that merges their three spots into one.  The hide of a cow is
represented by an N by M grid of characters like this:

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....

Here, each 'X' denotes part of a spot.  Two 'X's belong to the same spot if
count), so the figure above has exactly three spots.  All of the cows in
FJ's herd have exactly three spots.

FJ wants to use as little paint as possible to merge the three spots into
one.  In the example above, he can do this by painting only four
additional characters with 'X's (the new characters are marked with '*'s
below to make them easier to see).

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
...*....XXXXX...
..XXX....XXX....

order to merge three spots into one large spot.

PROBLEM NAME: pageant

INPUT FORMAT:

* Line 1: Two space-separated integers, N and M (1 <= N,M <= 50).

* Lines 2..1+N: Each line contains a length-M string of 'X's and '.'
specifying one row of the cow hide pattern.

SAMPLE INPUT (file pageant.in):

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....

INPUT DETAILS:

The pattern in the input shows a cow hide with three distinct spots.

OUTPUT FORMAT:

* Line 1: The minimum number of new 'X's that must be added to the
input pattern in order to obtain one single spot.

SAMPLE OUTPUT (file pageant.out):

4

OUTPUT DETAILS:

Four 'X's suffice to join the three spots into one.

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

Problem 2: Cow Lineup [Brian Dean]

Farmer John has hired a professional photographer to take a picture of some
of his cows.  Since FJ's cows represent a variety of different breeds, he
would like the photo to contain at least one cow from each distinct breed
present in his herd.

FJ's N cows are all standing at various positions along a line, each
described by an integer position (i.e., its x coordinate) as well as an
integer breed ID.  FJ plans to take a photograph of a contiguous range of
cows along the line.  The cost of this photograph is equal its size -- that
is, the difference between the maximum and minimum x coordinates of the
cows in the range of the photograph.

is at least one cow of each distinct breed appearing in FJ's herd.

PROBLEM NAME: lineup

INPUT FORMAT:

* Line 1: The number of cows, N (1 <= N <= 50,000).

* Lines 2..1+N: Each line contains two space-separated positive
integers specifying the x coordinate and breed ID of a single
cow.  Both numbers are at most 1 billion.

SAMPLE INPUT (file lineup.in):

6
25 7
26 1
15 1
22 3
20 1
30 1

INPUT DETAILS:

There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs
7,1,1,3,1,1.

OUTPUT FORMAT:

* Line 1: The smallest cost of a photograph containing each distinct
breed ID.

SAMPLE OUTPUT (file lineup.out):

4

OUTPUT DETAILS:

The range from x=22 up through x=26 (of total size 4) contains each of the
distinct breed IDs 1, 3, and 7 represented in FJ's herd.

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

Problem 3: Tile Exchanging [Ray Li]

Farmer John wants to remodel the floor of his barn using a collection of
square tiles he recently purchased from the local square mart store (which
of course, only sells square objects).  Unfortunately, he didn't measure
the size of the barn properly before making his purchase, so now he needs
to exchange some of his tiles for new square tiles of different sizes.

The N square tiles previously purchased by FJ have side lengths A_1...A_N.
He would like to exchange some of these with new square tiles so that the
total sum of the areas of the his tiles is exactly M.  Square mart is
currently offering a special deal: a tile of side length A_i can be
exchanged for a new tile of side length B_i for a cost of
|A_i-B_i|*|A_i-B_i| units. However, this deal only applies to
previously-purchased tiles -- FJ is not allowed to exchange a tile that he
has already obtained via exchanging some other tile (i.e., a size-3 tile
cannot be exchanged for a size-2 tile, which is then exchanged for a size-1
tile).

Please determine the minimum amount of money required to exchange tiles so
that the sum of the areas of the tiles becomes M.  Output -1 if it is
impossible to obtain an area of M.

PROBLEM NAME: tilechng

INPUT FORMAT:

* Line 1: Two space-separated integers, N (1<=N<=10) and M
(1<=M<=10,000).

* Lines 2..1+N: Each line contains one of the integers A_1 through
A_N, describing the side length of an input square
(1<=A_i<=100).

SAMPLE INPUT (file tilechng.in):

3 6
3
3
1

INPUT DETAILS:

There are 3 tiles.  Two are squares of side length 3, and one is a square
with side length 1.  We would like to exchange these to make a total area of 6.

OUTPUT FORMAT:

* Line 1: The minimum cost of exchanging tiles to obtain M units of
total area, or -1 if this is impossible.

SAMPLE OUTPUT (file tilechng.out):

5

OUTPUT DETAILS:

Exchange one of the side-3 squares for a side-2 square, and another side-3
square for a side-1 square.  This gives the desired area of 4+1+1=6 and
costs 4+1=5 units.

**********************************************************************
page revision: 0, last edited: 25 Nov 2011 00:48