Задача Z. Угадай число Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение...

В данной задаче требуется отгадать загаданное программой жюри число, используя не более 30 попыток. Число находится в диапазоне от 1 до n, где n может быть до 1 миллиарда. Это типичная задача на использование алгоритма бинарного поиска, который позволяет эффективно сузить диапазон возможных значений загаданного числа.

Решение с использованием бинарного поиска

Бинарный поиск — это алгоритм, который ищет целевое значение в отсортированном массиве, последовательно деля массив пополам и определяя, в какой из половин находится целевое значение. Применительно к данной задаче:

1. Инициализация диапазона поиска:

   • Установите начальные границы поиска: low = 1 и high = n.

2. Бинарный поиск:

   • Повторяйте следующие шаги до тех пор, пока не будет найдено загаданное число (пока ответ жюри не будет равен 0):
     1. Вычислите среднюю точку: mid = (low + high) // 2.
     2. Выведите mid в стандартный поток вывода и выполните сброс буфера вывода.
     3. Считайте ответ от программы жюри:
        • Если ответ 0, то mid — это загаданное число, завершаем программу.
        • Если ответ 1, это значит, что загаданное число больше mid, обновляем нижнюю границу поиска: low = mid + 1.
        • Если ответ -1, это значит, что загаданное число меньше mid, обновляем верхнюю границу поиска: high = mid - 1.

Пример кода на Python

import sys

def guess_number(n):
    low, high = 1, n
    
    while low 

Для решения данной задачи "Угадай число" можно воспользоваться методом бинарного поиска. Сначала задаем диапазон чисел от 1 до n, и далее делаем серединное значение из этого диапазона и отправляем его в качестве догадки программе жюри. В зависимости от ответа программы жюри (больше, меньше или равно), мы сокращаем диапазон поиска до половины и продолжаем процесс. Таким образом, с каждой догадкой диапазон значений будет сужаться, и после нескольких итераций мы сможем угадать число, которое загадала программа жюри. В данной задаче необходимо уложиться в 30 догадок, что вполне реально при использовании метода бинарного поиска.