Usaco Mar10 Bronze

Part of USACO Mar10

**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Four problems numbered 11 through 14
**********************************************************************

Problem 11: 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 <= 20) 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: boost

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 boost.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.

SAMPLE OUTPUT (file boost.out):

2
3
4

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

Problem 12: Hexadecimal Conversion [Traditional, 2008]

Bessie was teaching Jessie, her protege interesting in programming
contests the binary facts of life. She explained that computers
work in binary (base 2) and that all computer numbers in general
are stored as 0's and 1's. Jessie was a bit unclear on the concept,
so Bessie made her an exercise, shown below.

Write a program that converts an unsigned hexadecimal number to
octal (base 8) form.  Hexadecimal number can have at most 100,000
digits and is composed of digits and capital letters from A to F.

Note: a hexadecimal number is a special way of representing numbers
in base 16. The digits 0-9 still correspond to 0-9, and then A
(capital A!) corresponds to 10, B to 11, etc. (F stands for 15).

For example, the hexadecimal number A10B corresponds to the (decimal)
number 10*16^3 + 1*16^2 + 0*16^1 + 11*16^0 = 41227. The corresponding
octal (base 8) number would be 120413, since 1*8^5 + 2*8^4 + 0*8^3
+ 4*8^2 + 1*8^1 + 3*8^0 = 41227.

Hint: there is an easier way to convert from hexadecimal to octal than by
converting hexadecimal -> decimal -> octal. It might help to think about
the numbers in binary (base 2).

PROBLEM NAME: hex

INPUT FORMAT:

* Line 1: A single hexadecimal number. Multidigit numbers will have no
        leading zeroes (i.e., A1 instead of 00A1). 0 (by itself) is a
        valid input.

SAMPLE INPUT (file hex.in):

123ABC

OUTPUT FORMAT:

* Line 1: The octal value with no leading zeros.  If the input is 0,
        the output should also be 0.

SAMPLE OUTPUT (file hex.out):

4435274

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

Problem 13: MasterMind [Fatih Gelgi, 2008]

Jessie was learning about programming contests at Bessie's knee.
"Do they play games?" she asked.

"Oh yes," Bessie nodded sagely. "Here's a classic."

MasterMind is a classic two player game. One of the players is the
'codemaker'; she picks a four digit secret number S (1000 <= S <=
9999). The other player is the 'codebreaker' who repeatedly guesses
four digit numbers until she solves the code.

The codemaker provides feedback that comprises two integers for
each codebreaker guess G_i (1000 <= G_i <= 9999). For each codebreaker
guess, the codemaker's feedback comprises two integers:

* The first integer C_i (0 <= C_i <= 4) specifies how many of the
  guess's digits are correct and in their correct location in the
  secret number

* The second integer W_i (0 <= W_i <= 4-C_i) specifies how many of
  the remaining digits (i.e., those not described by C_i) are correct
  but in the wrong location.

For example, suppose codemaker's secret number is 2351. If codebreaker
guesses 1350, the codemaker provides the feedback "2 1", since 3
and 5 are in correct locations in the number, and 1 is in the wrong
location. As another example, if the secret number is 11223 (in a
five-digit version of mastermind) and the guess is 12322, then the
feedback would be "2 2".

Below is a sample game where the secret number is 2351:

        Correct digits in correct location
        | Correct digits in wrong location
Guess   | |
3157    1 2
1350    2 1
6120    0 2
2381    3 0
2351    4 0

For this task, you are given N (1 <= N <= 100) guesses with their
feedback in the middle of a game. You are asked to output the
smallest four digit number which can be a candidate for codemaker's
secret code (i.e., which satisfies all the constraints).

If there are no such numbers, output "NONE" (without the quotes).

PROBLEM NAME: mmind

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains guess i and its two responses
        expressed as three space-separated integers: G_i, C_i, and W_i

SAMPLE INPUT (file mmind.in):

4
3157 1 2
1350 2 1
6120 0 2
2381 3 0

OUTPUT FORMAT:

* Line 1: A single integer that is the smallest four-digit number
        (same range as the secret integer: 1000..9999) which could be
        the secret code. If there are no such numbers, output a single
        line containing the word "NONE" (without quotes).

SAMPLE OUTPUT (file mmind.out):

2351

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

Problem 14: Longest Contiguous Subsequence [Jon Losh, 2010]

Bessie's friend Jessie wanted to enter a programming contest. "What
are the tasks like?" she asked.

Bessie, known to be knowledgeable about so many things, said "Here
is a typical problem that folks solve early in their competitive
career. See if you can solve it."

Perhaps you can solve it, too.

You are given two sequences of integers, S1 and S2. S1 has length
L1 (1 <= L1 <= 180) and S2 has length L2 (1 <= L2 <= 180). Your job
is to print out the length of the longest contiguous subsequence
of numbers common to both S1 and S2. Ordered sequence S1 has elements
S1_1, S1_2, ..., S1_L1 (-100 <= S1_i <= 100); S2 has elements S2_i
(-100 <= S2_i <= 100).

A contiguous subsequence is a consecutive run of numbers in that
sequence. The subsequences of 1 2 3 1 are: the empty sequence, "1",
"1 2", "1 2 3", "1 2 3 4", "2", "2 3", "2 3 1", "3", "3 1", and a
repeat occurrence of "1".

PROBLEM NAME: sub

INPUT FORMAT:

* Line 1: Two space-separated integers: L1 and L2

* Lines 2..L1+1: Line i+1 contains a single integer: S1_i

* Lines L1+2..L1+L2+1: Line L1+i+1 contains a integer: S2_i

SAMPLE INPUT (file sub.in):

10 12
1
1
1
3
2
3
3
3
4
5
1
1
1
1
3
2
3
3
4
4
5
-8

INPUT DETAILS:

Two sequences:
1,1,1,3,2,3,3,3,4,5
1,1,1,1,3,2,3,3,4,4,5,-8

OUTPUT FORMAT:

* Line 1: A single integer, the length of the longest contiguous
        subsequence of S1 and S2

SAMPLE OUTPUT (file sub.out):

7

OUTPUT DETAILS:

Corresponds to the contiguous subsequence 1,1,1,3,2,3,3.

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