시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB596516.129%

문제

Учёные планируют провести измерение уровней излучения ряда чёрных дыр. Уровень излучения чёрной дыры задаётся целым числом от $1$ до $n$. Для измерения уровня излучения каждой чёрной дыры используется свой специальный орбитальный зонд, на котором установлен датчик излучения.

Датчик, установленный на зонде, может отвечать на следующие запросы: по значению $x$ определить, верно ли, что уровень излучения больше или равен $x$. К сожалению, из-за ошибки в программном обеспечении ответ датчика может быть неверным. К счастью, после первого же неверного ответа датчик этого зонда изменяет своё состояние и на все последующие запросы выдаёт только верные ответы.

Учёные хотят выяснить уровень излучения нескольких чёрных дыр, выполнив для каждой из них не слишком много запросов к датчику направленного к ней зонда.

Требуется написать программу, которая взаимодействует с программой жюри, симулирующей датчики зондов, и определяет уровень излучения каждой чёрной дыры.

Для каждого запуска программы-решения необходимо решить задачу для нескольких чёрных дыр с одинаковым значением $n$. Количество чёрных дыр в одном запуске не превосходит $100$ и не сообщается программе-решению. 

Для каждого теста жюри зафиксировано число $q$--- максимальное количество запросов, которые разрешается сделать для одной чёрной дыры. Гарантируется, что $q$ запросов достаточно, чтобы решить задачу независимо от того, какие ответы будет давать программа жюри. Это число не сообщается программе-решению. Ограничения $q$ в различных подзадачах приведены в таблице с информацией о системе оценки. Если программа-решение делает более $q$ запросов к программе жюри для одной чёрной дыры, то на этом тесте она получает в качестве результата тестирования <<Неверный ответ>>.

프로토콜

Сначала на вход подаётся число $n$ --- максимальный возможный уровень излучения чёрной дыры ($1 \le n \le 30\,000$). Это число одинаковое для всех исследуемых в этом запуске чёрных дыр. После считывания $n$ программа-решение должна интерактивно взаимодействовать с программой жюри, чтобы последовательно определить уровень излучения одной или нескольких чёрных дыр. 

Программа должна выполнять запросы к датчику и получать ответы об уровне излучения.

Чтобы сделать запрос, программа-решение должна вывести строку вида <<? $x$>>, где $x$--- целое положительное число ($1 \le x \le n$).

В ответ на запрос программы-решения программа жюри подаёт ей на вход либо строку <<Yes>>, если датчик сообщает, что уровень излучения чёрной дыры больше или равен значению $x$, заданному в запросе, либо строку <<No>>, если датчик сообщает, что уровень излучения чёрной дыры меньше $x$.

Если программа-решение определила ответ на задачу, то она должна вывести строку <<\mbox{! $x$}>>, где $x$ --- искомый уровень излучения чёрной дыры. Если $x$ является единственным уровнем излучения, который противоречит не более чем одному ответу программы жюри для данной чёрной дыры, то ответ для этой чёрной дыры считается правильным. 

После вывода ответа для очередной чёрной дыры программа должна считать строку. В случае, когда необходимо приступить к исследованию следующей черной дыры, на ввод будет подана строка <<Correct>>. 

Если все необходимые чёрные дыры были исследованы, то на ввод будет подана строка <<Done>>. В этом случае программа-решение  должна завершить работу. 

Если для очередной чёрной дыры дан неправильный ответ, программа-решение будет принудительно завершена и на этом тесте получит результат тестирования <<Неверный ответ>>.

Гарантируется, что после каждого ответа программы жюри существует такое значение уровня излучения, что ответы на все ранее сделанные запросы для данной чёрной дыры кроме, может быть, одного, верны. Программа жюри может адаптировать своё поведение, в том числе выбирать, какой из уже данных ответов был неверным и чему равен уровень излучения исследуемой чёрной дыры, в зависимости от запросов, сделанных программой-решением. 

서브태스크

В подзадачах 3--17 в каждом тесте значение $q$ равно минимальному числу разрешённых запросов, с помощью которых можно гарантированно (то есть сделав не более $q$ запросов) узнать уровень излучения чёрной дыры независимо от ответов датчика для значения $n$ в этом тесте.

번호배점제한
17

$n \le 1000$, $q = 30$

28

$n \le 1000$, $q = 21$

36

$n \le 4$, $q$ оптимально

49

$n \le 7$, $q$ оптимально

55

$n \le 12$, $q$ оптимально

66

$n \le 25$, $q$ оптимально

74

$n \le 40$, $q$ оптимально

85

$n \le 80$, $q$ оптимально

95

$n \le 150$, $q$ оптимально

108

$n \le 300$, $q$ оптимально

117

$n \le 500$, $q$ оптимально

125

$n \le 1000$, $q$ оптимально

135

$n \le 2000$, $q$ оптимально

145

$n \le 4000$, $q$ оптимально

155

$n \le 8000$, $q$ оптимально

165

$n \le 15\,000$, $q$ оптимально

175

$n \le 30\,000$, $q$ оптимально

예제 입력 1

2

Yes

No

Yes

Correct

No

No

Done

예제 출력 1


? 2

? 2

? 2

! 2

? 2

? 2

! 1

예제 입력 2

3

Yes

Yes

No

Yes

No

Done

예제 출력 2


? 2

? 2

? 3

? 3

? 3

! 2

힌트

В первом примере для первой чёрной дыры после первых двух запросов неизвестно, на какой из них ответ датчика оказался неверным, поэтому необходим третий запрос. 

Во втором примере показан один из возможных вариантов взаимодействия для $n = 3$, который находит ответ за 5 запросов. Можно показать, что за 4 запроса узнать ответ нельзя. 

В обоих примерах решение проверяется со значением $q = 30$.

Обратите внимание, что программа жюри может давать другие ответы, даже если решение будет задавать ровно те же запросы, что в примере. 

채점 및 기타 정보

  • 예제는 채점하지 않는다.