Сыграешь с Денисом?
(Время: 1 сек. Память: 16 Мб Сложность: 27%)
Это интерактивная задача.
Денису скучно и он хочет сыграть с вами в одну игру. Он загадал некоторое натуральное число N (1 ≤ N ≤ 109), и хочет, чтобы вы его угадали. Вы можете задавать Денису вопросы вида «? X», где X – натуральное число (1 ≤ X ≤ 109). После этого Денис сообщает вам остаток от деления числа X на N.
Как только вы посчитали, что знаете загаданное число, выведите сообщение «! X», означающее, что X – и есть это число. После вывода этого запроса общение с Денисом прекращается. Также, не забывайте, что Денис ответит не более чем на 40 вопросов.
Протокол взаимодействия
После каждого запроса вида «? X» вашей программе в новой строке будет сообщен остаток от деления вашего числа на загаданное число.
Вы должны выводить корректные запросы в формате, описанном выше. Последним должен следовать единственный запрос вида «! X», после чего ваша программа должна немедленно завершиться. Каждый ваш запрос должен завершаться переводом строки.
Ваша программа должна произвести не больше 40 запросов типа «? X». Обратите внимание, что последний запрос, выводящий ответ, не входит в данные 40 запросов.
Пример
| № | стандартный ввод | стандартный вывод |
|---|
| 1 | 2
4
4
3
0
0 | ? 10
? 12
? 4
? 11
? 8
? 16
! 8 |
Примечание
Для корректной работы программы после каждой операции вывода данных выводите перевод строки, а также очищайте буфер вывода. Очистка буфера вывода производится следующим образом:
- В языке Pascal: flush(output)
- В С/С++: fflush(stdout) или cout.flush()
- В Java: System.out.flush()
- В Python: sys.stdout.flush() из библиотеки sys
- В C# и Basic: Console.Out.Flush()
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
