ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102780
Тема:    [ Динамическое программирование (прочее) ]
Сложность: 3
Классы:
Название задачи: Уравнение с пропущенными цифрами .
В корзину
Прислать комментарий

Условие

Задано уравнение вида 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)-й с конца разряд, во второй – его наличия.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 1
Название Динамическое программирование
Задача
Номер 3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .