22331번 - Guess Which Cow 점수다국어인터랙티브

The N (1 ≤ N ≤ 50) cows in Farmer John's herd look very much alike and are numbered 1…N. When Farmer John puts a cow to bed in her stall, he must determine which cow he is putting to bed so he can put her in the correct stall.

Cows are distinguished using P (1 ≤ P ≤ 8) properties, numbered 1…P, each of which has three possible values. For example, the color of a cow's ear tag might be yellow, green, or red. For simplicity, the values of every property are represented as the letters ‘X’, ‘Y’, and ‘Z’. Any pair of Farmer John’s cows will differ in at least one property.

Write a program that, given the properties of the cows in Farmer John's herd, helps Farmer John determine which cow he is putting to bed. Your program can ask Farmer John no more than 100 questions of the form: Is the cow’s value for some property T in some set S? Try to ask as few questions as possible to determine the cow.

• The first line of the input file contains two space-separated integers, N and P.
• Each of the next N lines describes a cow’s properties using P space-separated letters. The first letter on each line is the value of property 1, and so on. The second line in the input file describes cow 1, the third line describes cow 2, etc.

The question/answer phase takes place via standard input and standard output.

Your program asks a question about the cow being put to bed by writing to standard output a line that is a ‘Q’ followed by a space, the property number, a space, and a space-separated set of one or more values. For example, “Q 1 Z Y” means “Does property 1 have value either ‘Z’ or ‘Y’ for the cow being put to bed?”. The property must be an integer in the range 1…P. All values must be ‘X’, ‘Y’, or ‘Z’ and no value should be listed more than once for a single question.

After asking each question your program asks, read a single line containing a single integer. The integer 1 means the value of the specified property of the cow being put to bed is in the set of values given; the integer 0 means it is not.

The program's last line of output should be a ‘C’ followed by a space and a single integer that specifies the cow that your program has determined Farmer John is putting to bed.

Example exchange (for example input above):

Correctness: 30% of points

Programs will receive full score on correctness only if the cow specified is the only cow that is consistent with the answers given. A program that asks more than 100 questions for a test case will receive no points for that test case.

Question count: 70% of points

The remaining points will be determined by the number of questions required to correctly determine the cow. The test cases are designed to reward minimizing the worst-case question count. Partial credit will be given for near-optimal question counts.