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

NEERC 2010, Четвертьфинал Восточного подрегиона

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

D. Винтовки белочехов

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
Белочехи решили прекратить ожесточённые бои в Сибири и вернуться домой. Но покинуть Россию было непросто — чтобы добраться на кораблях из Владивостока в Европу, были нужны деньги. Белочехи решили раздобыть необходимую сумму, продав свои винтовки наступающим войскам красных. Всего на продажу они выставили n винтовок. Первые две винтовки были самыми обычными, и белочехи просили за каждую из них только один рубль. Зато i-я винтовка (i ≥ 3) стоила столько же, сколько (i−1)-я и (i−2)-я вместе взятые.
В стране имеют хождение только банкноты с номиналами, равными степеням числа k (банкноты в один рубль, k рублей, k2 рублей и т. д.) В распоряжении большевиков уже достаточно типографий, поэтому напечатать нужное количество денег не составило труда. Они заплатили за каждую винтовку минимально возможное количество банкнот, в сумме дающее ровно столько, сколько просили за эту винтовку белочехи.
Когда винтовки попали в руки красных, Чапаев попросил Анку упорядочить их по возрастанию количества банкнот, которое было за них заплачено. Если за две винтовки было заплачено одинаковое количество банкнот, то раньше должна идти винтовка с меньшим номером. Помогите Анке выполнить просьбу Чапаева.

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

В единственной строке через пробел записаны целые числа k и n (2 ≤ k ≤ 10; 3 ≤ n ≤ 50000).

Результат

Выведите перестановку чисел от 1 до n — номера винтовок, упорядоченные по возрастанию количества уплаченных за них банкнот.

Пример

исходные данныерезультат
10 8
1 2 3 4 8 7 5 6

Замечания

Когда Анка выполнит просьбу Чапаева, стоимости винтовок в рублях будут выглядеть так: {1, 1, 2, 3, 21, 13, 5, 8}.
Автор задачи: Виктор Камашев
Источник задачи: NEERC 2010, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1803. Винтовки белочехов