Счастливый билет

Счастливый билет – это такой номер автобусного билета, состоящий из чётного количества десятичных цифр, в котором сумма первой половины цифр совпадает с суммой последней. При этом известно, что все номера билетов состоят из одинакового числа цифр и могут иметь ведущие нули. Например, если в записи билета используется 4 цифры, то билет с номером 123 будет записан как 0123. Билеты на каждой ленте нумеруются от 00…01 до 99…99. Таким образом, в ленте всего 10^K-1 билетов, где K – количество используемых цифр. Билеты 2112 и 051312 счастливые, а 9993 и 74 – нет.

Однажды Вася зашел в автобус и получил билет с номером N. Поскольку Васе было далеко ехать и делать в автобусе особо нечего, то он задумался: с каким номером будет следующий счастливый билет, который будет выдан из той же ленты, что и билет у Васи.

Входные данные

Входной файл INPUT.TXT содержит целое число N – номер билета, который получил Вася. Данный номер может содержать лидирующие нули. Гарантируется, что количество цифр в записи числа N чётно и не превосходит 10⁵.

Выходные данные

В выходной файл OUTPUT.TXT выведите номер следующего счастливого билета из текущей ленты в таком же формате, как и во входных данных. Если такого билета не существует, выведите номер минимального счастливого билета из новой ленты.

Примеры

Система оценки

Решения, работающие только для 4-значных билетов, будут оцениваться в 20 баллов.

Решения, работающие только для 4-значных и 8-значных билетов, будут оцениваться в 40 баллов.

Решения, работающие только для билетов, состоящих не более чем из 16 цифр, будут оцениваться в 60 баллов.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]