eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Задача Лойда

Задача Лойда

Лимит времени 1 секунда
Лимит использования памяти 16 MiB

Сэм Лойд — крупнейший американский мастер головоломок. Одна из самых известных его головоломок — это "Игра в пятнадцать". Также он известен как автор множества шахматных задач и задач на разрезание. Вам предлагается решить задачу Лойда про разрезание шахматной доски.

Задана шахматная доска размером n×n. Требуется распилить её на наибольшее количество частей так, чтобы любые две части были различны. Каждая часть должна состоять из одной или нескольких клеток и представлять собой связную по стороне фигуру. Части, отличающиеся только поворотом, считаются одинаковыми. Так, существует две одноклеточных части: черная клетка и белая клетка, и только одна часть, состоящая из двух клеток.

Вот одно из решений оригинальной задачи Лойда про разрезание обычной шахматной доски 8×8 на 18 различных частей:

Входные данные

В единственной строке содержится целое число n, длина стороны доски (1n30).

Выходные данные

В первой строке выведите максимальное количество частей, на которое можно разрезать доску. Далее выведите само разрезание: n строк по n маленьких латинских букв в каждой. Каждая часть должна состоять из одинаковых букв, при этом одну и ту же букву можно использовать для обозначения нескольких частей, но любые две соседние части должны состоять из разных букв. Если существует более одного оптимального разрезания, то можно вывести любое.

Пример

Входные данные #1
8
Выходные данные #1
18
aabbaaab
aacbbdab
bcccdddb
baaacccb
bbczzacd
acazzaad
acczzbcd
aaczzbcc
Автор Сэм Лойд, Игорь Чевдарь
Источник Ural SU Contest. Petrozavodsk Winter Session, February 2009