Симметричный амфитеатр
Contest: VK Cup 2021 - Квалификация (Engine)
Tags: *special, constructive algorithms, dp

Все готовятся к VK Fest 2021! Для того, чтобы зрителям была лучше видна главная сцена, планируется построить амфитеатр. В этой задаче мы будем рассматривать его сбоку — схематично он будет иметь форму лестницы из $$$n$$$ одинаковых квадратов. Лестница — это одна или более башен квадратов, выстроенных в ряд, где высоты башен невозрастают слева направо.

На следующем рисунке можно видеть три разные фигуры из $$$12$$$ квадратов. Первые две фигуры — лестницы, а третья — нет.

Из эстетических соображений было решено, что амфитеатр должен быть симметричным. Формально, амфитеатр называется симметричным, если при отражении его схемы относительно прямой $$$x = y$$$ получается тот же самый рисунок (где ось $$$x$$$ направлена слева направо, а ось $$$y$$$ — снизу вверх). Например, первая лестница на рисунке выше — симметричная, а вторая — нет.

Кроме того, амфитеатр должен быть максимально компактным — а именно, сторона минимального квадрата, внутрь которого можно его поместить, должна быть как можно меньше.

По заданному числу $$$n$$$ нарисуйте схему амфитеатра из ровно $$$n$$$ квадратов, удовлетворяющую всем условиям.

Input format:
В единственной строке задано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — число квадратов, из которых нужно составить схему амфитеатра.

Output format:
Если не существует схемы амфитеатра из $$$n$$$ квадратов, выведите единственное число $$$-1$$$.

Иначе в первой строке выведите целое число $$$m$$$ — минимальное возможное число строк и столбцов в схеме амфитеатра. Далее выведите $$$m$$$ строк, описывающих схему. Каждая строка должна содержать ровно $$$m$$$ символов 'o' (строчная латинская буква) или '.', где 'o' описывает построенный квадрат, а '.' — пустое место. Схема амфитеатра должна состоять ровно из $$$n$$$ символов 'o'. Ячейка в левом нижнем углу должна содержать квадрат. Если возможных ответов с минимальным $$$m$$$ несколько, выведите любой из них.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
3

Example output:
2
o.
oo

Example input:
17

Example output:
5
o....
ooo..
oooo.
oooo.
ooooo

Editorial:
Найдём минимальное $$$k$$$ такое, что $$$k^2 \ge n$$$. Понятно, что минимальный размер схемы $$$m$$$ не может быть меньше $$$k$$$.
Попробуем нарисовать схему с $$$m = k$$$. Для этого заполним полностью квадратами схему со стороной $$$k$$$, а потом заберём $$$x = k^2 - n$$$ квадратов, чтобы схема осталась корректной. Поскольку мы взяли именно минимальное $$$k$$$, достаточно рассмотреть $$$x < k^2 - (k-1)^2 = 2k-1$$$.
Если $$$x = 0$$$, можно ничего не забирать. Например, при $$$k = 6$$$ схема для $$$n = 36$$$ выглядит так:
Если $$$x = 1, 3, 5, \ldots, 2k-3$$$, можно забрать квадрат в правом верхнем углу, а дальше забирать параллельно по одному квадрату из верхней строки и правого столбца. Например, при $$$k = 6$$$ схемы для $$$n = 35, 33, 31, 29, 27$$$ могут выглядеть так:
Если $$$x = 4, 6, 8, \ldots, 2k-2$$$, можно забрать квадрат $$$2 \times 2$$$ в правом верхнем углу, а дальше, аналогично предыдущему случаю, забирать по одному квадрату из верхней строки и правого столбца. Например, при $$$k = 6$$$ схемы для $$$n = 32, 30, 28, 26$$$ могут выглядеть так:
Наконец, если $$$x = 2$$$, забрать два квадрата из полностью заполненной схемы $$$k \times k$$$ с сохранением условий не получится. В таком случае придётся увеличить размер схемы до $$$m = k+1$$$, а построить такую схему можно, например, забрав четыре квадрата из заполненной схемы размера $$$k \times k$$$ и добавив по одному квадрату в левый верхний и правый нижний углы. Например, при $$$k = 6$$$ схема для $$$n = 34$$$ может выглядеть так:
Построение в последнем случае работает только при $$$k \ge 3$$$, поскольку забрать четыре квадрата из схемы $$$2 \times 2$$$ нельзя. В случае $$$n = 2$$$, когда $$$x = 2$$$ и $$$k = 2$$$, решения не существует и нужно вывести $$$-1$$$.
Пример решения на Python: