G. Guess One Character
constructive algorithms; implementation; interactive
This is an interactive problem. You have to use flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout) or cout.flush(), in Java or Kotlin — System.out.flush(), and in Python — sys.stdout.flush().The jury has a string \(s\) consisting of characters 0 and/or 1. The length of this string is \(n\). You can ask the following queries: \(1\) \(t\) — ""how many times does \(t\) appear in \(s\) as a contiguous substring?"" Here, \(t\) should be a string consisting of characters 0 and/or 1; its length should be at least \(1\) and at most \(n\). For example, if the string \(s\) is 111011 and the string \(t\) is 11, the response to the query is \(3\). You have to guess at least one character in the string \(s\) by asking no more than \(3\) queries. Note that giving the answer does not count as a query.In every test and in every test case, the string \(s\) is fixed beforehand.
In the example, there are \(3\) test cases: 101, 11 and 10. Note that everything after the // sign is a comment that explains which line means what in the interaction. The jury program won't print these comments in the actual problem, and you shouldn't print them. The empty lines are also added for your convenience, the jury program won't print them, and your solution should not print any empty lines.