Ученик
11 класса Петя Булочкин очень увлекается кодированием информации. Один
раз, когда за завтраком он поедал очередную булочку и размышлял на любимую
тему, ему в голову пришла увлекательная мысль: «Можно так закодировать
информацию, что ее потом никто, даже я сам, не сможет раскодировать».
Какая польза от такого способа кодирования, Петя не знал, но мысль
показалась ему очень интересной. Через неделю в гимназии, где он учился,
должна была пройти научная конференция, и Петя решил выступить на ней с
докладом.
«Я
изобрел принципиально новый способ кодирования, который невозможно
раскодировать, – говорил Петя. – Правда, пока мой способ работает только
для числовой информации. Пусть у нас есть число N из t цифр (в десятичной системе
счисления). Вычеркивая из этого числа цифры всеми возможными способами, мы
будем получать другие числа. Заметьте, что не вычеркивать ни одной цифры –
тоже способ. Будем считать, что если вычеркнуть все цифры, то остаток
равен нулю. Найдем сумму этих чисел – это и будет код числа N».
Раздались громкие
аплодисменты докладчику. А затем посыпались вопросы, на которые Петя
успешно отвечал. Но одно замечание поставило его в затруднительное
положение: «Если мы будем реализовывать твой алгоритм на компьютере, то
уже для числа из 100 цифр, он будет работать очень долго. За всю свою
жизнь ты не закодируешь своим методом ни одного числа из 100 цифр. Твой
алгоритм нельзя применить на практике». Надо было спасать положение. «А
вот и нет. Завтра я принесу реализацию своего метода, которая будет
кодировать числа из 100 знаков не более чем за 1 секунду», - таков был
ответ Пети.
На
этом все и закончилось, однако написать такой программы Петя не мог.
Поэтому написать ее придется вам. Но перед этим рассмотрим Петин метод на
примере. Пусть N =109. Полученные после
вычеркивания числа показаны в таблице:
Номера вычеркиваемых цифр
Оставшееся число
–
109
1
09
2
19
3
10
1, 2
9
1, 3
0
2, 3
1
1, 2, 3
0
Поэтому
число 109 будет кодироваться числом 157.
Задание. По введенному числу
N (1<=N<=10100 )
определить число S – код числа N (при Петином методе
кодирования).
Ввод. Входные данные состоят из
одной строки, в которой расположено число N. Левая цифра числа N– не ноль.
Вывод. Вы должны вывести число
S – код числа
N. Не выводите
лидирующие (левые) нули.