| Автор: | Антон Карабанов, Андрей Баранов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход |
Тимофей с друзьями разрабатывает компьютерную игру "Свитки древних". Первой загадкой для игрока, очнувшегося в тюремной камере, будет автомат, который блокирует дверь. У автомата есть экран, на котором написано шестизначное число n с ведущими нулями и три кнопки. Нажатие на первую кнопку увеличивает число на 1 (если в результате получается 1000000, то на экране будет отображаться число 0 в виде 000000). Нажатие на вторую кнопку уменьшает число на 1 (если в результате получается -1, то на экране будет отображаться число 999999). Нажатие на третью кнопку упорядочивает цифры на экране в порядке возрастания. Например, если на экране было число 000618, то станет 000168, если было 500002, то станет 000025, если было 777777, то число не изменится. Дверь откроется, если на экране появится число m. При этом требуется наименьшее количество нажатий на кнопки.
Тимофей убеждает друзей, что n и m должны подбираться для каждого игрока случайным образом. Друзья возражают ему, что в этом случае требуемая последовательность нажатий кнопок для некоторых входных данных будет слишком длинной, что в конечном итоге отрицательно скажется на рейтинге игры. Помогите ребятам: составьте программу, которая по начальному числу n определит конечное число m, для которого требуемая последовательность нажатий наиболее длинная.
Единственная строка входного файла содержит натуральное число n (без ведущих нулей).
Выведите в первой строке натуральное число m — ответ на вопрос задачи. Если таких чисел несколько, выведите их через пробел в порядке возрастания. Во второй строке выведите одно натуральное число — наименьшее количество нажатий на кнопки для получения m из n.
1 ≤ n ≤ 999999
В первом примере дано начальное n = 12. Наиболее длинная последовательность нажатий потребуется для достижения числа 949998, чтобы до него добраться потребуется 50006 нажатий на кнопки — больше, чем до любого другого числа.
Во втором примере дано начальное n = 949998. Искомых чисел оказалось сразу два.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|