Одновимірний морський бій#25

Одновимірний морський бій (Editorial)

Спершу з'ясуємо, скільки клітинок потрібно, щоб розставити всі кораблі для заданого .

Кораблів розміру 1 \times j рівно k - j + 1 штук, тому сумарна довжина всіх кораблів дорівнює

\sum_{j=1}^{k} j\,(k - j + 1) = \frac{k(k+1)(k+2)}{6}.

Загальна кількість кораблів дорівнює 1 + 2 + \ldots + k = \frac{k(k+1)}{2}. Кораблі не можуть торкатися один одного, отже між сусідніми кораблями потрібна щонайменше одна порожня клітинка, а таких проміжків на один менше за кількість кораблів.

Отже, мінімальна довжина поля для заданого дорівнює

f(k) = \frac{k(k+1)(k+2)}{6} + \frac{k(k+1)}{2} - 1,

що після спрощення дає зручнішу форму 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: жодного корабля поставити не можна, відповідь нуль.