Олимпиадный тренинг

Задача . E. Выражение


Задача

Темы: дп *2400

Однажды Вася решал арифметические примеры. Он записал в тетради выражение a + b = c. Когда учитель проверил Васину тетрадь, выяснилось, что этот пример он решил неправильно. Теперь Вася оправдывается, что он просто забыл записать несколько цифр в числах a, b и c, но вспомнить, какие же тогда на самом деле были числа, у него не получается. Помогите Васе — найдите такие числа x, y и z, что:

  • x + y = z,
  • из выражения x + y = z можно вычеркиванием некоторых цифр получить a + b = c,
  • выражение x + y = z должно иметь минимальную длину.
Входные данные

В первой и единственной строке записано выражение a + b = c (1 ≤ a, b, c ≤ 106, a, b и c не содержат лидирующие нули) — выражение, которое было записано у Васи.

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

Выведите корректное выражение x + y = z (x, y и z — неотрицательные числа без лидирующих нулей). Выражение a + b = c должно встречаться в x + y = z как подпоследовательность. Выводимое решение должно иметь наименьшее возможное число символов; если же таких решений несколько, можно вывести любое.


Примеры
Входные данныеВыходные данные
1 2+4=5
21+4=25
2 1+1=3
1+31=32
3 1+1=2
1+1=2

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя