Codeforces Round 846 (Div. 2) |
---|
Закончено |
Это интерактивная задача.
Кира загадал некое положительное целое число $$$n$$$, а Хаято требуется его угадать.
Изначально Кира дает Хаято значение $$$\mathrm{cnt}$$$ — количество единичных битов в двоичной записи $$$n$$$. Для того чтобы угадать $$$n$$$, Хаято может делать лишь операции одного типа: выбрать некоторое целое число $$$x$$$ и вычесть его из $$$n$$$. Обратите внимание, что после каждой операции число $$$n$$$ изменяется. Кира не любит плохих запросов, поэтому если Хаято попробует вычесть число $$$x$$$ большее, чем $$$n$$$, то он проиграет Кире. После каждой операции Кира сообщает обновленное значение $$$\mathrm{cnt}$$$ — количество единичных битов в двоичной записи обновленного значения $$$n$$$.
У Киры не так много терпения, поэтому Хаято должен угадать изначальное значение числа $$$n$$$ за не более чем $$$30$$$ запросов.
Так как Хаято учится в начальной школе, он просит вашей помощи — напишите программу, которая угадывает число $$$n$$$. Кира — честный человек, поэтому он зафиксирует значение $$$n$$$ изначально и не станет как-то менять начальное число в зависимости от запросов Хаято.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$\mathrm{cnt}$$$ — изначальное количество единичных битов в двоичной записи $$$n$$$.
Загаданное целое число $$$n$$$ удовлетворяет следующему ограничению $$$1 \le n \le 10^9$$$.
Для угадывания $$$n$$$ вы можете не более $$$30$$$ раз произвести описанную операцию. Для этого выведите строку в формете «- x» ($$$1 \le x \le 10^9$$$).
После этой операции из $$$n$$$ вычитается число $$$x$$$, и поэтому значение $$$n$$$ изменяется. Если число $$$x$$$ оказалось больше, чем текущее число $$$n$$$, то такой запрос считается некорректным.
После каждой операции считайте одно неотрицательное целое число $$$\mathrm{cnt}$$$ — количество единичных битов в двоичной записи текущего $$$n$$$ после совершения операции.
Когда вы узнаете число $$$n$$$, выведите одну строку следующего формата: «! n» ($$$1 \le n \le 10^9$$$).
После этого переходите к решению следующего набора входных данных или завершите программу, если таких нет.
Если ваша программа сделает более $$$30$$$ операций для одного набора входных данных, вычтет число $$$x$$$ большее, чем $$$n$$$, или сделает некорректный запрос, то ответом на запрос будет -1, после получения такого ответа ваша программа должна немедленно завершится, чтобы получить вердикт Неправильный ответ. Иначе она может получить любой другой вердикт.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
Взломы
Чтобы сделать взлом, используйте следующий формат.
Первая строка должна содержать одно целое число $$$t$$$ ($$$1 \leq t \leq 500$$$).
Каждый набор входных данных должен содержать одно целое число $$$n$$$ ($$$1 \leq n \leq 10^9$$$) на отдельной строке.
3 1 0 1 1 0 2 1 0
- 1 ! 1 - 1 - 1 ! 2 - 2 - 1 ! 3
К примеру, количество единичных битов в числе $$$6$$$ это $$$2$$$, потому что двоичное представление $$$6$$$ это $$$110$$$. Для $$$13$$$ количество единичных битов $$$3$$$, так как $$$13_{10} = 1101_2$$$.
В первом примере $$$n = 1$$$, поэтому на вход дается число $$$1$$$. После вычитания из $$$n$$$ единицы оно становится нулевым, поэтому и количество единичных битов у него $$$0$$$.
В третьем примере $$$n = 3$$$, которое в двоичном представлении выглядит как $$$3_{10} = 11_2$$$, следовательно на вход даётся количество единиц, то есть $$$2$$$. После вычитания числа $$$2$$$ мы имеем $$$n = 1$$$, поэтому количество единичных битов теперь $$$1$$$. После вычитания из $$$n$$$ единицы оно становится равно нулю.
Название |
---|