Разбор добавил Виталий Павленко
Эта задача на бинпоиск по ответу. Нужно придумать функцию F, которая проверяет, сколько коров с переданным ей допустимым расстоянием можно расставить, и возвращает true, если можно расставить всех. Построим следующий график. Ось абсцисс целочисленная, ось ординат булевская. Отложим по оси абсцисс все допустимые расстояния, меньше которых между коровами быть не должно (от нуля до
\(+\infty\)), а по оси ординат — можем ли мы расставить всех коров с таким минимальным допустимым расстоянием. Легко видеть, что функция эта сначала принимает только значения true, а с некоторого момента — только значения false. По ней и будем делать бинпоиск. Нас интересует, где достигается крайнее правое значение true.
Берём отрезок [A; B] на оси абсцисс, покрывающий все возможные ответы на задачу. Для его середины M вызываем функцию F. Если она даёт true, то наш ответ лежит на отрезке [M; B], иначе — на полуинтервале [A; M). Рекурсивно вызываемся, творим бинпоиск и так далее.
На прямой расположены стойла, в которые необходимо расставить коров так, чтобы минимальное расcтояние между коровами было как можно больше.
Выходные данные
Выведите одно число – наибольшее возможное допустимое расстояние.