Usaco Hol09 Gold

Part of USACO Hol09

``````**********************************************************************
GOLD PROBLEMS
**********************************************************************
Four problems numbered 1 through 4
**********************************************************************

Problem 1: Cattle Bruisers [Neal Wu, 2008]

Canmuu is out for revenge after being utterly defeated by Bessie
in paintball and has challenged Bessie to a video game.

In this game, Bessie starts out at point (BX, BY) in the coordinate
grid (-1,000 <= BX <= 1,000; -1000 <= BY <= 1,000), and tries to
escape, starting at time 0. She moves continuously at a velocity
of (BVX, BVY) units/second (-100 <= BVX <= 100; -100 <= BVY <= 100).
Thus, at time 1 she will be at point (BX + BVX, BY + BVY); at time
1.5 she will be at (BX + 1.5*BVX, BY + 1.5*BVY).

Unfortunately, Canmuu has sent N (1 <= N <= 50,000) cattle bruisers
to pursue Bessie.  At time t=0, cattle bruiser i is at position
(X_i, Y_i) (-1,000 <= X_i <= 1,000; -1,000 <= Y_i <= 1,000) with
velocity (VX_i, VY_i) units/second (-1,000 <= VX_i <= 1,000; -1,000
<= VY_i <= 1,000).

Each cattle bruiser carries a "proximity" weapon to fire at Bessie;
the weapon can hurt Bessie when the cattle bruiser is no further
than R (1 <= R <= 2,500) units from her.

Bessie has a shield to protect herself from these attacks. However,
she does not want to waste any of her shield's power, so she would
like to know the maximum number of cattle bruisers within firing
range for any (potentially non-integer) time t >= 0.

In order to avoid precision errors with real numbers, it is guaranteed
that the answer produced will be the same whether the attack range
is decreased to R-0.0001 or increased to R+0.0001.

FEEDBACK: Your first 50  submissions for this problem will be run
on some of the official test data, and you will receive a summary
of the results.

PROBLEM NAME: cattleb

INPUT FORMAT:

* Line 1: Six space-separated integers: N, R, BX, BY, BVX, and BVY

* Lines 2..N+1: Line i+1 contains four space-separated integers: X_i,
Y_i, VX_i, and VY_i

SAMPLE INPUT (file cattleb.in):

3 1 0 0 0 2
0 -3 0 4
1 2 -1 1
1 -2 2 -1

INPUT DETAILS:

Bessie starts at point (0, 0) and is moving at 2 units per second
in the (positive) y-direction. There are 3 cattle bruisers, the
first of which starts at point (0, -3) and travels 4 units per
second in the y-direction. The maximum distance for a cattle bruiser
to be in range of Bessie is 1 unit.

OUTPUT FORMAT:

* Line 1: Print a single integer denoting the maximum number of cattle
bruisers within attack range at any point in time.

SAMPLE OUTPUT (file cattleb.out):

2

OUTPUT DETAILS:

At time 1.5, Bessie is at point (0, 3), and the three bruisers are
at points (0, 3), (-0.5, 3.5), and (4, -3.5). The first two cattle
bruisers are within 1 unit of Bessie, while the third will never
be within 1 unit of Bessie, so 2 is the most achievable.

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

Problem 2: Transmission Delay [Zeyuan Zhu, 2007]

Farmer John has taken to yodeling from the top of the barn in order
to communicate with the cows out in the pastures. Being bovine and
all, cows can hear binary messages (0's and 1's) but have trouble
with perfect communications because FJ's yodeling echoes off the
silo. In fact, in a sequence of N (1 <= N <= 2,000) bits, Bessie
will always receive a sequence of N bits, with the same number of
0s and 1s, but each 0 or 1 might be delayed.

Precisely speaking, for a given number D (0 <= D < N), the i-th bit
might be heard as the j-th one as long as |i - j| <= D (in other
words, no bit appears in a position farther than distance D from
its original position).

Consider the following message as an example: 0110. Four possible
messages might be heard if D = 1: 0101, 0110, 1001, and 1010.

