Mathtermind

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types

Mathtermind is a game where you try to guess 3 unique numbers (the winning combination) chosen by the game out of a set of numbers from 1 to 15. There are at most 7 rounds played. For each of these rounds, you guess 1 to 4 unique numbers. The game will then tell you that M numbers of your guess match its winning combination.

After guessing R rounds, you would like to know your chances of winning. Given the current game state, if a winning combination exists and you can determine what it is with 100\% certainty, output that combination in sorted order. If a winning combination exists but you can't determine what it is with 100\% certainty then output the number of possible winning combinations. Lastly, if a winning combination does not exist output -1.

Input Specification

The first line of the input will contain an integer R (1 \le R \le 7), the number of rounds.

The next 2R lines will alternate between the following:

A line containing N (1 \le N \le 4), the number of guesses, and M (0 \le M \le 3), the number of those guesses that match the winning combination.

A line containing N integers G_i (1 \le G_i \le 15), the numbers of your guess.

Output Specification

Output either the winning combination in sorted order, the number of possible winning combinations, or -1 depending on the input.

Sample Input 1

7
4 2
1 2 3 4
3 1
2 7 8
4 0
9 10 11 12
3 0
13 14 15
3 2
3 7 8
2 0
4 8
1 1
1

Sample Output 1

1 3 7

Explanation for Sample Output 1

The number of numbers in your guess that match the winning combination is denoted by >>.

#1: 1, 2, 3, 4
>> 2
#2: 2, 7, 8
>> 1
#3: 9, 10, 11, 12
>> 0
#4: 13, 14, 15
>> 0
#5: 3, 7, 8
>> 2
#6: 4, 8
>> 0
#7: 1
>> 1

For some guesses, the amount of numbers that match the winning combination is 0, meaning that those numbers can be eliminated, so the numbers 4, 8, 9, 10, 11, 12, 13, 14, and 15 are not part of the winning combination.

#1: 1, 2, 3
>> 2
#2: 2, 7
>> 1
#5: 3, 7
>> 2
#7: 1
>> 1

By using guesses #5 and #7, you can figure out that the winning combination is 1, 3, 7.

Sample Input 2

4
4 2
1 3 5 7
3 1
9 10 14
3 1
1 3 9
1 0
7

Sample Output 2

4

Explanation for Sample Output 2

The possible winning combinations are 1, 5, 10, 1, 5, 14, 3, 5, 10, and 3, 5, 14.

Sample Input 3

3
4 3
1 2 3 4
2 2
5 6
1 2
8

Sample Output 3

-1

Explanation for Sample Output 3

These 3 guesses imply that 6 numbers should appear in the winning combination with 8 appearing twice. This is not true because the winning combination can only consist of 3 distinct numbers from 1 to 15.


Comments

There are no comments at the moment.