Задача №113902. Поиграем?
Это интерактивная задача.
1804 год. Вице-президент Соединённых Штатов Аарон Бёрр вызывает на дуэль кандидата в губернаторы штата Нью-Йорк Александра Гамильтона за серию оскорбительных памфлетов в свой адрес.
Но Бёрр разумный человек и понимает, что даже если он убьет Гамильтона на дуэли, он потеряет свою репутацию, и его политическая карьера будет закончена. Поэтому противники решили просто сыграть в игру. Для честности они решили сыграть в неё g раз.
Каждую игру Гамильтон загадывает целое положительное число
n
, а Бёрр пытается его отгадать. Для любого целого положительного
x
Бёрр может спросить у Гамильтона долю чисел между
1
и
n
включительно, которые делятся на
x
. Иными словами, спрашивая про
x
, он получает значение выражения
, причём Гамильтон сообщает ему результат в виде
несократимой
дроби (здесь
обозначает результат округления вниз вещественного числа
r
).
Помогите Бёрру найти ответ за некоторое заранее определённое число запросов.
При запуске решения на вход подается целое число g — число игр между Гамильтоном и Бёрром ( 1 ≤ g ≤ 1000 ).
Для каждого теста зафиксировано число q ( 6 ≤ q ≤ 60 ) — максимальное количество запросов в одной игре. Гарантируется, что q запросов достаточно, чтобы решить задачу. Эти числа не сообщаются программе участника, но ограничения на эти числа в различных подзадачах приведены в таблице системы оценивания. Если программа участника делает более q запросов программе жюри, на этом тесте она получает в качестве результата тестирования «Wrong answer».
Чтобы сделать запрос, следует вывести строку «
X
t
», где
t
— целое положительное число (
1 ≤
t
≤ 10
18
), для которого требуется узнать значение выражения
В ответ на каждый запрос программа получает через пробел два числа a и b — числитель и знаменатель этой дроби после сокращения — или число - 1 в случае, если программа превысила ограничение по числу запросов.
Если программа определила загаданное число, то она должна вывести строку « N t », где t — предполагаемый ответ ( 1 ≤ t ≤ 10 18 ). Если ответ был правильный, то в ответ программа получает строку « Correct », а если неправильный, то она получает строку « Wrong ».
После этого программа переходит к следующей игре, если они остались, иначе она должна завершиться.
Обратите внимание, в случае считывания числа - 1 или строки « Wrong » вы обязательно должны сразу завершить вашу программу. В противном случае вердикт тестирующей системы может быть некорректным, в частности, вы можете получить вердикт Run-time error или Time limit exceeded!
Гарантируется, что в каждом тесте загаданные числа фиксированы в самом начале игры и не изменяются в зависимости от ваших запросов.
При запуске решения на вход подается целое число g — число игр между Гамильтоном и Бёрром ( 1 ≤ n ≤ 10 000 ).
Для каждого теста зафиксировано число q — максимальное количество запросов в одной игре. Гарантируется, что q запросов достаточно, чтобы решить задачу. Эти числа не сообщаются программе участника, но ограничения на эти числа в различных подзадачах приведены в таблице системы оценивания. Если программа участника делает более q запросов программе жюри, на этом тесте она получает в качестве результата тестирования «Неверный ответ».
Чтобы сделать запрос, следует вывести строку «
X
t
», где
t
— целое положительное число (
1 ≤
t
≤ 10
18
), для которого требуется узнать значение выражения
.
В ответ на каждый запрос программа получает через пробел два числа a и b — числитель и знаменатель этой дроби после сокращения , или число - 1 в случае, если программа превысила ограничение по числу запросов. Обратите внимание, в случае считывания числа - 1 вы обязательно должны сразу завершить вашу программу. В противном случае, вердикт тестирующей системы может быть некорректным!
Если программа определила загаданное число, то она должна вывести строку « N t », где t — предполагаемый ответ ( 1 ≤ t ≤ 10 18 ). Если ответ был правильный, то в ответ программа получает строку « Correct », а если неправильный, то она получает строку « Wrong ». Обратите внимание, в случае неправильного ответа вы обязательно должны сразу завершить вашу программу. В противном случае, вердикт тестирующей системы может быть некорректным!
После этого программа переходит к следующей игре, если они остались, иначе она завершается.
Тесты к этой задаче состоят из девяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
В первом примере g = 2 . Приведены примеры запросов, по которым игрок угадывает, что в первой игре загадано число 10 , а во второй 1 . Эти же числа загаданы в первом тесте в тестирующей системе.
В точности соблюдайте формат выходных данных. После каждого вывода обязательно выводите один перевод строки и сбрасывайте буфер вывода — для этого используйте flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.
2 60 10 1
< X 1073741824 > 0 1 < X 32768 > 0 1 < X 128 > 0 1 < X 8 > 1 10 < X 32 > 0 1 < X 16 > 0 1 < N 10 > Correct < X 1073741824 > 0 1 < X 32768 > 0 1 < X 128 > 0 1 < X 8 > 0 1 < X 2 > 0 1 < N 1 > Correct Ok, maximum is 6 queries