Source file: | shut.{c, cpp, java} |
Input file: | shut.in |
Shut the Box is a one-player game that begins with a set of N pieces labeled from 1 to N. All pieces are initially "unmarked" (in the picture at right, the unmarked pieces are those in an upward position). In the version we consider, a player is allowed up to T turns, with each turn defined by an independently chosen value V (typically determined by rolling one or more dice). During a turn, the player must designate a set of currently unmarked pieces whose numeric labels add precisely to V, and mark them. The game continues either until the player runs out of turns, or until a single turn when it becomes impossible to find a set of unmarked pieces summing to the designated value V (in which case it and all further turns are forfeited). The goal is to mark as many pieces as possible; marking all pieces is known as "shutting the box." Your goal is to determine the maximum number of pieces that can be marked by a fixed sequence of turns.
As an example, consider a game with 6 pieces and the
following sequence of turns:
Hint: avoid enormous arrays or lists, if possible.
Input: Each game begins with a line containing
two integers, N, T where
1 ≤ N ≤ 22 represents the
number of pieces, and
1 ≤ T ≤ N
represents the maximum number of turns that will be allowed.
The following line contains T integers designating
the sequence of turn values for the game; each such
value V will satisify 1 ≤ V ≤ 22.
You must read that
entire sequence from the input, even though a particular game
might end on an unsuccessful turn prior to the end of the sequence.
The data set ends with a line containing
Output: You should output a single line for each game, as shown below, reporting the ordinal for the game and the maximum number of pieces that can be marked during that game.
Example input: | Example output: |
6 4 10 3 4 2 6 5 10 2 4 5 3 10 10 1 1 3 4 5 6 7 8 9 10 22 22 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 | Game 1: 4 Game 2: 6 Game 3: 1 Game 4: 22 |