Задача 102926

Тема:    [ Перебор с отсечениями ]

Сложность: 3 Классы: Название задачи: Ребус .

Условие

Арифметический ребус – это зашифрованная запись сложения двух натуральных чисел (например, КОМП+КОМП=СБОРЫ). При этом одинаковым буквам должны соответствовать одинаковые цифры, разным – разные, и ни одно из чисел не может начинаться с нуля. Требуется написать программу, находящую все возможные решения такого ребуса. 

Входные данные
Входной файл содержит единственную строку с записью ребуса. Длина строки не превышает 30 символов.

Выходные данные
Первая строка выходного файла должна содержать число возможных решений ребуса, а остальные – список решений в алфавитном порядке. Каждое решение должно быть выведено не более одного раза.

Пример входного файла
ЛЕТО+ЛЕТО=ПОЛЕТ

Пример выходного файла
1
8947+8947=17894

Решение

Скачать архив тестов и решений

Логично организовать перебор, переходя от младших разрядов к старшим. В процессе перебора для каждой еще не известной буквы храним множество значений, которые она может принимать. По виду ребуса можно сразу же сделать некоторые заключения. Например, первая буква числа не может  равняться нулю. Если длина суммы на единицу больше, чем длина наибольшего из слагаемых, то первой ее цифрой может быть только единица. Если на i-м месте первого числа стоит буква A, а на i-м месте второго числа и суммы стоит буква B, то значением A может быть только 0 или 9, и т.д.

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

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