0374. Гараж в снегу

У вовиного дедушки есть гараж в кооперативе, в котором он держит свою машину. За зиму выпало очень много снега и дедушка попросил Вову почистить въезд в гараж от снега. Вова вооружился лопатой и бодро отправился к гаражам. По прибытии на место Вова обнаружил, что абсолютно все гаражи завалены доверху снегом и понять, какой же из них дедушкин, решительно невозможно. Всего Вова обнаружил N гаражей, расположенных в ряд вдоль дороги.

Вова вспомнил, что у гаражей определенно были номера. Позвонив дедушке, Вова узнал, что дедушкин гараж имеет номер X, а сами гаражи нумеруются в возрастающем порядке (но необязательно подряд), начиная с некоторого гаража i. Например, номера гаражей могут выглядеть вот так: 15 20 23 2 5 7 11 (в данном случае семь гаражей, нумерация начинается с четвёртого).

Откопать номер, написанный на гараже, намного проще, чем откопать гараж целиком, потому Вова решил сначала найти дедушкин гараж, а потом уже его откапывать. Помогите ему сделать это.

Формат входного файла

Это интерактивная задача, ваше решение будет взаимодействовать со специальной программой, подготовленной жюри. После запуска на стандартный поток ввода вы получите два числа N и X – общее количество гаражей в кооперативе и номер гаража вовиного дедушки (1 ≤ N ≤ 10⁶; 1 ≤ X ≤ 10⁹).

После этого вы можете отправлять Вову откапывать номер гаража, расположенного на месте i (1 ≤ i ≤ N). Для этого выведите число i, а за ним – перевод строки. В ответ на этот запрос вам на стандартный поток ввода придёт ответ a_i – номер гаража, расположенного на месте i (1 ≤ a_i ≤ 10⁹). Помните, что гаражи нумеруются по возрастанию, но не подряд, а нумерация начинается не с первого гаража в кооперативе. Номера гаражей – целые положительные числа. Гарантируется, что гараж с номером X в кооперативе есть. Номера гаражей различны.

После того, как вы в ответ получите число X (искомый номер гаража), ваша программа должна завершиться. Если ваша программа завершится до того, как гараж будет найден, тест будет не пройден. Также, вы можете использовать не более 30 запросов (после этого Вова устанет и не сможет откопать дедушкин гараж).

Не забывайте сбрасывать буфер вывода после вывода каждого запроса. Это делается при помощи функции fflush(stdout); в C++ и flush(output); в Pascal.

Пример:

В примере приведен пример диалога вашей программы и программы жюри (гаражи занумерованы так: 15 20 23 2 5 7 11). Первым запросом программа участника отправляет Вову откапывать номер четвёртого гаража и получает в ответ номер 2. После второго запроса выясняется номер первого гаража 15, а после третьего запроса искомый гараж оказывается найден.

Источник: Открытый весенний чемпионат ПетрГУ по программированию, 20 апреля 2014

Обсудить       Отправить решение



Версия для печати