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

Соревнование школьников. Октябрь 2005

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

A. Сотовые символы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Знаменитый гангстер Вито Маретти получил подарок от шефа полиции — последнюю модель сотового телефона Gnusmas. Телефон имеет много навороченных функций, большинство из которых не нужны обычному гангстеру. Но есть и полезные функции. Одна из таких — возможность вставки дополнительных символов в SMS.
Она устроена так: если требуется ввести символ, которого нет на клавиатуре, Вито должен сначала нажать клавишу "*". После этого появляется N дополнительных символов. Они записаны в виде таблицы с M столбцами. Все строки этой таблицы, кроме последней, содержат ровно M символов, последняя строка может содержать от 1 до M символов. Изначально курсор стоит на левом верхнем символе.
[.] , ! ? _
+ - " = *
( ) /    
В этом примере N = 13, M = 5. Курсор обозначен как "[x]".
Клавишами ВЛЕВО, ВПРАВО, ВНИЗ, ВВЕРХ курсор можно передвигать по таблице соответственно влево, вправо, вниз и вверх. Кроме того, клавиша ВЛЕВО перемещает курсор из первого символа в ряду на последний символ в предыдущем ряду, ВПРАВО — из последнего символа в ряду на первый символ в следующем ряду. Из первого символа в первом ряду с помощью клавиши ВЛЕВО можно попасть в последний символ в последнем ряду, из последнего символа в последнем ряду с помощью клавиши ВПРАВО можно попасть в первый символ в первом ряду. Таким образом, за несколько нажатий клавиш можно выбрать любой символ.
В примере из клетки с символом "." за один шаг можно перейти в клетки с символами ",", "+", "/" (при этом кнопка ВВЕРХ оставит курсор на месте); из клетки с символом "*" — в клетки с символами "=", "_", "(" (при этом кнопка ВНИЗ оставит курсор на месте).
Даже для гангстера не трудно понять, что курсор в начале ставится не на оптимальное место. Ведь среднее значение количества нажатий клавиш для выбора какого-либо символа не минимально. Вито был крайне возмущен этим фактом. Если он теперь захочет послать SMS шефу полиции, то ему придется лишний раз нажимать на клавиши. Но не отказываться же от подарка. Вито решил шантажировать Вас, чтобы Вы перепрограммировали его телефон.

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

Числа N и M (1 ≤ N ≤ 256; 1 ≤ M ≤ min(N, 20)).

Результат

В первой строке выведите "Mean = X", где X — среднее количество нажатий клавиш при наилучшем начальном положении курсора с точностью до двух знаков после запятой. Затем выведите N чисел, по M в одной строке — минимальное количество нажатий клавиш, необходимое для выбора каждого из символов, при найденном начальном положении курсора. Если вариантов с наименьшим средним несколько, выведите любой из них.

Пример

исходные данныерезультат
5 3
Mean = 1.00
1 0 1
2 1
Автор задачи: Владимир Яковлев
Источник задачи: XII командный чемпионат школьников Свердловской области по программированию (15 октября 2005 года)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1400. Сотовые символы