Politicians and Programmers#10819
This is an interactive problem
There are citizens in SmartLand, numbered from to n-1. Surprisingly, each of them is either a politician or a programmer (but not both), and everyone in the SmartLand knows who the others are. Of course, programmers always tell the truth and politicians always lie.
You want to determine, for each citizen of SmartLand, whether he is a politician or a programmer. To do this, you can do the following:
Choose three distinct citizens , , , and ask the following question: "Is it true that would answer "Yes" to the question "Is programmer?""
However, there is an important constraint: You can't ask the same citizen twice. That is, each citizen can be chosen as at most once.
Determine for each citizen, whether they are programmers or politicians.
Start by reading an integer (5 \le n \le 1000) — the number of citizens of SmartLand.
To ask the question, output:
?
Here , , must be distinct integers with 0 \le X, Y, Z \le n-1, and must not have been asked before.
In response, the interactor will output , if answers "Yes", and otherwise.
When you want to output answer, output:
!
Here is a binary string of length , and s_i should be , if citizen is programmer, and if he is politician.
Make sure to exit immediately to avoid getting other verdicts.
If you ask the invalid query, you will receive a verdict Wrong Answer.
After printing a query do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded verdict.
To do this, use:
fflush(stdout) or cout.flush() in C++;
System.out.flush() in Java;
stdout.flush() in Python;
It is guaranteed that the roles of all citizens are fixed before the start of the interaction. In other words, the interactor is not adaptive.
Example 1
In the sample, citizens , , , are programmers, and citizen is politician.
Note that the queries in the sample are not sufficient to determine who each citizen is, but nobody forbids you to answer anyways...