Given the message to be yodeled by FJ, along with two numbers D and
K (1 <= K <= 100,000,000), determine the number of different messages
that might be heard by Bessie, modulo 100,000,000. Also determine
the K-th smallest such message in lexicographical order (in binary
representation, with 0 coming before 1). It is guaranteed that K
will be no larger than the number of different possible messages.

MEMORY LIMIT: 32 MB

TIME LIMIT: 2 seconds

FEEDBACK: Your first 50 submissions for this problem will be run
on some of the official test data, and you will receive a summary
of the results.

PROBLEM NAME: delay

INPUT FORMAT:

* Line 1: Three space-separated integers: N, D, and K

* Line 2: FJ's binary message, containing exactly N bits

SAMPLE INPUT (file delay.in):

4 1 3
0110

OUTPUT FORMAT:

* Line 1: The number of different possible messages that can heard by
Bessie, mod 100,000,000

* Line 2: The K-th smallest such message (in binary representation)

Note that if your program's first line of output is correct but the second
line of output is either missing or wrong, you will receive 40% of the
points for that test case.

SAMPLE OUTPUT (file delay.out):

4
1001

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

Problem 3: Holiday Painting [Brian Hamrick and Neal Wu, 2008]

To show their spirit for the holidays, the cows would like to paint
a picture! Their picture will be represented as an R x C (1 <= R
<= 50,000; 1 <= C <= 15) grid of unit squares, each of which is
either 0 or 1. The grid rows are conveniently numbered 1..R; the
columns are numbered 1..C.

Being pressed for time, the cows have asked their neighbors north
of the border for help. Under the very helpful supervision of Canmuu
the moose, they constructed a machine to throw paint at the picture
in entire buckets! Beginning with all 0's in the picture grid, the
machine splashes a certain paint color (either 0 or 1) over a
rectangle in the grid. In particular, Canmuu suggested that they
perform Q (1 <= Q <= 10,000) operations; operation i consists of
five integers R1_i, R2_i, C1_i, C2_i, and X_i (1 <= R1_i <= R2_i
<= R; 1 <= C1_i <= C2_i <= C; 0 <= X_i <= 1), meaning that the cows
will paint each unit square with a row index between R1_i and R2_i,
inclusive, and a column index between C1_i and C2_i, inclusive,
with color X_i.

However, painting a picture like this is quite prone to mistakes.
So Canmuu has enlisted you to determine, after each operation, the
number of unit squares in the grid which are the correct color.

MEMORY LIMIT: 64 MB

TIME LIMIT: 1.5 seconds

PROBLEM NAME: holpaint

INPUT FORMAT:

* Line 1: Three space-separated integers: R, C, and Q

* Lines 2..R+1: Line i+1 contains C characters, each '0' or '1',
denoting the i-th row of the grid in the obvious way.

* Lines R+2..R+Q+1: Line R+i+1 contains five space-separated integers
representing a paint operation: R1_i, R2_i, C1_i, C2_i, and
X_i

SAMPLE INPUT (file holpaint.in):

17 15 10
111111101111111
111111000111111
111110000011111
111100000001111
111000000000111
111100000001111
111000000000111
110000000000011
111000000000111
110000000000011
100000000000001
110000000000011
100000000000001
000000000000000
111111000111111
111111000111111
111111000111111
5 8 2 14 1
8 17 3 7 1
4 5 10 15 0
7 16 12 14 1
2 17 13 14 0
2 6 2 3 1
13 14 4 8 1
3 6 6 7 1
1 16 10 11 0
7 16 10 10 0

INPUT DETAILS:

The cows want to paint a picture of a holiday tree

OUTPUT FORMAT:

* Lines 1..Q: On line i+1, print a single integer representing the
number of matching unit squares after the i-th operation.

SAMPLE OUTPUT (file holpaint.out):

113
94
95
91
87
93
91
87
93
93

OUTPUT DETAILS:

After the first operation, the picture grid looks as follows:

000000000000000
000000000000000
000000000000000
000000000000000
011111111111110
011111111111110
011111111111110
011111111111110
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000
000000000000000

There are 113 unit squares which match the corresponding square in
the tree image; they are denoted below by an 'x' (the other bits
are shown as they appear after the first paint splash):

