Помогите пожалуйста решить такую задачу:
Задано арифметическое выпажение (сложение или вычитание) над неотрицательными десятичными целыми числами. Синтаксис выражения может быть следующим: первый операнд, оператор (+ или -) второй операнд, символ =, результат оператора (сумма или разность, в соответствии с оператором). Операнд не превышает 999 999 999. Для разности первый операнд должен быть больше или равен второму. В выражении не должно быть пробелов. Прописные латинские буквы замещают некоторые цифры (возможно включая ничего не значащие нули) так, что одинаковые буквы соответству одинаковым цифрам и различные буквы соответствуют различным цифрам. Это гарантирует, что в конце концов такое замещение будет сделано. Задача - восстановить замещенные цифры.
Ввод:
С клавиатуры вводится строка с зашифрованным арифметическим выражением.
Вывод:
Программа должна вывести несколько строк. Каждая строка описывает одно замещение и содержит букву и соответствующую ей цифру. Цифра и буква должны быть отделены ровно одним пробелом. Вывод должен быть отсортирован по возрастанию букв. Букв, не участвующих в замещении в
списке быть не должно. Если задача имеет несколько решений, достаточно вывести одно из них.
Пример
ввода:
103K+G0G1=CG36
вывода:
C 1
G 0
K 5
Есть мнение - перебор. Будут другие варианты?
А задачка-то интересная... Может, чисто из любви к искусству стоит попробовать. Кто её задал и сколько времени даётся?
Теоретически, конечно, можно перебором, но может попасться такое выражение, что перебрать надо будет 10 в 9 степени значений. Преджде чем переходить к перебору, надо попытаться как-то разбить числа на разряды и ещё что-то в том же духе сделать. Если будет время, подумаю.
Эта задачка с городской олимпиады
По идее 1 или 3 секунды.