Mastermind
Time limit3sMemory limit512 MB
Guess a hidden 4-digit sequence over six colors using at most K red/white feedback queries per game, for T games.
- Level
Medium7 of 10
- Topics
- Brute force, Simulation, Implementation, Combinatorics
- Solved
- No attempts yet
Problem
Let us play a game of Mastermind against the grader.
Mastermind is a game where you determine the colors and order of four balls chosen by the grader. There are six ball colors, represented by the natural numbers 1 through 6. To determine the colors and order of the balls, you must ask the grader questions. For convenience, the colors and order of the balls chosen by the grader are represented by a sequence A.
When you ask the grader about a sequence B, the grader tells you the number of red pins and the number of white pins. The number of red pins is the number of balls whose position and color both match, and the number of white pins is the number of balls whose color matches but whose position differs.
In one game you may ask K questions, and you must determine A by asking the grader at most K questions.
Input
The Sample Grader reads the following information from Standard Input.
The first line gives T and K. The following T lines each give one sequence A, the colors and order of the balls chosen by the grader.
Output
The Sample Grader writes the following information to Standard Output.
If you have correctly determined the number the grader had in mind in all T games, output "AC"; otherwise output "WA".
Constraints
- 1 ≤ T ≤ 100
- 5 ≤ K ≤ 12