Дано поле в игре, представляющее собой полоску длины n клеток. На этом поле расположен корабль из k клеток, где k ≤ n. После каждого выстрела на поле сообщается результат: "Мимо", "ранен" или "убит". Нужно написать программу, которая будет выводить количество выстрелов до уничтожения корабля. Для решения этой задачи можно использовать бинарный поиск. Представим поле в виде массива, где каждый элемент будет обозначать состояние клетки: 0 - пустая клетка, 1 - клетка с кораблем. Изначально все клетки будут пустыми, и мы будем изменять состояние клеток в процессе игры. Будем делать выстрелы посередине поля до тех пор, пока находимся внутри корабля. В начале игры будем считать, что мы находимся в середине поля, то есть будем смотреть на клетку с индексом n // 2. Если текущая клетка пуста, мы будем делать выстрел посередине от начала поля до текущей позиции. Если текущая клетка содержит корабль, мы будем делать выстрелы посередине от текущей позиции до конца поля. Теперь проделаем это в цикле, пока не уничтожим корабль: 1. Проверим, сколько клеток с кораблем осталось на поле: - Если клеток с кораблем не осталось, выйдем из цикла. - Если осталась только одна клетка, это означает, что мы попали в корабль, и мы уничтожили его. Выходим из цикла. - В противном случае продолжаем игру. 2. Проверим, находимся ли мы внутри корабля: - Если индекс последнего выстрела меньше или равен индексу последней клетки корабля, значит, мы находимся внутри корабля. - В противном случае, мы находимся за пределами корабля. 3. Находим позицию следующего выстрела: - Если мы находимся внутри корабля, позиция следующего выстрела будет находиться между текущей позицией и концом поля. - Если мы находимся за пределами корабля, позиция следующего выстрела будет находиться между началом поля и текущей позицией. 4. Проверяем, что полученная позиция не выходит за пределы поля. Если это так, смещаем позицию на границу поля. 5. Выводим количество выстрелов, увеличиваем счетчик выстрелов и обновляем состояние поля после выстрела. Пример решения на языке Python:

python

n = int(input())  # Длина поля

k = int(input())  # Длина корабля



shots = 0  # Счетчик выстрелов



# Создание и заполнение поля

field = [0] * n

for i in range(k):

    field[i] = 1



while sum(field) > 0:

    # Проверка количества оставшихся клеток с кораблем

    if sum(field) == 1:

        shots += 1

        break



    # Проверка нахождения внутри корабля

    if shots <= k - 1:

        left = shots

        right = n - 1

    else:

        left = 0

        right = shots



    # Нахождение позиции следующего выстрела

    position = (left + right) // 2



    # Проверка, что позиция не выходит за пределы поля

    if position < 0:

        position = 0

    elif position >= n:

        position = n - 1



    # Проверка результата выстрела и обновление состояния поля

    if field[position] == 1:

        field[position] = 0

        shots += 1

    else:

        shots += 1



print(shots)

На вход программе подается два числа: длина поля и длина корабля. Пример входных данных: `4 2`. Выходные данные программы - количество выстрелов до уничтожения корабля. В данном случае результатом будет число 3.