Требуется расшифровать запись сложения двух чисел, в котором цифры заменены буквами, причем разные цифры заменены разными буквами, одинаковые - одинаковыми. Предполагается, что исходное равенство верно и записано по обычным правилам арифметики. В частности, в записи числа первая слева цифра не является цифрой 0; используется десятичная система счисления. Ввести ребус в формате ЧИСЛО+ЕЩЕ=СУММА, вывести в столбик все решения в строковом лексикографическом порядке.
ЧИСЛО+ЕЩЕ=СУММА
29348+767=30115 29368+747=30115 59638+474=60112 59678+434=60112 69714+838=70552 69734+818=70552
Сначала я, конечно, написал решение «в лоб», которое (после ввода и подготовки данных) начиналось строкой
Этого достаточно, чтобы любой пример решался менее, чем за минуту, но наши лимиты намного жёстче.
Спойлер:
Я решал задачу рекурсивно по n. Для каждого n делал предположение относительно соответствия n-й буквы одной из оставшихся оставшимся цифр (если буква уже встречалась, значит, в данном месте выбора нет). Затем складывал числовые «хвосты» слагаемых и проверял совпадение с числовым «хвостом» суммы (с точностью до предыдущей цифры). Если совпадения нет, предположение неверно, если есть, можно разбирать случай для n+1 и оставшихся цифр.
Ч11
И9
С6
Л3
О0
+
Е7
Щ4
Е1
С12
У10
М8
М5
А2