Ускорить код

@Sasuna · Регистрация: 14.12.2023

Студворк — интернет-сервис помощи студентам

Решил задачу но проходит 5/30 тестов из за лимита времени.
Ограничение времени 3 секунды, 25 тестов проходит за 3.086 с.
Задача:
Маша и Витя запоминают слова английского языка в оригинальной игровой форме. За день им нужно выучить n слов, 20 ≤ n ≤ 100, каждое из которых имеет длину от 5 до 8 символов. Маша выбирает из этого набора наугад несколько попарно различных слов (так же от 5 до 8) и собирает их в одну строку без пробелов. Далее она переставляет буквы в этой строке так, что слова оказываются полностью перепутанными и дает эту строку Вите. Теперь Витя должен восстановить все слова, которые выбрала Маша.

Но у Вити плохо получается, а Маша уже забыла какие слова она выбрала. Нужно им помочь — написать программу, которая восстановит слова, которые были выбраны Машей.

Формат ввода
В первой строке находится строка, которую Маша предложила Вите. Во второй строке содержится число n — количество слов, которые нужно выучить детям, 20 ≤ n ≤ 100.

В следующих n строках содержатся эти слова по одному в строке. Все слова в этом наборе различны. Слова отсортированы в лексикографическом (алфавитном) порядке. Все слова состоят из маленьких букв от 'a' до 'z'. Обратите внимание, что в тестах к этой задаче все заданные слова реально существуют в английском языке и случайным образом выбраны из словаря.

Гарантируется, что длина каждого слова из предложенного набора (словаря) в пределах от 5 до 8, строка, которую получила Маша может быть получена путем перестановки букв некоторых различных слов из предложенного словаря, причем набор выбранных Машей слов определяется по ней однозначно. Количество слов, из которых составлена Машина строка находится в пределах от 5 до 8.

Формат вывода
Вывести все слова, выбранные Машей, в алфавитном порядке по одному в строке.

Мой код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from itertools import combinations
from collections import Counter
 
def can_form_string(words, target):
    combined = ''.join(words)
    return Counter(combined) == Counter(target)
 
target_string = input().strip()
n = int(input().strip())
words = [input().strip() for _ in range(n)]
 
target_length = len(target_string)
 
result = []
for r in range(5, 9):
    for combo in combinations(words, r):
        if sum(len(word) for word in combo) == target_length:
            if can_form_string(combo, target_string):
                result = sorted(combo)
                break
    if result:
        break
 
for word in result:
    print(word)

@anton78spb · 22.10.2024, 20:25

Сообщение от Sasuna

Решил задачу но проходит 5/30 тестов из за лимита времени.

Под "решил задачу" теперь подразумевается скормил ее ChatGPT 4o-mini?

@Whabablca · 23.10.2024, 02:49

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import Counter, deque
 
s, n = input(), int(input())
word_data = [(w, Counter(w)) for w in (input() for _ in range(n))]
stack = deque([(0, Counter(s), [], 0)])
 
while stack:
    idx, remain, path, depth = stack.pop()
    
    if not remain and 5 <= depth <= 8:
        print(*sorted(path), sep='\n')
        break
    
    if depth > 8 or idx >= n:
        continue
    
    for i in range(n-1, idx-1, -1):
        word, cnt = word_data[i]
        if all(cnt[c] <= remain[c] for c in cnt):
            stack.append((i + 1, remain - cnt, path + [word], depth + 1))

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .