Usaco Mar10 Silver

Part of USACO Mar10

**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Three problems numbered 6 through 8
**********************************************************************

Problem 6: The Rock Game [Tom Conerly, 2010]

Before the cows head home for rest and recreation, Farmer John wants
them to get some intellectual stimulation by playing a game.

The game board comprises N (1 <= N <= 15) identical holes in the
ground, all of which are initially empty. A cow moves by either
covering exactly one hole with a rock, or uncovering exactly one
previously covered hole. The game state is defined by which holes
are covered with rocks and which aren't. The goal of the game is
for the cows to reach every possible game state exactly once and
then return to the state with all holes uncovered.

The cows have been having a tough time winning the game.  Below is
an example of one of their games:

       Holes
time   1  2  3 
-----------------
0      O  O  O  Initially all of the holes are empty
1      O  O  X  The cow covers hole 3
2      X  O  X  The cow covers hole 1
3      X  O  O  The cow uncovers hole 3
4      X  X  O  The cow covers hole 2
5      O  X  O  The cow uncovers hole 1
6      O  X  X  The cow covers hole 3
7      X  X  X  The cow covers hole 1

Now the cows are stuck! They must uncover one hole and no matter
which one they uncover they will reach a state they have already
reached. For example if they remove the rock from the second hole
they will reach the state (X O X) which they already visited at
time 2.

Below is an example of a valid solution for N=3 holes:

       Holes
time   1  2  3 
-----------------
0      O  O  O  Initial state: all of the holes are empty
1      O  X  O  The cow covers hole 2
2      O  X  X  The cow covers hole 3
3      O  O  X  The cow uncovers hole 2
4      X  O  X  The cow covers hole 1
5      X  X  X  The cow covers hole 2
6      X  X  O  The cow uncovers hole 3
7      X  O  O  The cow uncovers hole 2
8      O  O  O  The cow uncovers the 1st hole

which returns the game board to the start having, visited each state once.

The cows are tired of the game and want your help. Given N, create
a valid sequence of states that solves the game. If there are
multiple solutions return any one.

PROBLEM NAME: rocks

INPUT FORMAT:

* Line 1: A single integer: N

SAMPLE INPUT (file rocks.in):

3

OUTPUT FORMAT:

* Lines 1..2^N+1: A string of length N containing only 'O' and 'X'
        (where O denotes a uncovered hole and X denotes a covered
        hole). The jth character in this line represents whether the
        jth hole is covered or uncovered in this state. The first and
        last lines must be all uncovered (all O).

SAMPLE OUTPUT (file rocks.out):

OOO
OXO
OXX
OOX
XOX
XXX
XXO
XOO
OOO

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

Problem 7: Test Taking [Tom Conerly, 2010]

Farmer John has to take his annual farming license test. The test
comprises N (1 <= N <= 1,000,000) true/false questions. After FJ's
dismal performance on last year's test Bessie wishes to help him.

Bessie has inside information that the number of questions whose
answer is true will be one of t_1, t_2, t_3,..., or t_K (0 <= t_i
<= N; 0 <= K <= 10,000) -- even though Bessie has no information
about any answer to any specific question. Bessie wants to know the
best score that FJ is guaranteed achieve by exploiting this information
carefully, even if he doesn't know the actual answers to any test
questions.

To demonstrate Bessie's idea, consider a license test with N=6
questions where Bessie knows that the number of questions with the
answer 'true' is either 0 or 3. FJ can always get at least 3 answers
correct using logic like this: If FJ answers 'false' on every
question and there are 0 questions with the answer 'true' then he
will get all 6 correct. If there are 3 questions with the answer
'true' then he will get 3 answers correct. So as long as he marks
every answer as 'false' he is guaranteed to get at least 3 correct
without knowing any answer to the test questions.

On the other hand, consider what happens if FJ chooses an inferior
strategy: he guesses that some 3 answers are 'true' and the other
3 are 'false'. If it turns out that NO answers are 'true' then FJ
will get 3 answers correct, the ones he guessed were false. If 3
answers are 'true' then FJ could get as few as 0 answers correct.
If he answered incorrectly on all 3 of that answers for which he
guessed 'true', and the other 3 (for which he guessed 'false') are
true, then he gets 0 correct answers. Even though FJ could get 3
correct in this case by guessing 'false' every time, he can not
always guarantee even 1 correct by guessing some 3 answers as 'true',
so this strategy can not guarantee getting any answer correct. FJ
should use the previous paragraph's strategy.

Given Bessie's inside information, determine the number of answers
FJ can always get correct using this information assuming he uses
it optimally.

PROBLEM NAME: teststr

INPUT FORMAT:

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

* Lines 2..K+1: Line i+1 contains a single integer: t_i

SAMPLE INPUT (file teststr.in):

6 2
0
3

OUTPUT FORMAT:

* Line 1: A single integer, the best score FJ is guaranteed to achieve

SAMPLE OUTPUT (file teststr.out):

3

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

Problem 8: Need For Speed [Jeffrey Wang, 2007]

Bessie is preparing her race car for the upcoming Grand Prix, but
she wants to buy some extra parts to improve the car's performance.
Her race car currently has mass M (1 <= M <= 1,000) and is able
to push itself forward with a force of F (1 <= F <= 1,000,000).
The Race Car Performance Store has N (1 <= N <= 10,000) parts
conveniently numbered 1..N. Bessie can buy as many or as few parts
as she wishes though the store stocks no more than one instance
of each part.

Part P_i adds force F_i (1 <= F_i <= 1,000,000) and has mass
M_i (1 <= M_i <= 1,000). Newton's Second Law decrees that F =
MA, where F is force, M is mass, and A is acceleration. If Bessie
wants to maximize the total acceleration of her race car (and
minimize the mass otherwise), which extra parts should she choose?

Consider a race car with initial F=1500 and M=100. Four parts are
available for enhancement:

          i  F_i  M_i
          1  250   25
          2  150    9
          3  120    5
          4  200    8

Adding just part 2, e.g., would result in an acceleration of
(1500+150)/(100+9) = 1650/109 = 15.13761.

Below is a chart of showing the acceleration for all possible
combinations of adding/not-adding the four parts (in column one,
1=part added, 0=part not added):

Parts   Aggregate   Aggregate        
1234        F           M       F/M
0000      1500         100    15.0000
0001      1700         108    15.7407
0010      1620         105    15.4286
0011      1820         113    16.1062
0100      1650         109    15.1376
0101      1850         117    15.8120
0110      1770         114    15.5263
0111      1970         122    16.1475 <-- highest F/M
1000      1750         125    14.0000
1001      1950         133    14.6617
1010      1870         130    14.3846
1011      2070         138    15.0000
1100      1900         134    14.1791
1101      2100         142    14.7887
1110      2020         139    14.5324
1111      2220         147    15.1020

Thus, the best additional part combination is parts 2, 3, and 4.

PROBLEM NAME: sboost

INPUT FORMAT:

* Line 1: Three space-separated integers: F, M, and N

* Lines 2..N+1: Line i+1 contains two space separated integers: F_i
        and M_i

SAMPLE INPUT (file sboost.in):

1500 100 4
250 25
150 9
120 5
200 8

OUTPUT FORMAT:

* Lines 1..P: The index values of P extra parts, one per line, that
        Bessie should add to her racecar. If she should not add any,
        output 'NONE' (without quotes). The output should be given in
        increasing order, so if the optimal set of parts is {2,4,6,7},
        then the output should be in the order 2,4,6,7 and not, for
        example, 4,2,7,6. Solutions will be unique.

SAMPLE OUTPUT (file sboost.out):

2
3
4

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