Поиск

Угадай число


Ограничение времени                   1 секунда
Ограничение памяти 512Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt

Это интерактивная задача.

В процессе тестирования программа участника взаимодействует с программой жюри с использованием стандартных потоков ввода/вывода.

Программа жюри загадала число от 1 до n, цель программы участника — отгадать, задав не более чем за 30 вопросов. Для этого программа участника сообщает свои догадки программе жюри, а программа жюри отвечает, является ли загаданное число бóльшим, меньшим или равным сделанной догадке.

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

Сначала ваша программа должна прочитать из стандартного потока ввода число n. Затем протокол общения следующий: ваша программа выводит в стандартный поток вывода одну строку, содержащую число — свою догадку о загаданном числе.

После этого программа должна считать из стандартного потока ввода одно число: ответ программы жюри. Возможны следующие ответы:

  • «1» — загаданное число больше последней догадки;
  • «-1» — загаданное число меньше последней догадки;
  • «0» — последняя догадка верна. Считав 0, ваша программа должна завершиться.

Примечания

В данной задаче две подзадачи. Каждая оценивается в 50 баллов. Баллы за подзадачу начисляются только при прохождении всех тестов и предыдущих подзадач.

  1. 1 ≤ n ≤ 30
  2. 1 ≤ n ≤ 109

Пример

Ввод

5
-1
1
0

Вывод

3
1
2


Для отправки решения задачи необходимо авторизоваться!