Андрей готовился к ЕГЭ по информатике и встретил в демо-версии ЕГЭ 2015 года такую задачу:
Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.
1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).
Пример. Исходное число: 3165. Суммы: 3+1 = 4; 6+5 = 11. Результат: 114.
Укажите наименьшее число, в результате обработки которого автомат выдаст число 1311.
Андрей решил, что для самопроверки он напишет программу, которая решает подобную задачу. Мы думаем, что вы тоже с этим справитесь.
Программа получает на вход некоторое натуральное число N, которое может содержать две, три или четыре цифры.
Программа должна вывести такое наименьшее целое четырёхзначное число K, после применения к которому описанного выше алгоритма получается число N. Если же такого числа не существует, программа должна вывести число 0.