This page was generated at 17:01:21 GMT.
You have 2 hours and 48.4
minutes remaining for contest submissions.
Contest ends in 3 days 21 hours 58
minutes 39 seconds. **********************************************************************
GOLD PROBLEMS
**********************************************************************
Three problems numbered 1 through 3
**********************************************************************
Problem 1: Muddy Fields [Alex Schwendner, 2004]
Rain has pummeled the cows' field, a rectangular grid of R rows and
C columns (1 <= R <= 50, 1 <= C <= 50). While good for the grass,
the rain makes some patches of bare earth quite muddy. The
cows, being meticulous grazers, don't want to get their hooves dirty
while they eat.
To prevent those muddy hooves, Farmer John will place a number of
wooden boards over the muddy parts of the cows' field. Each of the
boards is 1 unit wide, and can be any length long. Each board must
be aligned parallel to one of the sides of the field.
Farmer John wishes to minimize the number of boards needed to cover
the muddy spots, some of which might require more than one board
to cover. The boards may not cover any grass and deprive the cows
of grazing area but they can overlap each other.
Compute the minimum number of boards FJ requires to cover all the mud in
the field.
PROBLEM NAME: cover
INPUT FORMAT:
* Line 1: Two space-separated integers: R and C
* Lines 2..R+1: Each line contains a string of C characters, with '*'
representing a muddy patch, and '.' representing a grassy
patch. No spaces are present.
SAMPLE INPUT (file cover.in):
4 4
*.*.
.***
***.
..*.
OUTPUT FORMAT:
* Line 1: A single integer representing the number of boards FJ needs.
SAMPLE OUTPUT (file cover.out):
4
OUTPUT DETAILS:
Boards 1, 2, 3 and 4 are placed as follows:
1.2.
.333
444.
..2.
Board 2 overlaps boards 3 and 4.
**********************************************************************
Problem 2: The Wedding Juicer [Maria Plachta, 1999]
Farmer John's cows have taken a side job designing interesting punch-bowl
designs. The designs are created as follows:
* A flat board of size W cm x H cm is procured
(3 <= W <= 300, 3 <= H <= 300)
* On every 1 cm x 1 cm square of the board, a 1 cm x 1 cm
block is placed. This block has some integer height B (1
<= B <= 1,000,000,000)
The blocks are all glued together carefully so that punch will not drain
through them. They are glued so well, in fact, that the corner blocks
really don't matter!
FJ's cows can never figure out, however, just how much punch their bowl
designs will hold. Presuming the bowl is freestanding (i.e., no special
walls around the bowl), calculate how much juice the bowl can hold. Some
juice bowls, of course, leak out all the juice on the edges and will hold 0.
PROBLEM NAME: juice
INPUT FORMAT:
* Line 1: Two space-separated integers, W and H
* Lines 2..H+1: Line i+1 contains row i of bowl heights: W
space-separated integers each of which represents the height B
of a square in the bowl. The first integer is the height of
column 1, the second integers is the height of column 2, and
so on.
SAMPLE INPUT (file juice.in):
4 5
5 8 7 7
5 2 1 5
7 1 7 1
8 9 6 9
9 8 9 9
OUTPUT FORMAT:
* Line 1: A single integer that is the number of cc's the described
bowl will hold.
SAMPLE OUTPUT (file juice.out):
12
OUTPUT DETAILS:
Fill-up the two squares of height 1 to height 5, for 4 cc for each square.
Fill the square of height 2 to height 5, for 3 cc of joice. Fill the
square of height 6 to height 7 for 1 cc of juice. 2*4 + 3 + 1 = 12.
**********************************************************************
Problem 3: Naptime [Tiankai Liu, 2004]
Goneril is a very sleep-deprived cow. Her day is partitioned into
N (3 <= N <= 3,830) equal time periods but she can spend only B (2
<= B < N) not necessarily contiguous periods in bed. Due to her
bovine hormone levels, each period has its own utility U_i (0 <=
U_i <= 200,000), which is the amount of rest derived from sleeping
during that period. These utility values are fixed and are independent
of what Goneril chooses to do, including when she decides to be in
bed.
With the help of her alarm clock, she can choose exactly which
periods to spend in bed and which periods to spend doing more
critical items such as writing papers or watching baseball. However,
she can only get in or out of bed on the boundaries of a period.
She wants to choose her sleeping periods to maximize the sum of the
utilities over the periods during which she is in bed. Unfortunately,
every time she climbs in bed, she has to spend the first period
falling asleep and gets no sleep utility from that period.
The periods wrap around in a circle; if Goneril spends both periods
N and 1 in bed, then she does get sleep utility out of period 1.
What is the maximum total sleep utility Goneril can achieve?
PROBLEM NAME: naptime
INPUT FORMAT:
* Line 1: Two space-separated integers: N and B
* Lines 2..N+1: Line i+1 contains a single integer, U_i, between 0 and
200,000 inclusive
SAMPLE INPUT (file naptime.in):
5 3
2
0
3
1
4
INPUT DETAILS:
The day is divided into 5 periods, with utilities 2, 0, 3, 1, 4 in that
order. Goneril must pick 3 periods.
OUTPUT FORMAT:
* Line 1: A single integer, the maximum total sleep utility Goneril
can achieve.
SAMPLE OUTPUT (file naptime.out):
6
OUTPUT DETAILS:
Goneril can get total utility 6 by being in bed during periods 4,
5, and 1, with utilities 0 [getting to sleep], 4, and 2
respectively.
**********************************************************************