MMIND - The Game of Master-Mind

no tags 

If you want to buy a new cellular phone, there are many various types to choose from. To decide which one is the best for you, you have to consider several important things: its size and weight, battery capacity, WAP support, colour, price. One of the most important things is also the list of games the phone provides. Nokia is one of the most successful phone makers because of its famous Snake and Snake II. ACM wants to make and sell its own phone and they need to program several games for it. One of them is Master-Mind, the famous board logical game.

The game is played between two players. One of them chooses a secret code consisting of P ordered pins, each of them having one of the predefined set of C colours. The goal of the second player is to guess that secret sequence of colours. Some colours may not appear in the code, some colours may appear more than once.

The player makes guesses, which are formed in the same way as the secret code. After each guess, he/she is provided with an information on how successful the guess was. This feedback is called a hint. Each hint consists of B black points and W white points. The black point stands for every pin that was guessed right, i.e. the right colour was put on the right position. The white point means right colour but on the wrong position. For example, if the secret code is "white, yellow, red, blue, white" and the guess was "white, red, white, white, blue", the hint would consist of one black point (for the white on the first position) and three white points (for the other white, red and blue colours). The goal is to guess the sequence with the minimal number of hints.

The new ACM phone should have the possibility to play both roles. It can make the secret code and give hints, but it can also make its own guesses. Your goal is to write a program for the latter case, that means a program that makes Master-Mind guesses.

Input

There is a single positive integer T on the first line of input. It stands for the number of test cases to follow. Each test case describes one game situation and you are to make a guess. On the first line of each test case, there are three integer numbers, P, C and M. P ( 1 <= P <= 10) is the number of pins, C (1 <= C <= 100) is the number of colours, and M (1 <= M <= 100) is the number of already played guesses.

Then there are 2 x M lines, two lines for every guess. At the first line of each guess, there are P integer numbers representing colours of the guess. Each colour is represented by a number Gi, 1 <= Gi <= C. The second line contains two integer numbers, B and W, stating for the number of black and white points given by the corresponding hint.

Let's have a secret code S1, S2, ... SP and the guess G1, G2, ... GP. Then we can make a set H containing pairs of numbers (I,J) such that SI = GJ, and that any number can appear at most once on the first position and at most once on the second position. That means for every two different pairs from that set, (I1,J1) and (I2,J2), we have I1 <> I2 and J1 <> J2. Then we denote B(H) the number of pairs in the set, that meet the condition I = J, and W(H) the number of pairs with I <> J.

We define an ordering of every two possible sets H1 and H2. Let's say H1 <= H2 if and only if one of the following holds:

  • B(H1) < B(H2), or
  • B(H1) = B(H2) and W(H1) <= W(H2)

Then we can find a maximal set Hmax according to this ordering. The numbers B(Hmax) and W(Hmax) are the black and white points for that hint.

Output

For every test case, print the line containing P numbers representing P colours of the next guess. Your guess must be valid according to all previous guesses and hints. The guess is valid if the sequence could be a secret code, i.e. the sequence was not eliminated by previous guesses and hints.

If there is no valid guess possible, output the sentence You are cheating!. If there are more valid guesses, output the one that is lexicographically smallest. I.e. find such guess G that for every other valid guess V there exists such a number I that:

  • GJ = VJ for every J<I, and
  • GI<VI.

Example

Sample Input:

3
4 3 2
1 2 3 2
1 1
2 1 3 2
1 1
4 6 2
3 3 3 3
3 0
4 4 4 4
2 0
8 9 3
1 2 3 4 5 6 7 8
0 0
2 3 4 5 6 7 8 9
1 0
3 4 5 6 7 8 9 9
2 0

Sample Output

1 1 1 3
You are cheating!
9 9 9 9 9 9 9 9
Warning: large Input/Output data, be careful with certain languages

hide comments
Sai Krishna: 2016-09-01 18:05:29

Cows and Bulls game as many call this.

abhishek27: 2015-11-09 09:29:14

found difficult but finally solved ..

:D: 2012-09-19 17:00:22

You should look for an efficient heuristics rather than an solution running optimally in pessimistic case. Try to think of some brute force and optimize from there. My program is fastest ex aequo with Lixupeng (at the time of writing) and it would completely fail for some hard cases. Especially for high C, there would be some serious problems, but in actual data it's pretty low (something like C<=10).

Andrew Smith: 2012-06-15 16:44:56

1 1 1 3 is a feasable guess.
In both hints, the White pin referes to the 3 which is the right color but wrong position. The black pin refers to the 1 which, in eithr hint, is still in the correct place. However,
3 3 3 1 is also valid, but I believe that 1 1 1 3 is lexicographically the smallest.

chayan ghosh: 2012-02-10 18:13:59

for d first test case the only feasible guess left is 3 3 3 1... and definitely 1 1 1 3 is not a feasible one. :)


Added by:adrian
Date:2004-05-09
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:ACM Central European Programming Contest, Prague 2000