ПОМОГИТЕ!!!! Задача по программированию

Question

ПОМОГИТЕ!!!! Задача по программированию

.выавыавы Знаток (343), закрыт 8 месяцев назад

6-Скрытый смысл
Ограничение времени: 3 с
Ограничение реального времени: 6 с
Ограничение памяти: 256M
Задача [C] 6: Скрытый смысл
Условие задачи (pdf)

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

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

Пример ребуса:

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

Более формально:

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

Любым двум одинаковым буквам соответствуют одинаковые цифры, а любым двум разным буквам – разные цифры.

Формат входных данных
Даны 3 строки, состоящие из строчных латинских букв. Каждая строка имеет длину от 1 до 10.

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

Примеры
Входные данные
x
y
z
Выходные данные
1
2
3
Входные данные
a
b
a
Выходные данные
UNSOLVABLE
Входные данные
win
lose
game
Выходные данные
530
6891
7421
Входные данные
four
seven
eight
Выходные данные
UNSOLVABLE
Входные данные
love
hate
feel
Выходные данные
4352
1872
6224

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')

Answer 2

‮‮sultan churkabek‮‮ Мыслитель (6606) 8 месяцев назад

ещё чё сделать?

Answer 3

nikolajminenko Гуру (2761) 8 месяцев назад

Почему бы не использовать нейросеть

.выавыавыЗнаток (343) 8 месяцев назад

так я пробовал говорит что не правильно

Папа Высший разум (154840) Сергей Соколов, так реши это перебором, делов-то. Если в строках больше 10 различных букв, то в сад (т.е. UNSOLVABLE). Для букв на первом месте строк исключаем нули, а последняя цифра третьей строки должна быть суммой последних цифр первых двух строк по модулю 10.

ПапаВысший разум (154840) 8 месяцев назад

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

.выавыавыЗнаток (343) 8 месяцев назад

так она вообще то решила препедующие 5 задач

Папа Высший разум (154840) Сергей Соколов, не решила, а нагуглила что-то похожее по ключевым словам. Иногда найденный код решает задачу, но как правило - наименее эффективным способом, потому что большинство так решает, а нейросеть ориентируется по большинству вариантов.

Answer 4

GVit Профи (566) 8 месяцев назад

1 вопрос и смогу доделать: Цифры к буквам любые?

Алгеброид ГеометриевичУченик (124) 8 месяцев назад

Да, к каждой уникальной букве - своя цифра

GVitПрофи (566) 8 месяцев назад

но какая не важно?
(почти готово завтра могу)

Пётр ДрачевУченик (103) 8 месяцев назад

ДАДАДАД НЕ ВАЖНО, ТО ЕСТЬ К КАЖДОЙ БУКВЕ УНИКАЛЬНАЯ ЦИФРА, ТОЛЬКО НЕ 0 ЕСЛИ ОН ВПЕРЕДИ, ЕЩЕ
a
b
a
Выходные данные
UNSOLVABLE
ВОТ ТАКАЯ ТЕМА, ТО ЕСТЬ ЧИСЛО НЕ МОЖЕТ БЫТЬ РАВНУ 0