F. Круговой сапёр
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Интерактивная задача

Дана окружность из $$$L = 10^9$$$ ячеек, пронумерованных по кругу от $$$1$$$ до $$$L$$$ (ячейки $$$1$$$ и $$$L$$$ соседние). В $$$n$$$ различных ячейках стоят мины; в каждом тесте расположение мин выбрано случайно и равновероятно среди всех наборов из $$$n$$$ ячеек.

Вы можете делать пробы ячеек. Если в пробуемой ячейке есть мина, она взрывается. В ответ на пробу ячейки $$$i$$$ вы узнаёте, была ли в ней мина, и расстояние $$$d$$$ от $$$i$$$ до некоторой оставшейся не взорванной мины. Какая именно мина выбирается, определяется неизвестным вам правилом — это не обязательно ближайшая мина. Расстояние между ячейками $$$a$$$ и $$$b$$$ равно $$$\min(|a - b|,\, L - |a - b|)$$$.

Сделав не более $$$30$$$ проб, укажите ячейку, в которой точно стоит не взорванная мина.

Входные данные

Первая строка содержит целое число $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$ — количество мин.

Выходные данные

Смотрите раздел «Протокол взаимодействия».

Протокол взаимодействия

Сначала прочитайте число $$$n$$$.

Чтобы сделать пробу, выведите «? i» $$$(1 \le i \le L)$$$ и прочитайте ответ:

  • «YES d», если в ячейке $$$i$$$ была мина (она взорвалась),
  • «NO d», если мины не было.

Здесь $$$d$$$ — расстояние от $$$i$$$ до некоторой не взорванной мины; мина, взорванная этой пробой, не учитывается.

Можно сделать не более $$$30$$$ проб. Чтобы дать окончательный ответ, выведите «! i» и завершите программу: в этот момент в ячейке $$$i$$$ должна стоять не взорванная мина. Ответ в лимит проб не входит.

Ваша программа получит вердикт «Неправильный ответ» в случае:

  • нарушения формата вывода;
  • превышения количества доступных проб;
  • все мины взорваны;
  • выведенный ответ неверен (ячейка не содержит не взорванную мину).

После каждого выведенного запроса обязательно сбрасывайте буфер вывода, иначе ваша программа получит вердикт «Idleness Limit Exceeded»:

  • C++: std::endl при выводе через iostream (cout « ... « endl), fflush(stdout) после вывода через stdio (printf);
  • Java: System.out.println(...), а при выводе через другой поток (PrintWriter, BufferedWriter) — его flush() после каждой строки;
  • Python: print(..., flush=True), а ответы интерактора читайте через input().
Пример
Лог взаимодействия
> 4
< ? 1
> YES 4
< ? 1
> NO 11
< ? 13
> NO 1
< ! 12
Примечание

Пример. На окружности стоят мины в ячейках $$$1$$$, $$$5$$$, $$$12$$$ и $$$100$$$ (программе эти позиции не известны, она видит только $$$n = 4$$$).

  • На запрос «? 1» интерактор отвечает «YES 4»: в ячейке $$$1$$$ была мина и она взорвалась (расстояния до мин $$$5$$$, $$$12$$$ и $$$100$$$ равны $$$4$$$, $$$11$$$ и $$$99$$$ соответственно, интерактор выбрал мину $$$5$$$ и ответил расстоянием до неё);
  • На повторный запрос «? 1» интерактор отвечает «NO 11»: мины в ячейке $$$1$$$ уже нет, а расстояние до мины $$$12$$$, которую выбрал интерактор, равно $$$11$$$;
  • На запрос «? 13» интерактор отвечает «NO 1»: в ячейке $$$13$$$ мины нет, интерактор выбрал мину $$$12$$$ и вывел расстояние до нее;
  • программа выводит «! 12» и завершается — ответ верный, так как в этой ячейке есть невзорванная мина. Всего было сделано $$$3$$$ пробы из разрешённых $$$30$$$ (запрос «! 12» в этот лимит не входит).

Этот пример показывает, что расстояние $$$d$$$ в ответе интерактора — это расстояние до какой-то (не обязательно ближайшей) не взорванной мины, и что уже взорванную мину выводить в качестве ответа нельзя.

Стратегия поиска невзорванной мины, используемая в примере, не обязательно является оптимальной.