Задача B. Числовая последовательность ≡

Условие

Дима недавно поступил на работу в Научно-исследовательский институт числовых последовательностей. Как следует из названия этого института, основным направлением его работы является проведение различных исследований в области числовых последовательностей.

Недавно руководитель отдела, где начал работать Дима, столкнулся с весьма интересной последовательностью чисел a₁, a₂, …, a_n, …, которая определяется следующим образом: a₁ = 0 и каждое последующее число a_i + 1 (i ≥ 1) определяется как наименьшее натуральное число, большее a_i, десятичная запись которого не содержит цифр, представленных в десятичной записи a_i. Требуется написать программу, которая заданному n вычисляет величину a_n.

Формат входного файла

Входной файл содержит целое число n.

Формат выходного файла

Выходной файл должен содержать число a_n.

Ограничения

1 ≤ n ≤ 500

Примеры тестов

1

0

28

911

Разбор

Решение задачи предполагает нахождение элементов последовательности, описанной в условии, в порядке перечисления.

Заметим, что каждое число последовательности обладает следующим свойством: в десятичной записи все его цифры, кроме первой, равны. Действительно, предположим, что в некотором элементе последовательности найдутся две различные цифры, ни одна из которых не стоит на старшей позиции. Тогда большую из них можно уменьшить и при этом число по-прежнему будет больше предыдущего элемента последовательности. Получили противоречие.

Таким образом, для нахождения следующего числа достаточно перебрать первую цифру числа, вторую цифру, а также его длину (количество цифр очередного числа равно или на единицу больше количества цифр предыдущего числа последовательности). После этого необходимо найти наименьшее из чисел, удовлетворяющих требованием задачи (множества цифр очередного числа и предыдущего числа последовательности не должны пересекаться).