Задача E. Спички ≡

Условие

Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости N квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами — сами спички.

Напишите программу, которая по количеству квадратов N, которые необходимо составить, находит минимальное необходимое для этого количество спичек.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

4

12

Разбор

Для каждого квадрата необходимы четыре спички. Однако на плоскости каждая спичка может являться стороной одного (С1К) или двух квадратов (С2К). Наша задача — минимизировать число С1К.

Очевидно, что выкладываемая фигура должна представлять собой фрагменты сетки с квадратными ячейками, сторонами которых являются спички. Площадью фигуры (в спичках квадратных) является количество квадратов. Количество С1К — это периметр P фигуры.

Очевидно, что фигура должна быть связной. Если это не так, то можно соединить ее отдельные части, сделав общей хотя бы одну С1К (т.е. сделать ее С2К), тем самым уменьшив периметр.

Если фигура имеет внутри пустоту, можно заполнить ее спичками, увеличив площадь и уменьшив периметр (левый рисунок).

Если фигура при обходе имеет подряд более одного вогнутого угла, можно заполнить выемку спичками, увеличив площадь и уменьшив периметр (средний рисунок).

Если фигура при обходе имеет один вогнутый угол между двумя выпуклыми, можно заменить все три угла на один выпуклый, заполнив выемку спичками. При этом увеличится площадь и не изменится периметр (правый рисунок).

Если фигура — прямоугольник a × b, причем a − b > 1, то можно оставить периметр таким же и увеличить площадь, заменив эту фигуру на прямоугольник (a − 1) × (b + 1).

Соответственно, если фигура — квадрат a × a или прямоугольник (a + 1) × a, то увеличить площадь, оставив прежним или уменьшив периметр — НЕЛЬЗЯ.

Отсюда, если количество квадратов N = a × a или N = (a + 1) × a, что можно проверить равенством N = ⌊ √N⌋  × ⌈ √N⌉, периметр вычисляется как сумма сторон P = 2 × ⌊ √N⌋  + 2 × ⌈ √N⌉.

Иначе, периметр фигуры не станет хуже, если количество квадратов N увеличить на единицу. По индукции, периметр фигуры из N квадратов равен периметру фигуры размера a × a или (a + 1) × a, имеющей минимальное не меньшее N количество квадратов.

Эта фигура имеет размеры либо ⌊ √N⌋  × ⌈ √N⌉ (если N < ⌊ √N⌋  × ⌈ √N⌉), либо ⌈ √N⌉  × ⌈ √N⌉ (если N > ⌊ √N⌋  × ⌈ √N⌉)), а ее периметр соответственно вычисляется как P = 2 × ⌊ √N⌋  + 2 × ⌈ √N⌉ или P = 2 × ⌈ √N⌉  + 2 × ⌈ √N⌉.

Зная периметр, вспомним, что (N × 4 − P) спичек являются С2К, а P спичек — С1К. Поэтому вычисляем количество спичек как P + (N × 4 − P) / 2 = (N × 4 + P) / 2 = N × 2 + P / 2.