Алиса и её младший брат Боб играют в игру на угадывание чисел.
Боб загадал (скрытое) целое число $S$.
Алиса может задавать вопросы о скрытом числе следующего вида: «Является ли скрытое число не меньше $x$?» Боб отвечает на её вопросы «Да» или «Нет». К сожалению, после $K \ge 1$ вопросов Боб устаёт от игры, и с этого момента он будет давать ложные ответы на все вопросы.
То есть Боб: Отвечает «Да» на первые $K$ вопросов тогда и только тогда, когда $x \le S$. После $K$-го вопроса он отвечает «Да» тогда и только тогда, когда $S < x$.
Заметьте, что Боб всегда отвечает правильно на первый вопрос, и Алиса не знает значения $K$.
Ваша задача — разработать и реализовать стратегию опроса для Алисы, чтобы определить скрытое число. Ваш балл зависит от количества заданных вопросов — чем меньше вопросов, тем выше балл.
Детали реализации
Вы должны реализовать следующую процедуру:
long long play_game()- Эта процедура вызывается не более $T$ раз для каждого теста.
Процедура должна найти и вернуть скрытое число $S$, вызывая следующую процедуру для задания вопросов о скрытом числе:
bool ask(long long x)- $x$: число, задающее вопрос Алисы.
- Значение $x$ должно быть в диапазоне от $1$ до $10^{18}$ включительно.
- Процедура возвращает логическое значение, представляющее ответ Боба.
- Процедура может быть вызвана не более $150$ раз в каждом вызове
play_game.
Поведение проверяющей системы является адаптивным, что означает, что в некоторых тестах значения $S$ и $K$ не зафиксированы до вызова play_game. Гарантируется, что существует по крайней мере одна пара $(S, K)$, для которой ответы проверяющей системы согласованы.
Ограничения
- $1 \le T \le 1000$
- $1 \le S \le 10^{18}$
- $1 \le K \le 150$
Подзадачи
Если ваше решение не соответствует описанным выше деталям реализации или если значение, возвращаемое play_game, неверно даже для одного вызова, ваше решение получит 0 баллов.
В противном случае, пусть $C$ — максимальное количество вопросов, которое задает ваше решение во всех вызовах play_game. Ваш балл рассчитывается согласно следующей таблице:
| Условие | Баллы |
|---|---|
| $132 < C \le 150$ | $20 \cdot (\frac{150-C}{18})^2$ |
| $78 < C \le 132$ | $20 + 20 \cdot (\frac{132-C}{54})^2$ |
| $72 < C \le 78$ | $40 + 30 \cdot (\frac{78-C}{6})^2$ |
| $67 < C \le 72$ | $70 + 30 \cdot (\frac{72-C}{5})^2$ |
| $C \le 67$ | $100$ |
Примеры
Рассмотрим сценарий, где скрытое целое число $S = 2$, а $K = 1$. Игра начинается с вызова:
play_game()Предположим, что play_game сначала вызывает ask(2). Так как $2 \le S = 2$ и Боб в этот момент говорит правду, вызов возвращает true.
Предположим, play_game снова вызывает ask(2). Хотя условие $2 \le S = 2$ всё ещё выполняется, Боб теперь лжёт (так как он уже сказал правду $K = 1$ раз), поэтому вызов возвращает false. Получение противоречивых ответов на один и тот же вопрос показывает, что Боб будет лгать на все последующие вопросы.
Теперь предположим, что play_game вызывает ask(3). Так как $3 \le S = 2$ ложно, а Боб лжёт, вызов возвращает true. В этот момент мы можем сделать вывод, что $2 \le S < 3$, что означает $S = 2$.
Следовательно, процедура должна вернуть $2$.
Примечание
Проверяющая система в примере не является адаптивной. Она обрабатывает $T$ сценариев, и в каждом случае считывает фиксированные значения $S$ и $K$ из входных данных и отвечает на вопросы соответствующим образом.
Входные данные:
T S[0] K[0] S[1] K[1] ... S[T-1] K[T-1]
Здесь $S[i]$ и $K[i]$ ($0 \le i < T$) задают скрытые параметры для каждого вызова play_game.
Выходные данные:
G[0] C[0] G[1] C[1] ... G[T-1] C[T-1]
Здесь $G[i]$ ($0 \le i < T$) — это число, возвращенное play_game, когда скрытые параметры равны $S[i]$ и $K[i]$, а $C[i]$ — это количество вопросов, заданных во время этого вызова.