시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 17 | 1 | 1 | 5.882% |
В Далёкой-Далёкой Галактике $10^{18}$ планет, и все они пронумерованы натуральными числами от $1$ до $10^{18}$.
В Архивах джедаев были сохранены сведения о всех планетах Галактики: по кругу в огромном зале были расположены ячейки, пронумерованные против часовой стрелки от 1 до $10^{18}$. Исходно Архивы были устроены очень просто: в ячейке с номером $i$ хранились сведения о планете с номером $i$. Поэтому, зная лишь номер планеты, всегда можно было легко найти информацию о ней.
Вот и Оби-Вану Кеноби понадобилось узнать координаты планеты Камино, которая имеет номер $x$. Однако, заглянув в Архивы, он с удивлением обнаружил, что кто-то удалил из Архивов $m$ ячеек со сведениями о некоторых планетах. Кроме того, оставшиеся ячейки были заново пронумерованы, начиная с $1$, против часовой стрелки (возможно, начиная не с той, с которой они нумеровались исходно), и теперь в ячейке с номером $i$ могут храниться сведения о совсем другой планете.
Оби-Ван в затруднении. Ему нужно срочно найти данные о планете Камино. Оби-Ван может проверить содержимое ячейки и узнать, данные о какой планете в ней находятся. У Оби-Вана мало времени, поэтому он может проверить содержимое не более чем десяти ячеек.
Помогите ему выяснить, в какой ячейке находятся данные о планете Камино, если, конечно, они не были удалены из Архивов.
Сначала вашей программе подаётся на вход в отдельной строке два числа: $x$ --- номер планеты Камино ($1 \le x \le 10^{18}$) и $m$ --- число удаленных из Архивов ячеек ($0 \le m \le 500$).
После этого ваша программа может делать запросы: <<посмотреть, сведения о какой планете записаны в ячейке номер $v$>>. Для этого нужно вывести в выходной поток на отдельной строке <<? v
>> ($1 \le v \le 10^{18}-m$). В ответ на запрос во входном потоке на отдельной строке будет записано одно число --- номер планеты, сведения о которой записаны в ячейке $v$. Вы можете сделать не более десяти таких запросов, иначе ваша программа получит вердикт <<Wrong answer
>>.
В конце вы должны вывести в выходной поток <<! a
>>, где $a$ --- это номер ячейки, в которой записаны сведения о планете Камино. Если данные о планете Камино были удалены из Архива, то следует вместо номера ячейки вывести $-1$, таким образом последнее сообщение должно быть <<! -1
>>.
16 3 10 12 13 16
? 1 ? 2 ? 3 ? 4 ! 4
В примере из Архива были удалены данные о планетах с номерами $11$, $14$ и $15$, а ячейки были перенумерованы, начиная с ячейки, содержащей сведения о планете с номером $10$.
Olympiad > Russian Olympiad in Informatics > Russia Team High School Programming Contest > Russia Team High School Programming Contest 2016 G번