Помогите решить задачу по программированию(питон) Задача [C] 6: Скрытый смысл

Question

Помогите решить задачу по программированию(питон) Задача [C] 6: Скрытый смысл

@Ghirardellig Ученик (172), закрыт 2 месяца назад

Шестиклассница Лиза любит искать везде скрытый смысл. Недавно на кружке математики она научилась решать числовые ребусы.

Числовой ребус – это задача, условие которой записывается, как сложение двух чисел в столбик, но вместо чисел записаны слова. Чтобы решить ребус, нужно заменить каждую букву ребуса на цифру, так чтобы в итоге получилось верное равенство. (При этом каждая цифра может соответствовать только одной букве.) Ребус может иметь одно или несколько подходящих решений, а также не иметь решений вовсе.

Лиза думает, что если ребус имеет решение, то слова, из которых он состоит, имеют скрытую связь. Она придумала уже целую кучу слов, которые она хочет проверить на наличие скрытой связи, и составила из них ребусы. Однако решение некоторых ребусов может занять очень много времени, поэтому Лиза просит вас помочь ей и написать программу, которая найдет решение для каждого ребуса или скажет, что его не существует.

Более формально:
Сопоставьте каждой из 3 строк S1, S2, S3, положительные числа N1, N2, N3, так что выполнено
следующее:
• Si имеет такую же длину, как Ni (в десятичной записи).
• В записи чисел N1, N2, N3 нет ведущих нулей.
• Любым двум одинаковым буквам соответствуют одинаковые цифры, а любым двум разным
буквам – разные цифры.

Формат входных данных
Даны 3 строки, состоящие из строчных латинских букв. Каждая строка имеет длину от 1 до 10.
Формат выходных данных
Если решения не существует – выведите UNSOLVABLE, иначе выведите три числа (каждое в
отдельной строке) – ответ на задачу.

Пример
win
lose
game
Ответ
530
6891
7421

Answer 1

Держи. Алгоритм поиска с возвратом. Считаем полным перебором, да ещё и на Питоне, поэтому получается не шибко быстро. Но может, в твои лимиты времени уложится.

 def tryit(a, b, c, i, j, k, dig, let):
    while i >= 0 and dig[ord(a[i])-ord('a')] != -1: i -= 1
    while j >= 0 and dig[ord(b[j])-ord('a')] != -1: j -= 1
    while k >= 0 and dig[ord(c[k])-ord('a')] != -1: k -= 1
    if i >= 0:
        l = a[i]
        i -= 1
    elif j >= 0:
        l = b[j]
        j -= 1
    elif k >= 0:
        l = c[k]
        k -= 1
    else:
        an = int(''.join(str(dig[ord(f)-ord('a')]) for f in a))
        bn = int(''.join(str(dig[ord(f)-ord('a')]) for f in b))
        cn = int(''.join(str(dig[ord(f)-ord('a')]) for f in c))
        return (an, bn, cn) if an + bn == cn else ('UNSOLVABLE',)
    m = ord(l) - ord('a')
    for d in range(10):
        if let[d] is None:
            let[d] = l
            dig[m] = d
            t = tryit(a, b, c, i, j, k, dig, let)
            if len(t) == 3: return t
            let[d] = None
            dig[m] = -1
    return ('UNSOLVABLE',)

a, b, c = map(input, ('',) * 3)

dig = [-1] * 26
let = [None] * 10
present = 0

for l in a:
    present |= 1 << (ord(l) - ord('a'))
for l in b:
    present |= 1 << (ord(l) - ord('a'))
for l in c:
    present |= 1 << (ord(l) - ord('a'))

r = tryit(a, b, c, len(a)-1, len(b)-1, len(c)-1, dig, let) if present.bit_count() <= 10 else ('UNSOLVABLE',)
print(*r, sep='\n')

P.S. На твоих тестовых данных возможно несколько правильных ответов. Программа выведет не тот, который приведён у тебя.