Usaco Dec07 Bronze

Part of USACO Dec07

**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Three problems numbered 11 through 13
**********************************************************************

Problem 11: Bookshelf [Neal Wu, 2007]

Farmer John recently bought a bookshelf for cow library, but the
shelf is getting filled up quite quickly, and now the only available
space is at the top.

Each of the N cows (1 <= N <= 20,000) has some height of H_i (1 <=
H_i <= 10,000) and a total height summed across all N cows of S.
The bookshelf has a height of B (1 <= B <= S < 2,000,000,007).

To reach the top of the bookshelf taller than the tallest cow, one
or more of the cows can stand on top of each other in a stack, so
that their total height is the sum of each of their individual
heights. This total height must be no less than the height of the
bookshelf. Since more cows than necessary in the stack can be
dangerous, your job is to find the set of cows that produces a stack
of the smallest number of cows possible such that the stack can
reach the bookshelf.

PROBLEM NAME: shelf

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains a single integer: H_i

SAMPLE INPUT (file shelf.in):

6 40
6
18
11
13
19
11

INPUT DETAILS:

Six cows; bookshelf height 40. Cow heights fall in the range 6..19.

OUTPUT FORMAT:

* Line 1: A single integer representing the size of the smallest set
        of cows that can reach the bookshelf.

SAMPLE OUTPUT (file shelf.out):

3

OUTPUT DETAILS:

One way to reach 40 with 3 cows is 18+11+13; many others exist

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

Problem 12: Bookshelf 2 [Neal Wu, 2007]

Farmer John recently bought another bookshelf for the cow library,
but the shelf is getting filled up quite quickly, and now the only
available space is at the top.

FJ has N cows (1 <= N <= 20) each with some height of H_i (1 <= H_i
<= 1,000,000 - these are very tall cows). The bookshelf has a height
of B (1 <= B <= S, where S is the sum of the heights of all cows).

To reach the top of the bookshelf, one or more of the cows can stand
on top of each other in a stack, so that their total height is the
sum of each of their individual heights. This total height must be
no less than the height of the bookshelf in order for the cows to
reach the top.

Since a taller stack of cows than necessary can be dangerous, your
job is to find the set of cows that produces a stack of the smallest
height possible such that the stack can reach the bookshelf. Your
program should print the minimal 'excess' height between the optimal
stack of cows and the bookshelf.

PROBLEM NAME: shelf2

INPUT FORMAT:

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

* Lines 2..N+1: Line i+1 contains a single integer: H_i

SAMPLE INPUT (file shelf2.in):

5 16
3
1
3
5
6

OUTPUT FORMAT:

* Line 1: A single integer representing the (non-negative) difference
        between the total height of the optimal set of cows and the
        height of the shelf.

SAMPLE OUTPUT (file shelf2.out):

1

OUTPUT DETAILS:

Here we use cows 1, 3, 4, and 5, for a total height of 3 + 3 + 5 + 6 = 17.
It is not possible to obtain a total height of 16, so the answer is 1.

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

Problem 13: Card Stacking [Jeffrey Wang, 2007]

Bessie is playing a card game with her N-1 (2 <= N <= 100) cow
friends using a deck with K (N <= K <= 100,000; K is a multiple of
N) cards.  The deck contains M = K/N "good" cards and K-M "bad"
cards. Bessie is the dealer and, naturally, wants to deal herself
all of the "good" cards. She loves winning.

Her friends suspect that she will cheat, though, so they devise a
dealing system in an attempt to prevent Bessie from cheating. They
tell her to deal as follows:

   1. Start by dealing the card on the top of the deck to the cow
      to her right

   2. Every time she deals a card, she must place the next P (1 <=
      P <= 10) cards on the bottom of the deck; and

   3. Continue dealing in this manner to each player sequentially
      in a counterclockwise manner

Bessie, desperate to win, asks you to help her figure out where she
should put the "good" cards so that she gets all of them. Notationally,
the top card is card #1, next card is #2, and so on.

PROBLEM NAME: cheat

INPUT FORMAT:

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

SAMPLE INPUT (file cheat.in):

3 9 2

INPUT DETAILS:

Bessie is playing cards with two cow friends and a deck of 9 cards.
She must place two cards on the bottom of the deck each time she
deals one.

OUTPUT FORMAT:

* Lines 1..M: Positions from top in ascending order in which Bessie
        should place "good" cards, such that when dealt, Bessie will
        obtain all good cards.

SAMPLE OUTPUT (file cheat.out):

3
7
8

OUTPUT DETAILS:

Bessie should put the "good" cards in positions 3, 7, and 8. The
cards will be dealt as follows; the card numbers are "position in
original deck":
                                      Card Deck         P1      P2    Bessie
 Initial configuration           1 2 3 4 5 6 7 8 9  - - -   - - -   - - -
 Deal top card [1] to Player 1   2 3 4 5 6 7 8 9    1 - -   - - -   - - -
 Top card to bottom (#1 of 2)    3 4 5 6 7 8 9 2    1 - -   - - -   - - -
 Top card to bottom (#2 of 2)    4 5 6 7 8 9 2 3    1 - -   - - -   - - -
 Deal top card [4] to Player 2   5 6 7 8 9 2 3      1 - -   4 - -   - - -
 Top card to bottom (#1 of 2)    6 7 8 9 2 3 5      1 - -   4 - -   - - -
 Top card to bottom (#2 of 2)    7 8 9 2 3 5 6      1 - -   4 - -   - - -
 Deal top card [7] to Bessie     8 9 2 3 5 6        1 - -   4 - -   7 - -
 Top card to bottom (#1 of 2)    9 2 3 5 6 8        1 - -   4 - -   7 - -
 Top card to bottom (#2 of 2)    2 3 5 6 8 9        1 - -   4 - -   7 - -
 Deal top card [2] to Player 1   3 5 6 8 9          1 2 -   4 - -   7 - -
 Top card to bottom (#1 of 2)    5 6 8 9 3          1 2 -   4 - -   7 - -
 Top card to bottom (#2 of 2)    6 8 9 3 5          1 2 -   4 - -   7 - -
 Deal top card [6] to Player 2   8 9 3 5            1 2 -   4 6 -   7 - -
 Top card to bottom (#1 of 2)    9 3 5 8            1 2 -   4 6 -   7 - -
 Top card to bottom (#2 of 2)    3 5 8 9            1 2 -   4 6 -   7 - -
 Deal top card [3] to Bessie     5 8 9              1 2 -   4 6 -   7 3 -
 Top card to bottom (#1 of 2)    8 9 5              1 2 -   4 6 -   7 3 -
 Top card to bottom (#2 of 2)    9 5 8              1 2 -   4 6 -   7 3 -
 Deal top card [9] to Player 1   5 8                1 2 9   4 6 -   7 3 -
 Top card to bottom (#1 of 2)    8 5                1 2 9   4 6 -   7 3 -
 Top card to bottom (#2 of 2)    5 8                1 2 9   4 6 -   7 3 -
 Deal top card [5] to Player 2   8                  1 2 9   4 6 5   7 3 -
 Top card to bottom (#1 of 2)    8                  1 2 9   4 6 5   7 3 -
 Top card to bottom (#1 of 2)    8                  1 2 9   4 6 5   7 3 -
 Deal top card [8] to Bessie     -                  1 2 9   4 6 5   7 3 8

Bessie will end up with the "good cards" that have been placed in
positions 3, 7, and 8 in the original deck.

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