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

1708. Сумма цифр 2

Ограничение времени: 5.0 секунды
Ограничение памяти: 64 МБ
Как известно, Петька очень любит арифметику. Он много раз загадывал положительное целое число и сообщал Чапаеву сумму его цифр, а также сумму квадратов его цифр. Чапаев всегда без особых раздумий называл наименьшее число, удовлетворяющее этим требованиям. Но Петька всегда получал в ответ не то число, которое загадывал. Что же с этим делать? Как бы загадать такое число, чтобы Чапаев назвал именно его?
Петька обратился за помощью к Фурманову. Он попросил научить его определять, является ли число наименьшим с заданными суммами цифр и квадратов цифр. Фурманов был не прочь порешать на досуге математические ребусы и отнёсся к этой задачке с большим интересом. Немного поразмыслив, он понял, что от порядка цифр эти суммы не зависят, а значит, в «наименьших» числах цифры всегда идут по возрастанию. И ещё из этого следует, что нулей в таких числах не бывает. Уже всерьёз занявшись задачей, он обнаружил и такое свойство: если из «наименьшего» числа вычеркнуть несколько цифр, то снова получится «наименьшее» число.
И тут Фурманов понял, что может выписать несколько шаблонов, которые будут определять все числа, интересующие Петьку. Для этого ему будет достаточно таких шаблонов, в которых кроме цифр встречаются звёздочки, означающие, что предыдущая цифра может повторяться произвольное количество раз (в т. ч. вообще отсутствовать).
Фурманов взял вчерашний номер «Правды» и на полях выписал шаблоны. Список был таким, что любое «наименьшее» число обязательно подходит хотя бы под один из шаблонов, и в то же время любое число, подходящее под шаблоны, является «наименьшим». При этом список оказался ещё и самым коротким из возможных. А вы смогли бы повторить столь героический поступок Фурманова?

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

Входные данные содержат единственное целое число — основание системы счисления, для которой нужно составить такой список (от 2 до 36).

Результат

Выведите список шаблонов, отсортированный по возрастанию по обычным правилам. Каждый шаблон может содержать только цифры данной системы счисления (1, 2, …, 9, A, B, …) и звёздочку. Шаблоны не должны содержать лишние элементы: вместо шаблона «12*2*3» следует выводить «12*3». Допускается, что пустая строка может подходить под некоторые шаблоны.

Пример

исходные данныерезультат
4
1*2*
112*3*
12*3*
2*3*

Замечания

Числа 222 и 1113 имеют одинаковые сумму цифр и сумму квадратов цифр. Поэтому любое число, содержащее три единицы и одну тройку, можно «уменьшить», сохранив при этом суммы цифр и квадратов цифр.
Автор задачи: Владимир Яковлев
Источник задачи: XIII чемпионат Урала по спортивному программированию, 4 апреля 2009 г.