Мадока наконец-то узнала пароль от своего компьютера. Но так как ее отец известный популяризатор математики, то пароль — это ответ на следующую задачу:
Требуется узнать максимальное число, сумма цифр в десятичной записи которого равна \(n\), а также в его десятичной записи нет нулей и подряд идущих одинаковых цифр.
Так как Мадока уже устала от математики, то помогите ей решить эту задачу!
Примечание
Все числа с суммой цифр \(2\) без нулей в записи: \(2\), \(11\). Но последнее не подходит, так как в нем \(2\) единицы подряд. Поэтому ответ \(2\).
Все числа с суммой цифр \(3\) без нулей в записи: \(111\), \(12\), \(21\), \(3\). Первое не подходит, так как в нём две едицины подряд, поэтому максимальное число \(21\).
Все числа с суммой цифр \(4\) без нулей в записи: \(1111\), \(211\), \(121\), \(112\), \(13\), \(31\), \(22\), \(4\). Числа \(1111\), \(211\), \(112\), \(22\) не подходят, так как в них есть одинаковые подряд идущих цифр. А среди остальных максимальное число — \(121\).