Not an official ACM page
[1996 North-Central Regional problem set | My ACM problem archive | my home page]

1996 ACM North Central Programming Contest
November 9, 1996

Problem G -- "Cheapest" Scores

Many games have scores associated with different types of events, and the overall score is just the sum of the these individual event scores. Take, for example, a hypothetical game called Dunking. In this game, you can earn 2 points for a douser and 7 points for a bucket. Immediately after a douser you can score an additional 3 points for a soaker, or an additional 6 points for a gusher. Note that you cannot get points for a soaker or a gusher by themselves. Additionally, immediately following a soaker you can get an additional point for a spray. The table below gives all the scoring possibilities for Dunking: 
Total Points | Event Sequence
-------------|----------------
     2       | A douser
     5       | A douser, then a soaker
     8       | A douser, then a gusher
     6       | A douser, then a soaker, then a spray
     7       | A bucket
Note:
An event sequence is defined as a number of consecutive scoring events in which all but the first have a prerequisite event. For example, a douser/soaker/spray combination is one event sequence, but three dousers in a row are three separate event sequences.

Given a particular score, what is the smallest number of event sequences which will achieve that score? For Dunking, some scores are impossible (like 1 and 3). Others can be obtained in several ways--to get 8 points you could score one douser/gusher, a douser/soaker/spray and a "stand-alone" douser, or four dousers. The one douser/gusher is the optimum way to achieve 8 points, since it requires only one "event sequence". In this problem you will be presented with the scoring schemes for multiple games, and for each scheme, a set of potential scores to be analyzed. For each game and score, you are to determine if that score can be achieved, and if it can, the optimal manner in which it can be achieved. Optimal, again, means achieving the score with the smallest number of event sequences.

Input

Each game's scoring scheme will begin with a line containing an integer N identifying the number of scoring events that are possible for that game. The next N lines will contain the event name (case significant, but no more than 16 characters), the integer score associated with that event, and the name of an event that must immediately precede it in the game, if required. These items will be separated by whitespace (blanks and/or tabs). A value of zero for N marks the end of the input data.

Following each scoring scheme will be a sequence of integers, each giving a potential score. This sequence will terminate with zero, which is not to be treated as a potential score.

Output

For each game/score pair, print a heading line similar to that shown in the output shown below; it includes the game number (starting with 1), a period, the score number (starting with 1 for each game), and the score in parentheses. On the following lines print the number of each type of scoring event required to obtain the specified score, and the number of points achieved by completing those events (in parentheses), or a message indicating the score is impossible. Display a blank line after the output for each game/score pair.

Sample Input

5
douser      2
soaker      3     douser
spray 1	    soaker
gusher      6     douser
bucket      7
1
2
4
5
6
7
8
9
0
4

foul 0
freeshot 1 foul
goal 2
whopper 4
1
2
3
4
5
0

0

Sample Output

Case 1.1 (1):
      This score is impossible.

Case 1.2 (2):
      1 douser (2)

Case 1.3 (4):
      2 dousers (4)

Case 1.4 (5):
      1 douser (2)
      1 soaker (3)

Case 1.5 (6):
      1 douser (2)
      1 soaker (3)
      1 spray (1)

Case 1.6 (7):
      1 bucket (7)

Case 1.7 (8):
      1 douser (2)
      1 gusher (6)

Case 1.8 (9):
      1 douser (2)
      1 bucket (7)

Case 2.1 (1):
      1 foul (0)
      1 freeshot (1)

Case 2.2 (2):
      1 goal (2)

Case 2.3 (3):
      1 foul (0)
      1 freeshot (1)
      1 goal (2)

Case 2.4 (4):
      1 whopper (4)

Case 2.5 (5):
      1 foul (0)
      1 freeshot (1)
      1 whopper (4)

Judge's Input Data

This page maintained by Ed Karrels.
Last updated September 20, 1999