eolymp
bolt
Try our new interface for solving problems
Problems

Politicians and Competitive Programmers

Politicians and Competitive Programmers

\textbf{This is an interactive problem} There are $n$ citizens in SmartLand, numbered from $0$ to $n-1$. Surprisingly, each of them is either politician or a competitive programmer (but not both), and everyone in the SmartLand knows who the others are. Of course, competitive programmers always tell truth and politicians always lie. You want to determine, for each citizen of SmartLand, whether he is a politician or a competitive programmer. To do this, you can do the following: \begin{itemize} \item Choose three \textbf{distinct} citizens $X$, $Y$, $Z$, and ask $X$ the following question: ``Is it true that $Y$ would answer ``Yes'' to the question ``Is $Z$ competitive programmer?'''' \end{itemize} However, there is an important constraint: \textbf{You can't ask the same citizen twice.} That is, each citizen can be chosen as $X$ at most once. Determine for each citizen, whether they are competitive programmers or politicians. \Interaction Start by reading an integer $n$ ($5 \le n \le 1000$) --- the number of citizens of SmartLand. To ask the question, output: \t{?} $X$ $Y$ $Z$ Here $X$, $Y$, $Z$ must be distinct integers with $0 \le X, Y, Z \le n-1$, and $X$ couldn't have been asked questions before. In response, the interactor will output $1$, if $X$ answers ``Yes'', and $0$ otherwise. When you want to output answer, output: \t{!} $s$ Here $s$ is a binary string of length $n$, and $s_i$ should be $1$, if citizen $i$ is competitive programmer, and $0$ 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 \t{Wrong Answer}. After printing a query do not forget to output the end of the line and flush the output. Otherwise, you will get \t{Idleness limit exceeded} verdict. To do this, use: \begin{itemize} \item \t{fflush(stdout)} or \t{cout.flush()} in C++; \item \t{System.out.flush()} in Java; \item \t{stdout.flush()} in Python; \end{itemize} It is guaranteed that the roles of all citizens are fixed before the start of the interaction. In other words, \textbf{the interactor is not adaptive}. \Note In the sample, citizens $0$, $1$, $2$, $3$ are competitive programmers, and citizen $4$ 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...
Time limit 1 second
Memory limit 256 MiB
Input example #1
4
5
11110
Output example #1
Author Anton Trygub
Source All-Ukrainian Collegiate Programming Contest 2021-2022, II stage