Для решения этой задачи можно использовать метод бинарного поиска. Первым шагом в решении задачи будет нахождение максимального числа выстрелов, при котором корабль обязательно будет потоплен. Заметим, что если корабль занимает k клеток, то он может располагаться на поле по n - k + 1 способу (так как он может начинаться с любой клетки и занимать k клеток). Проверим возможность потопления корабля за определенное число выстрелов x. Мы можем попытаться потопить корабль, выполнив x выстрелов, при этом все выстрелы должны быть выполнены точно в одну и ту же точку поля. Если x ≥ k, то корабль обязательно будет потоплен, поскольку он занимает не более k клеток. В этом случае ответом будет x. Если x < k, то мы можем расположить корабль на поле так, чтобы он находился в позиции, где он не может быть потоплен за x выстрелов. Для этого надо, чтобы между любыми двумя клетками, куда мы стреляем, было хотя бы x свободных клеток (то есть клеток, которые не являются частью корабля). То есть, если (x - 1) * 2 ≥ n - k, то ответом будет x, так как мы можем разместить корабль на поле так, чтобы он занимал только k клеток и между любыми двумя клетками, куда мы стреляем, было хотя бы x свободных клеток. Иначе, ответом будет x + 1, так как невозможно разместить корабль таким образом, чтобы он был безопасен при x выстрелах, но мы можем разместить корабль так, чтобы он был безопасен при x + 1 выстрелах. Таким образом, алгоритм решения задачи будет выглядеть следующим образом: 1. Считываем значения n и k. 2. Если k ≥ n, выводим k (так как корабль занимает не более k клеток). 3. Иначе, находим значение максимального числа выстрелов x, при котором корабль может быть безопасно потоплен. 4. Выводим значение x + 1. Рассмотрим реализацию данного алгоритма на языке Python:

python

n = int(input())

k = int(input())



if k >= n:

    print(k)

else:

    x = (n - k) // 2

    if x * 2 < n - k:

        x += 1

    print(x + 1)

Приведенный код решает задачу за O(1) времени и использует O(1) памяти.