MMIND  The Game of MasterMind
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 MasterMind, 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 MasterMind 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 G_{i}, 1 <= G_{i} <= 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 S_{1}, S_{2}, ... S_{P} and the guess G_{1}, G_{2}, ... G_{P}. Then we can make a set H containing pairs of numbers (I,J) such that S_{I} = G_{J}, 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, (I_{1},J_{1}) and (I_{2},J_{2}), we have I_{1} <> I_{2} and J_{1} <> J_{2}. 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 H_{1} and H_{2}. Let's say H_{1} <= H_{2} if and only if one of the following holds:
 B(H_{1}) < B(H_{2}), or
 B(H_{1}) = B(H_{2}) and W(H_{1}) <= W(H_{2})
Then we can find a maximal set H_{max} according to this ordering. The numbers B(H_{max}) and W(H_{max}) 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:
 G_{J} = V_{J} for every J<I, and
 G_{I}<V_{I}.
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 9Warning: large Input/Output data, be careful with certain languages
hide comments
Sai Krishna:
20160901 18:05:29
Cows and Bulls game as many call this. 

abhishek27:
20151109 09:29:14
found difficult but finally solved .. 

:D:
20120919 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:
20120615 16:44:56
1 1 1 3 is a feasable guess.


chayan ghosh:
20120210 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:  20040509 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  ACM Central European Programming Contest, Prague 2000 