Encoding
Турнир за Купата на Декана, 2014
Time Limit: 0.1s, Memory Limit: 64MiB
Ели изобрети нов метод за кодиране на числа. За да види колко надежден е той, тя показа на Крис неговата употреба в редицата 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211 и поиска от приятелката си да намери кое е следващото число. За нейна изненада Крис отговори почти веднага – числото, очевидно, е 31131211131221.

Окей де, може би не толкова очевидно. Крис е забелязала, че всяко следващо число се получава като се вземе предходното, раздели се на под-интервали, съставени от една и съща цифра (например 13112221 -> 1, 3, 11, 222, 1), и после се запише колко пъти се среща цифрата във всеки от интервалите, както и самата цифра в интервала. Тоест "един път 1" (11), "един път 3" (13), "два пъти 1" (21), "три пъти 2" (32), "един път 1" (11) = 1113213211.

За да изтрие мазната усмивка от лицето на Кристина, Ели сега измисли друга задача. По дадено неотрицателно цяло число X, тя иска от нея да намери най-малкото неотрицателно цяло число, което на някоя стъпка би генерирало X по горния алгоритъм. Например, ако даденото число е 31131211131221, отговорът трябва да е 1. Ако пък числото е 42, отговорът трябва да е 42. Забележете, че 2222 би генерирало 42, но 42 е по-малко и би било реалният отговор.

За да се избегне двузначност, Ели добави правилото, че никое от числата в поредицата няма да съдържа повече от девет последователни еднакви цифри. С други думи, нито даденото от нея число, нито намереното от вас, нито което и да е от числата между тях (ако има такива) съдържа повече от девет последователни еднакви цифри.

Помогнете на Крис да реши и тази задача.
Вход
На стандартния вход ще бъде зададено едно неотрицателно цяло число X.
Изход
На стандартния изход изведете най-малкото неотрицателно число, което след нула или повече стъпки на алгоритъма на Ели води до X.
Ограничения
  • 0 ≤ X ≤ 1,000,000,000,000,000,000
Примерен Вход Примерен Изход
311312111312211
1112211
4242
311012111011
132114311331121432
13371337
Забележете, че число преди 1011 не може да има, тъй като то би било 01, което не е валидно цяло число. Също така забележете, че числото преди 1337 е 3777, а число преди 3777 не може да има, тъй като би нарушило правилото на Ели за повече от 9 последователни еднакви цифри.
Мрън!