Спершу з'ясуємо, скільки клітинок потрібно, щоб розставити всі кораблі для заданого .
Кораблів розміру 1 \times j рівно k - j + 1 штук, тому сумарна довжина всіх кораблів дорівнює
Загальна кількість кораблів дорівнює 1 + 2 + \ldots + k = \frac{k(k+1)}{2}. Кораблі не можуть торкатися один одного, отже між сусідніми кораблями потрібна щонайменше одна порожня клітинка, а таких проміжків на один менше за кількість кораблів.
Отже, мінімальна довжина поля для заданого дорівнює
що після спрощення дає зручнішу форму f(k) + 1 = \frac{k(k+1)(k+5)}{6}.
Функція строго зростає, тому відповіддю є найбільше , для якого f(k) \le N. Оскільки N \le 10^{18}, значення не перевищує кількох мільйонів, і потрібне шукається двійковим пошуком за \mathcal{O}(\log N).
Обчислення слід виконувати у 64-бітному цілому типі (long long у C++), інакше проміжний добуток переповниться. Не забудьте про випадок N = 0: жодного корабля поставити не можна, відповідь нуль.