NumberGuess
SRM 119 · 2002-11-07 · by axchma
SRM 119 · 2002-11-07 · by axchma
Problem Statement
Problem Statement
You are watching two children playing a number game. Aaron thinks of a number
between 1 and 8 inclusive. Kate needs to guess this number by asking yes or no
questions. You know that Aaron may give a wrong answer, but not more than one
wrong answer per round.
Your task is, given Kate's questions and Aaron's answers over the course of a single round, return the number Aaron
thought of, or one of the two
In more detail:
- the answers are in the same order as the questions
- Kate's questions are presented as a list of numbers separated by spaces. For example, if Kate asks: "Is this number more than 5?", this question is translated to the form: "Is this number from the set {6, 7, 8}?" and the input String would list the set in ascending order: "6 7 8"
- Aaron's answer is always either "YES" or "NO"
- return "CONTRADICTION" when the answers contradict the fact that Aaron lies not more than once (see examples)
- return "NOT ENOUGH INFO" when Aaron's number is not uniquely determined, and there is no contradiction
- in all other cases return the number Aaron thought of
Constraints
- questions has between 1 and 10 elements inclusive
- answers must contain the same number of elements as questions
- each element of questions has between 1 and 15 characters inclusive
- each element of questions consists of digits between 1 and 8 inclusive and spaces
- each element of questions starts and ends with a digit
- each element of questions doesn't have two spaces or two digits in a row
- digits in an element of questions are distinct and in ascending order
- each element of answers is either "YES" or "NO"
Examples
0)
{"1 2 3"}
{"YES"}
Returns: "NOT ENOUGH INFO"
1)
{"1 2 3","1 2 3","1 2 3","1 2 3"}
{"YES","NO","YES","NO"}
Returns: "CONTRADICTION"
2)
{"1","1"}
{"YES","YES"}
Returns: "1"
3)
{"1 2 3 4","1 2","1","1 3"}
{"YES","YES","YES","YES"}
Returns: "1"
4)
{"1 2 3 4","1 2","1"}
{"YES","YES","YES"}
Returns: "NOT ENOUGH INFO"
as Aaron could have thought of 1 and given all true answers or he could have thought of 2, and lied on the last answer
16)
{"8","5","2 7","2 6 8","5 7","3 7","4 8","5","4","3 4 5"}
{"YES","NO","NO","NO","NO","NO","NO","NO","NO","NO"}
Returns: "1"
Well, half of this is random garbage....
Submissions are judged against all 22 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NumberGuess with a public method string answer(vector<string> questions, vector<string> answers) · 22 test cases · 2 s / 256 MB per case