Отримання знань

Задача Riddle

(запропонована читачем популярних книг з інформатики)

Я загадаю ціле число з інтервалу [A,B]. Напишіть програму, що за мінімальну кількість запитань відгадає це число. Грати будемо так. Я повідомляю програмі числа A і B, програма виводить свою версію відповіді. Якщо вона менше задуманого мною, я повідомлю програмі про це числом  -1, якщо більше, то числом 1, а якщо вгадано – числом 0. Так буде продовжуватися, поки програма не вгадає число (звичайно, я буду грати чесно!). Намагайтеся, щоб ваша програма вгадала число за мінімальну кількість ходів.

Технічні умови: У першому рядку вводите з клавіатури два цілих числа А та В через пропуск – межі діапазону (-100000£A£B£100000). Програма на екран виводить свою версію в новому рядку. З нового рядка ви вводите "-1", "1" або "0" (без лапок). Так продовжується до того моменту, поки число не буде вгадано (тобто ваша відповідь "0" повинна завершити роботу програми).

Приклад:

 (я задумав число 2)

Введення: 1 6  Виведення: 3 Введення: 1 Виведення: 2 Введення: 0