Морской бой

Посчитаем минимальное количество клеток поля, необходимое, чтобы расположить корабли, в зависимости от числа k. Поскольку количество кораблей равняется 1 + 2 + ... + k, количество клеток, разделяющих корабли, равняется этой сумме, вычисляемой по известной формуле . Единицу отнимаем потому что разделяющих клеток на одну меньше, чем кораблей.

Теперь посчитаем количество клеток, занимаемое непосредственно кораблями. Это количество по условию равняется следующей сумме: k + 2·(k - 1) + 3·(k - 2) + ... + k·1. Раскрыв скобки и вынеся k, а также минус, за скобки, получим следующее выражение: (1 + 2 + ... + kk - (1·2 + 2·3 + ... + (k - 1)·k). Заменив скобки эквивалентными формулами, получим: . Заметим, что функция , определяющая минимальное количество необходимых для расположения кораблей клеток в зависимости от k, монотонна. Значит, требуемое для решения задачи значение k можно найти двоичным поиском за .