Codeforces Round 534 (Div. 1) |
---|
Закончено |
Это интерактивная задача.
Вася и Петя собираются сыграть в следующую игру: Петя загадает некоторое целое число $$$a$$$. После этого Вася должен будет отгадать его, задав несколько вопросов. Он может сказать пару целых неотрицательных чисел $$$(x, y)$$$. В ответ Петя скажет:
Операция $$$(x \bmod a)$$$ обозначает операцию взятия остатка $$$x$$$ при делении на $$$a$$$.
Вася должен отгадать число $$$a$$$ за не более, чем 60 вопросов.
Гарантируется, что Петя загадал число, удовлетворяющее неравенству $$$1 \leq a \leq 10^9$$$.
Помогите Васе играть в эту игру и напишите программу, которая будет угадывать число $$$a$$$.
Вам нужно будет сыграть несколько игр.
Перед началом каждой игры вы должны считать строку:
После считывания строки "start" (без кавычек) начинается очередная игра.
Сначала ваша программа может сделать несколько запросов вида спросить пару целых чисел $$$(x, y)$$$. Можно спрашивать только числа, удовлетворяющие неравенствам $$$0 \leq x, y \leq 2 \cdot 10^9$$$. Для этого нужно вывести "? x y" (без кавычек). В ответ ваша программа получит один из символов:
После того, как вы зададите несколько вопросов ваша программа должна вывести ответ в формате "! a" (без кавычек). Выведенное вами число $$$a$$$ должно удовлетворять неравенству $$$1 \leq a \leq 10^9$$$. Гарантируется, что задагаданное число $$$a$$$ удовлетворяло этому неравенству. На этом текущая игра закончится.
Напомним, что ваша программа не может задать больше, чем $$$60$$$ вопросов во время одной игры.
Если ваша программа не завершится после считывания "mistake" (без кавычек), "end" (без кавычек) или "e" (без кавычек), то она может получить любой вердикт, потому что будет считывать данные из закрытого потока ввода. Также, если ваша программа задаст вопрос или выведет ответ в неверном формате, она может получить любой вердикт. Будьте внимательны.
Не забудьте сбрасывать буфер вывода после того, как зададите вопрос или выведете ответ.
Чтобы сбросить буфер вывода вы можете использовать:
Гарантируется, что будет сыграно не меньше $$$1$$$ и не больше, чем $$$100$$$ игр.
Взломы:
Во взломах можно использовать только одну игру. Чтобы взломать решение участника с загаданным числом $$$a$$$ ($$$1 \leq a \leq 10^9$$$), в первой строке теста должно быть расположено единственное число $$$1$$$, а во второй число $$$a$$$.
start x x start x x y start x x y y end
? 0 0 ? 10 1 ! 1 ? 0 0 ? 3 4 ? 2 5 ! 2 ? 2 4 ? 2 5 ? 3 10 ? 9 1 ! 3
В тесте из условия будет сыграно $$$3$$$ игры, в которых будут задагаданы числа $$$1$$$, $$$2$$$ и $$$3$$$.
В первой игре ответом на любой вопрос будет "x" (без кавычек), так как $$$(x \bmod 1) = 0$$$ для всех целых $$$x$$$.
Во второй игре, если спросить пару $$$(0, 0)$$$, то ответом будет "x" (без кавычек), так как $$$(0 \bmod 2) \geq (0 \bmod 2)$$$. А если, например, спросить пару $$$(2, 5)$$$, то ответом будет "y" (без кавычек), так как $$$(2 \bmod 2) < (5 \bmod 2)$$$, потому что $$$(2 \bmod 2) = 0$$$ и $$$(5 \bmod 2) = 1$$$.
Название |
---|