Загадали? Угадаем!
(Время: 1 сек. Память: 16 Мб Сложность: 41%)
Это интерактивная задача.
Вам требуется сыграть с программой жюри в следующую игру:
Программа жюри загадывает целое число N от 1 до 104. Вы можете задавать запрос – целое число K от 1 до 108 включительно. На запрос программа жюри сообщает остаток от деления числа NN на число K.
Ваша задача – отгадать загаданное число не более, чем за 5 запросов.
Протокол взаимодействия
Взаимодействие вашей программы с программой жюри осуществляется через стандартный поток ввода-вывода. Сначала программа жюри сообщает Вам одно целое число T (1 ≤ T ≤ 1000) – количество партий, которые Вам надо сыграть.
В каждой партии взаимодействие начинает ваша программа запросом числа K. Запрос задаётся в виде «? K», где 1 ≤ K ≤ 108 – целое число. Программа жюри выдаст ответ – остаток от деления загаданного числа в степени самого себя на K. Вы можете задать не более пяти запросов за партию.
Если Вы хотите назвать число N, то выведите строку «! N», где N – предполагаемое значение N. Если программа жюри выведет число 1, то ответ угадан верно и Вы можете начать следующую партию. Если программа жюри выведет число –1, то ответ угадан неверно.
После успешного прохождения всех партий Ваша программа должна немедленно завершиться.
Пример
№ | стандартный ввод | стандартный вывод |
1 | 1 7 27 27 1 | ? 10 ? 100 ? 100000000 ! 3 |
Примечание
Для корректной работы программы после каждой операции вывода данных выводите перевод строки, а также очищайте буфер вывода. Очистка буфера вывода производится следующим образом:
- В языке Pascal: flush(output)
- В С/С++: fflush(stdout) или cout.flush()
- В Java: System.out.flush()
- В Python: sys.stdout.flush() из библиотеки sys
- В C# и Basic: Console.Out.Flush()
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|