0000000x0000000
000000xxx000000
00000xxxxx00000
0000xxxxxxx0000
0xx111111111xx0
0xxx1111111xxx0
0xx111111111xx0
0x11111111111x0
000xxxxxxxxx000
00xxxxxxxxxxx00
0xxxxxxxxxxxxx0
00xxxxxxxxxxx00
0xxxxxxxxxxxxx0
xxxxxxxxxxxxxxx
000000xxx000000
000000xxx000000
000000xxx000000

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

Problem 4: Pearl Bracelet [Richard Peng, 2008]

Bessie received a magic bracelet of a set of the rarest black pearls
for her favorite holiday. Bessie loved the bracelet and marveled
that each pearl contained a small number engraved on it. She noticed
that if you align the the bracelet's pearls in all the possible
ways by bending it around some point (see below), the 'progressive'
sums of the pearls' numbers that have corresponding numbers on the
top and bottom sides of the bracelet never, ever match when compared
using mod M (2 <= M <= 100). 'Progressive' sums are exemplified
below.

Suppose the mod M is 3. Consider a bracelet with N=6 pearls, etched
sequentially with the numbers 0, 1, 0, 2, 1, 0. We'll illustrate
this bracelet with its clasps like this:

>0-1-0-2-1-0<

The six-pearl bracelet can be laid out on the ground in five different
ways so that some pearls 'correspond' to each other (see below).
We can 'progressively' sum-mod-M those pearls that correspond on
the top and also sum-mod-M the corresponding pearls on the bottom,
as shown with ONE-sums, TWO-sums, THREE-sums (and so on when N >
6).

|     THREE-sums         |     TWO-sums      | ONE-sums
--------------+------------------------+-------------------+---------
>0-1-0-2-1 |                        |                   | => 1
| |                        |                   |
>0 |                        |                   | => 0
--------------+------------------------+-------------------+---------
>0-1-0-2 |                        | => 0+2 = 2        | => 2
| |                        |                   |
>0-1 |                        | => 0+1 = 1        | => 1
--------------+------------------------+-------------------+---------
>0-1-0 | => 0+1+0 = 1           | => 1+0 = 1        | => 0
| |                        |                   |
>0-1-2 | => 0+1+2 = 3 mod 3 = 0 | => 1+2 mod 3 = 0  | => 2
--------------+------------------------+-------------------+---------
>0-1 |                        | => 0+1 = 1        | => 1
| |                        |                   |
>0-1-2-0 |                        | => 2+0 = 2        | => 0
--------------+------------------------+-------------------+---------
>0 |                        |                   | => 0
| |                        |                   |
>0-1-2-0-1 |                        |                   | => 1

Bessie notes that all the pairs of sums contain different numbers
and has heard this is true for all the magic bracelets. Bessie
wondered what is longest possible bracelet that has this unique-sum
property.

Given M, find a really long (but no longer than 20,000) set of
numbers can be etched on the black pearls to maintain this unique
sum property for a bracelet.

This is an output-only problem, the 15 input files can be downloaded
at: http://ace.delos.com/perlbrac.zip

SCORING: Scoring for this problem will be relative; your integer
score (out of 10) for each test case will be int (10 * sqrt (YOURS
/ BEST)), where YOURS is the length of your solution, and BEST is
the length of the best solution among all contestants.

FEEDBACK: When you submit a file for grading, it will be checked
for both correct format and validity (i.e., whether it satisfies
the required numerical properties), and you will be informed of the
results.

PROBLEM NAME: perlbrac

INPUT FORMAT:

* Line 1: Two space-separated integers: the case number and M

SAMPLE INPUT (file perlbrac.in):

0 6

OUTPUT FORMAT:

* Line 1: A single line containing the task name and case number:
#FILE perlbrac CASENUM

* Line 2: A single line with a single integer, N (which must be no
larger than 20,000)

* Lines 3..N+1: Line i+2 contains a single integer that is the integer
etched onto the i-th pearl on the bracelet; this number should
be between 0 and M - 1, inclusive

SAMPLE OUTPUT (file perlbrac.out):

#FILE perlbrac 0
6
0
1
0
2
1
0

**********************************************************************```
```
page revision: 0, last edited: 06 Jun 2009 21:31