Задача №113461. Архивы джедаев
Это интерактивная задача.
В Далёкой-Далёкой Галактике \(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».
После каждого действия вашей программы выводите символ перевода строки. Если вы используете «writeln» в Паскале, «cout << ... << endl» в C++, «System.out.println» в Java или «print» в Python, сброс потока вывода у вас происходит автоматически, дополнительно делать «flush» не обязательно. Если вы используете другой способ вывода, рекомендуется делать «flush», но все равно обязательно требуется выводить символ перевода строки.
Ниже приведены наиболее типичные причины получения тех или иных сообщений об ошибке.
Если ваша программа соблюдает протокол, но неверно определяет искомый номер ячейки либо выполняет слишком много запросов, вы получите результат «Wrong Answer».
Если ваша программа выводит некорректно отформатированные сообщения программе жюри, то вы получите результат «Presentation Error» либо «Wrong Answer».
Если ваша программа нарушила протокол и ждет ввода в то же время, когда его ждет и программа жюри, то вы получите результат «Idleness Limit Exceeded». Обратите внимание, что к такому же результату может привести и то, что вы не переводите строку после каждого выведенного сообщения или выводите не тем способом, который описан в начале раздела, и не делаете «flush».
При входных данных:
16 3 10 12 13 16выход будет следующим:
? 1 ? 2 ? 3 ? 4 ! 4В примере из Архива были удалены данные о планетах с номерами 11, 14 и 15, а ячейки были перенумерованы, начиная с ячейки, содержащей сведения о планете с номером 10.