RPGAMES - Roll Playing Games

no tags 

Phil Kropotnik is a game maker, and one common problem he runs into is determining the set of dice to use in a game. In many current games, non-traditional dice are often required, that is, dice with more or fewer sides than the traditional 6-sided cube. Typically, Phil will pick random values for all but the last die, then try to determine specific values to put on the last die so that certain sums can be rolled with certain probabilities (actually, instead of dealing with probabilities, Phil just deals with the total number of different ways a given sum can be obtained by rolling all the dice). Currently he makes this determination by hand, but needless to say he would love to see this process automated. That is your task.

For example, suppose Phil starts with a 4-sided die with face values 1, 10, 15, and 20 and he wishes to determine how to label a 5-sided die so that there are a) 3 ways to obtain a sum of 2, b) 1 way to obtain a sum of 3, c) 3 ways to obtain 11, d) 4 ways to obtain 16, and e)1 way to obtain 26. To get these results he should label the faces of his 5-sided die with the values 1, 1, 1, 2, and 6. (For instance, the sum 16 may be obtained as 10 +6 or as 15 +1, with three different “1” faces to choose from on the second die, for a total of 4 different ways.) Note that he sometimes only cares about a subset of the sums reachable by rolling all the dices (like in the previous example).


Input will consist of multiple input sets. Each input set will start with a single line containing an integer n indicating the number of dice that are already specified. Each of the next n lines describes one of these dice. Each of these lines will start with an integer f (indicating the number of faces on the die) followed by f integers indicating the value of each face. The last line of each problem instance will have the form

r m v1 c1 v2 c2 v3 c3 ··· vm cm

where r is the number of faces required on the unspecified die, m is the number of sums of interest, v1,...,vsm are these sums, and c1,...,cm are the counts of the desired number of different ways in which to achieve each of the respective sums.

Input values will satisfy the following constraints: 1 ≤ n ≤ 20, 3 ≤ f ≤ 20, 1 ≤ m ≤ 10, and 1 ≤ r ≤ 6. Values on the faces of all dice, both the specified ones and the unknown die, will be integers in the range 1 ...50, and values for the vi’s and ci’s are all non-negative and are strictly less than the maximum value of a 32-bit signed integer.

The last input set is followed by a line containing a single 0; it should not be processed.


For each input set, output a single line containing either the phrase “Final die face values are” followed by the r face values in non-descending order, or the phrase “Impossible” if no die can be found meeting the specifications of the problem. If there are multiple dice which will solve the problem, choose the one whose lowest face value is the smallest; if there is still a tie, choose the one whose second-lowest face value is smallest, etc.



4 1 10 15 20
5 5 2 3 3 1 11 3 16 4 26 1
6 1 2 3 4 5 6
6 3 7 6 2 1 13 1
6 1 2 3 4 5 6
4 1 2 2 3
3 3 7 9
8 1 4 5 9 23 24 30 38
4 4 48 57 51 37 56 31 63 11


Final die face values are 1 1 1 2 6
Final die face values are 3 7 9 9

hide comments
tobi303: 2017-02-21 12:03:54

I am non native english speaker, so I am not sure, but doesnt "non-descending order" just mean that they are not ordered in descending order? Shouldnt it be "ascending order" instead? Isnt 3 5 4 2 7 non-descending?

Danilo: 2012-04-23 11:22:20

thanks you Adrian. :)

Adrian Kuegel: 2012-04-23 10:48:41

@Danilo: watch for overflow

Danilo: 2012-04-20 22:06:58

Hi, I would appreciate some tip about my code, what is the problem, does it output solution where there are no solution, or vice versa... thanks

Patrick Klitzke: 2012-04-19 15:28:11

o. k. thanks, i had a bug in it. Try to reset every variable for every test case :).

Adrian Kuegel: 2012-04-19 14:35:01

I took a quick look at your output, you have once a case where you print "Impossible" which has a solution, and one time it is the other way round

Patrick Klitzke: 2012-04-19 11:34:30

are there any special tricks to get accepted, i think my optimations are correct and I care about big numbers, too.

Adrian Kuegel: 2012-04-17 12:38:35

thanks, you are right, that was wrong. I had asserts for all constraints in my program, but unfortunately I had 1 <= r as constraint check. I changed the problem description accordingly, so now values for r between 1 and 3 are allowed, too.

Ugljesa Stojanovic: 2012-04-17 08:56:06

4 ≤ r isn't true

Last edit: 2014-04-15 18:44:43
Adrian Kuegel: 2012-04-17 08:56:06

Please read carefully. It says, that maybe he does not care for certain sums reachable with the dice. So he only cares about a subset of the reachable numbers. But for each number that he cares about, there should be exactly that number of possibilities that he wants!

Added by:Adrian Kuegel
Time limit:1.918s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:ACM East Central North America Regional Programming Contest 2004