Жюри выбрало некоторое целое число $x$ из интервала $[1, n]$. Ваша задача — угадать его. Чтобы вам не приходилось делать это вслепую, вы можете задавать запросы. В каждом запросе можно указать целое число $y$ из интервала $[0, c]$, а в ответ мы сообщим вам количество делителей числа $x + y$.
Чтобы немного усложнить задачу, в ходе одного запуска программы вам потребуется решить $t$ тестовых случаев. Суммарное количество запросов, которые вы можете задать во всех них, ограничено числом $q$.
Протокол взаимодействия
Это интерактивная задача. Вам необходимо написать программу, которая будет взаимодействовать с жюри, используя предоставленную библиотеку. Чтобы использовать библиотеку, необходимо добавить в свою программу:
- C++:
#include "dzilib.h" - Python:
from dzilib import GetT, GetN, GetQ, GetC, Ask, Answer
Библиотека предоставляет следующие функции:
GetT()— возвращает параметр $t$ — количество тестовых случаев для решения.GetN()— возвращает параметр $n$ — ограничение на скрытые значения $x$.GetQ()— возвращает параметр $q$ — ограничение на суммарное количество запросов, которые можно задать во всех $t$ тестовых случаях.GetC()— возвращает параметр $c$ — ограничение на подаваемые вами значения $y$.Ask(y)— возвращает количество положительных делителей скрытого числа $x$, увеличенного на $y$. Должно выполняться условие $0 \le y \le c$.Answer(z)— сообщает библиотеке, что, по вашему мнению, скрытое значение $x$ равно $z$. Функция ничего не возвращает (в языке C++ функция имеет типvoid).
В языке Python все параметры библиотечных функций и возвращаемые ими значения являются целыми числами. В языке C++ типы принимаемых и возвращаемых значений функций соответствуют тем, что указаны в предоставленной библиотеке, о которой подробнее рассказано в разделе «Детали реализации».
В любой момент работы программы (кроме самого её завершения) активен ровно один тестовый случай. Первый тестовый случай активируется сразу после запуска программы. Когда тестовый случай активен, вы можете задавать запросы с помощью функции Ask. Когда вы решите, что знаете скрытое значение $x$, вы можете передать его с помощью функции Answer, и библиотека его проверит. Если переданное значение неверно, библиотека завершит работу программы с вердиктом «неправильный ответ». Если значение параметра верно, функция завершится; если решенный тестовый случай был не последним, сразу активируется следующий. После ответа на последний тестовый случай вы должны завершить работу программы. Если вы этого не сделаете и попытаетесь использовать функцию Ask или Answer, вы получите вердикт «неправильный ответ».
Функции GetT, GetN, GetQ и GetC можно использовать в любой момент работы программы, возвращаемые ими значения не меняются. Эти функции не учитываются в лимите запросов, но потребляют процессорное время. Значение $q$ ограничивает только количество вызовов функции Ask. В момент, когда вы превысите суммарное допустимое количество запросов, библиотека завершит работу программы, и вы получите вердикт «неправильный ответ».
Не следует считывать какие-либо данные со стандартного ввода или выводить что-либо на стандартный вывод. Преднамеренные попытки повлиять на внутреннюю работу оценивающей библиотеки запрещены.
Библиотека
Скрытые значения $x$ во всех тестах и их порядок определены заранее. Это означает, что библиотека, с которой взаимодействует ваша программа, не является «злонамеренной» и не будет подстраивать свое поведение под действия вашей программы.
Ограничения, указанные в условии задачи, касаются только времени и памяти, потребляемых вашей программой. Время работы библиотеки и потребляемая ею память могут зависеть от теста и точного поведения вашей программы. По этой причине ограничения по времени и памяти в системе SIO2 несколько выше, чем указанные в условии.
Примеры
В тестовом примере $t = 2$, $n = 10^6$, $q = 10^4$, $c = 10^{15}$, скрытыми значениями являются последовательно $1000$ и $1$. Пример взаимодействия с библиотекой может выглядеть следующим образом:
| Вызванная функция | Результат | Описание |
|---|---|---|
GetT() |
$2$ | $t = 2$. |
GetN() |
$1\,000\,000$ | $n = 10^6$. |
GetQ() |
$10\,000$ | $q = 10^4$. |
GetC() |
$1\,000\,000\,000\,000\,000$ | $c = 10^{15}$. |
Ask(1) |
$8$ | Число $x + 1$ имеет $8$ делителей: $1, 7, 11, 13, 77, 91, 143$ и $1001$. |
Ask(24) |
$11$ | Число $x + 24$ имеет $11$ делителей: $1, 2, 4, 8, 16, 32, 64, 128, 256, 512$ и $1024$. |
Answer(1000) |
— | Правильный ответ, начинается следующий тестовый случай. |
GetT() |
$2$ | Допустимый запрос — возвращаемое значение не меняется. |
Answer(1) |
— | Правильный пример коммуникации и предоставление верного ответа на последний тестовый случай. После ответа необходимо завершить работу программы. |
Было задано $2$ запроса Ask, что укладывается в лимит $10\,000$ запросов. Помните, что учитывается суммарное количество запросов для всех тестовых случаев в одном тесте.
Подзадачи
Внутри группы тестов все тесты имеют одинаковые значения $t, n, q$ и $c$, представленные в следующей таблице:
| Номер группы | $t$ | $n$ | $q$ | $c$ |
|---|---|---|---|---|
| 1 | 50 | $10^5$ | 50 000 | $10^{12}$ |
| 2 | 50 | $10^6$ | 5 000 | $10^{12}$ |
| 3 | 10 | $10^9$ | 50 000 | $10^{12}$ |
| 4 | 10 | $10^{14}$ | 5 000 | $10^{17}$ |
| 5 | 10 | $10^{14}$ | 2 000 | $10^{17}$ |
| 6 | 10 | $10^{14}$ | 1 300 | $10^{17}$ |
| 7 | 10 | $10^{14}$ | 950 | $10^{17}$ |
| 8 | 10 | $10^{14}$ | 820 | $10^{17}$ |
| 9 | 10 | $10^{14}$ | 750 | $10^{17}$ |
| 10 | 10 | $10^{14}$ | 720 | $10^{17}$ |
Тестовый пример не принадлежит ни к одной из групп. Вы можете его решить, однако обратите внимание, что возможно получение полного балла без его решения.
Детали реализации
Примеры ошибочных решений и примеры библиотек на языках C++ и Python находятся в архивах в разделе «Файлы» на SIO2. Эти решения и библиотеки иллюстрируют типы, возвращаемые и принимаемые всеми функциями. Примерные библиотеки могут отличаться поведением от той, которая будет использована для оценки решений, и могут не соответствовать всем предположениям задачи. Они служат лишь для демонстрации способа взаимодействия с программой.
Решение dzi.cpp на языке C++ можно скомпилировать следующим образом:
g++ -O3 -static -o dzi dzi.cpp dzilib.cpp -std=c++20
Необходимо убедиться, что файлы dzilib.h и dzilib.cpp находятся в той же папке, что и решение.
Решение dzi.py можно запустить командой:
python dzi.py
Необходимо убедиться, что файл dzilib.py находится в той же папке, что и решение.
После запуска, в самом начале работы программы, библиотека считывает со стандартного ввода значения $t, n, q$ и $c$, а затем последовательно скрытые значения $x$. Входной файл, соответствующий тестовому примеру, находится в обоих архивах под названием dzi0.in.