ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU contest. Petrozavodsk training camp. Winter 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Задача Лойда

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Сэм Лойд — крупнейший американский мастер головоломок. Одна из самых известных его головоломок — это «Игра в пятнадцать». Также он известен как автор множества шахматных задач и задач на разрезание. Вам предлагается решить задачу Лойда про разрезание шахматной доски.
Задана шахматная доска размером n × n. Требуется распилить её на наибольшее количество частей так, чтобы любые две части были различны. Каждая часть должна состоять из одной или нескольких клеток и представлять собой связную по стороне фигуру. Части, отличающиеся только поворотом, считаются одинаковыми. Так, существует две одноклеточных части: черная клетка и белая клетка, и только одна часть, состоящая из двух клеток.
Вот одно из решений оригинальной задачи Лойда про разрезание обычной шахматной доски 8 × 8 на 18 различных частей:
Problem illustration

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
8
18
aaaacaaa
bbbcccba
baddabbb
aacdacba
accdacaa
babdccbb
baaadbba
babbaaaa
Автор задачи: Сэм Лойд, Игорь Чевдарь
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, February 2009
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1693. Задача Лойда