Решение на питон С++

Question

Маша и Витя запоминают слова английского языка в оригинальной игровой форме. За день им нужно выучить n слов, 20 ≤ n ≤ 100, каждое из которых имеет длину от 5 до 8 символов. Маша выбирает из этого набора наугад несколько попарно различных слов (так же от 5 до 8) и собирает их в одну строку без пробелов. Далее она переставляет буквы в этой строке так, что слова оказываются полностью перепутанными и дает эту строку Вите. Теперь Витя должен восстановить все слова, которые выбрала Маша. 
 
Но у Вити плохо получается, а Маша уже забыла какие слова она выбрала. Нужно им помочь — написать программу, которая восстановит слова, которые были выбраны Машей. 
 
Формат ввода 
В первой строке находится строка, которую Маша предложила Вите. Во второй строке содержится число n — количество слов, которые нужно выучить детям, 20 ≤ n ≤ 100. 
 
В следующих n строках содержатся эти слова по одному в строке. Все слова в этом наборе различны. Слова отсортированы в лексикографическом (алфавитном) порядке. Все слова состоят из маленьких букв от 'a' до 'z'. Обратите внимание, что в тестах к этой задаче все заданные слова реально существуют в английском языке и случайным образом выбраны из словаря. 
 
Гарантируется, что длина каждого слова из предложенного набора (словаря) в пределах от 5 до 8, строка, которую получила Маша может быть получена путем перестановки букв некоторых различных слов из предложенного словаря, причем набор выбранных Машей слов определяется по ней однозначно. Количество слов, из которых составлена Машина строка находится в пределах от 5 до 8. 
 
Формат вывода 
Вывести все слова, выбранные Машей, в алфавитном порядке по одному в строке. 
 
Пример 
Ввод	Вывод 
stirbaexsudueoeidgomttcrnrwlunapntetacwri 
24 
bridge 
cranky 
document 
drawing 
farmer 
fighter 
figurine 
gravy 
havoc 
minimum 
reactant 
reply 
republic 
sonata 
soprano 
split 
subset 
tailor 
texture 
tomorrow 
trout 
vicinity 
wrist 
writer 
document 
drawing 
republic 
sonata 
texture 
wrist

Egor · Answer

Чат гпт уже не помогает?

Виталя Курылёв · Answer

from collections import defaultdict 
 
def восстановить_слова(перемешанная_строка, слова): 
    &#34;&#34;&#34; 
    Восстанавливает слова, которые были выбраны Машей, из перемешанной строки. 
 
    Args: 
        перемешанная_строка: Строка, которую Маша дала Вите. 
        слова: Список слов, которые Маша и Витя должны выучить. 
 
    Returns: 
        Список слов, выбранных Машей. 
    &#34;&#34;&#34; 
 
    частоты_букв = defaultdict(int) 
    for буква in перемешанная_строка: 
        частоты_букв[буква] += 1 
 
    выбранные_слова = [] 
    for слово in слова: 
        частоты_букв_в_слове = defaultdict(int) 
        for буква in слово: 
            частоты_букв_в_слове[буква] += 1 
 
        соответствие = True 
        for буква, количество in частоты_букв_в_слове.items(): 
            if частоты_букв[буква] < количество: 
                соответствие = False 
                break 
 
        if соответствие: 
            выбранные_слова.append(слово) 
            for буква, количество in частоты_букв_в_слове.items(): 
                частоты_букв[буква] -= количество 
 
    return выбранные_слова 
 
# Ввод данных 
перемешанная_строка = input() 
n = int(input()) 
слова = [] 
for _ in range(n): 
    слова.append(input()) 
 
# Вывод результата 
выбранные_слова = восстановить_слова(перемешанная_строка, слова) 
выбранные_слова.sort() 
for слово in выбранные_слова: 
    print(слово)

Resurce InheiT · Answer

from collections import Counter 
 
mixed_word = input() 
n = int(input()) 
words = [input() for _ in range(n)] 
 
mixed_count = Counter(mixed_word) 
mixed_len = len(mixed_word) 
 
result = [] 
 
def solve(current_words, current_len): 
    if current_len == mixed_len: 
        counts = Counter(&#34;&#34;.join(current_words)) 
        if counts == mixed_count: 
            result.extend(sorted(current_words)) 
        return 
     
    if current_len > mixed_len: 
        return 
 
    for word in words: 
        if word not in current_words: 
            solve(current_words + [word], current_len + len(word))

solve([], 0) 
 
for word in sorted(list(set(result))): 
    print(word)