Задача 102780
|
Название задачи: Уравнение с пропущенными цифрами . |
 |
Условие
Задано уравнение вида A + B = C, где A, B и C – неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса (?). Примером такого уравнения является ?2+34=4?. Требуется так подставить вместо знаков вопроса цифры, чтобы это равенство стало верным, либо определить, что это невозможно.Входные данные
Заданное уравнение содержится в первой строке входного файла. Длина уравнения не превышает 80 символов. Входной файл не содержит пробелов.
Выходные данные
В выходной файл требуется вывести верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение «решения не существует».
Пример входного файла
??2?4+9?=355
Пример выходного файла
00264+91=355
Решение
Скачать архив тестов и решенийПусть N – максимальное число разрядов, которое могут иметь числа из уравнения. По очереди для последних k = 1, 2, ..., N разрядов уравнения решаем две подзадачи, аналогичные исходной, но затрагивающие лишь последние k разрядов уравнения. В первой из этих подзадач требуем отсутствия переноса в (k+1)-й с конца разряд, во второй – его наличия.
