У Томаса есть массив целых чисел $$$a_1,~\ldots,~a_n$$$, все элементы которого различны и находятся в промежутке от $$$0$$$ до $$$n$$$. Как можно заметить, одного из чисел от $$$0$$$ до $$$n$$$ нет в этом массиве.
Вам нужно найти это число. Вы можете не более $$$2 \cdot n + 19$$$ раз спросить, чему равен $$$b$$$-й бит числа $$$a_i$$$.
Это интерактивная задача. Ваша программа должна общаться с программой жюри, используя для этого стандартные потоки ввода и вывода.
В самом начале вашей программе сообщается целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — размер массива.
После этого вы можете сделать не более $$$2 \cdot n + 19$$$ запросов. Чтобы сделать запрос, выведите символ «?», а затем через пробел числа $$$i$$$ и $$$b$$$ ($$$1 \le i \le n, 0 \le b \le \log_{2}n$$$) — индекс $$$i$$$ в массиве и номер бита, который вы хотите узнать. Биты нумеруются с нуля, начиная с младшего.
В ответ на такой запрос сообщается число $$$0$$$ или $$$1$$$ — значение $$$b$$$-го бита числа $$$a_i$$$.
Как только вы определите недостающее в массиве число, выведите символ «!», а затем через пробел это число. После этого ваша программа должна завершиться.
3 0 1 0
? 1 1 ? 2 0 ? 3 1 ! 2
Обратите внимание, что каждое выведенное вами сообщение должно завершаться переводом строки. Также после вывода каждого сообщения ваша программа должна очищать потоковый буфер, чтобы выведенная вами информация дошла до программы жюри: например, это делают вызовы «fflush(stdout)» или «cout.flush()» в C++, «System.out.flush()» в Java, «Console.Out.Flush()» в C#, «flush(output)» в Pascal, «sys.stdout.flush()» в Python.
Пустые строки в примере приведены лишь для удобства, чтобы было лучше понятно, в каком порядке выводятся сообщения. При решении задачи вам не нужно выводить пустые строки, и программа жюри тоже не будет выводить пустые строки.
Название |
---|