Напиши программу. Ограничение времени 3 секунды Ограничение памяти 64Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt Маша и Витя запоминают слова английского языка в оригинальной игровой форме. За день им нужно выучить n слов, 20 ≤ n ≤ 100, каждое из которых имеет длину от 5 до 8 символов. Маша выбирает из этого набора наугад несколько попарно различных слов (так же от 5 до 8) и собирает их в одну строку без пробелов. Далее она переставляет буквы в этой строке так, что слова оказываются полностью перепутанными и дает эту строку Вите. Теперь Витя должен восстановить все слова, которые выбрала Маша. Но у Вити плохо получается, а Маша уже забыла какие слова она выбрала. Нужно им помочь — написать программу, которая восстановит слова, которые были выбраны Машей. Формат ввода В первой строке находится строка, которую Маша предложила Вите. Во второй строке содержится число n — количество слов, которые нужно выучить детям, 20 ≤ n ≤ 100. В следующих n строках содержатся эти слова по одному в строке. Все слова в этом наборе различны. Слова отсортированы в лексикографическом (алфавитном) порядке. Все слова состоят из маленьких букв от 'a' до 'z'. Обратите внимание, что в тестах к этой задаче все заданные слова реально существуют в английском языке и случайным образом выбраны из словаря. Гарантируется, что длина каждого слова из предложенного набора (словаря) в пределах от 5 до 8, строка, которую получила Маша может быть получена путем перестановки букв некоторых различных слов из предложенного словаря, причем набор выбранных Машей слов определяется по ней однозначно. Количество слов, из которых составлена Машина строка находится в пределах от 5 до 8. Формат вывода Вывести все слова, выбранные Машей, в алфавитном порядке по одному в строке.

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

1. Считать входные данные.
2. Сформировать все возможные комбинации слов, длина которых будет составлять от 5 до 8.
3. Проверить, какие комбинации составляют перемешанную строку.
4. Вывести найденные слова в алфавитном порядке.

Вот пример реализации на Python:

from itertools import permutations

# Функция для считывания входных данных
def read_input():
    with open("input.txt", "r") as file:
        mixed_string = file.readline().strip()
        n = int(file.readline().strip())
        words = [file.readline().strip() for _ in range(n)]
    return mixed_string, words

# Функция для проверки, можем ли из слов составить перемешанную строку
def can_form_mixed_string(words, mixed_string):
    combined_string = ''.join(words)
    return sorted(combined_string) == sorted(mixed_string)

# Основная функция
def main():
    mixed_string, words = read_input()
    result = []
    
    # Генерируем все возможные сочетания слов длиной от 5 до 8
    for r in range(5, 9):
        for combination in permutations(words, r):
            if can_form_mixed_string(combination, mixed_string):
                result = sorted(combination)
                break
        if result:
            break
    
    # Вывод результата в файл output.txt
    with open("output.txt", "w") as file:
        for word in result:
            file.write(word + "\n")

# Запуск программы
if __name__ == "__main__":
    main()

Пояснение кода:

1. read_input: Эта функция читает данные из файла input.txt. Она возвращает перемешанную строку и список слов.
2. can_form_mixed_string: Проверяет, можно ли составить перемешанную строку из данного набора слов. Для этого объединяем все буквы из слов и сравниваем их с перемешанной строкой, отсортировав их для удобства сравнения.
3. main: Основная логика программы. Мы рассматриваем все сочетания слов длиной от 5 до 8 и проверяем, можно ли получить перемешанную строку из этих слов. Как только мы находим подходящее сочетание, сохраняем его и перебираем дальше.
4. Результат записывается в файл output.txt в алфавитном порядке.

Обязательно протестируйте программу с различными входными данными, чтобы убедиться в ее корректности!