Python-сообщество

Dragonfly · Янв. 6, 2018 11:24:30

Здравствуйте. Прошу навести на мысль, как можно избавится от ошибки “Time Limit Exceeded” в, казалось бы простой задаче про клавиатуру:
Условие:
Всем известно, что со временем клавиатура изнашивается, и клавиши на ней начинают залипать. Конечно, некоторое время такую клавиатуру еще можно использовать, но для нажатий клавиш приходиться использовать большую силу.
При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий, которое она должна выдерживать. Если знать эти величины для используемой клавиатуры, то для определенной последовательности нажатых клавиш можно определить, какие клавиши в процессе их использования сломаются, а какие — нет.
Требуется написать программу, определяющую, какие клавиши сломаются в процессе заданного варианта эксплуатации клавиатуры.
Формат ввода
Первая строка входных данных содержит целое число n (1≤n≤1000) — количество клавиш на клавиатуре. Вторая строка содержит n целых чисел —с₁, с₂, … , сn, где сᵢ (1≤cᵢ≤100000) — количество нажатий,выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1≤k≤100000) — общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1≤pj≤n) — последовательность нажатых клавиш.
Формат вывода
Программа должна вывести n строк, содержащих информацию об исправности клавиш. Если i-я клавиша сломалась, то i-ая строка должна содержать слово YES, если же клавиша работоспособна — слово NO.

Мое решение:

 button = int(input())
sb = 1 # первая клавиша
norm_press_button = list(map(int, input().split()))
number_press = int(input())
spb = list(map(int, input().split()))  # sequence_press_button
for now in range(len(spb)):
    while sb <= button:
        p = spb.count(sb)
        if p <= norm_press_button[sb - 1]:
            print('NO')
        else:
            print('YES')
        sb += 1

Отредактировано FishHook (Янв. 6, 2018 12:29:38)

FishHook · Янв. 6, 2018 12:43:19

Dragonfly
как можно избавится от ошибки “Time Limit Exceeded”

Это не ошибка, это контрольная программа вам говорит, что ваш алгоритм неэффективен, что его можно реализовать с меньшей сложностью. Искусство писать эффективные программы и есть искуство программирования, и смысл вашего обучения как раз в этом. Думайте как ускорить программу, какие структуры данных использовать. Вот шпаргалка. Может быть есть структуры со сложностью доступа меньше чем у списка? Может быть spb.count(sb) в двойном цикле делать не стоит? Давай включим голову и подумаем, что делает spb.count(sb)? Может быть не стоит каждый раз проходить весь большой список, а сделать это можно один раз?
Может быть информацию о сломанных клавишах нужно кешировать, чтобы не гонять лишний раз циклы?

marvellik · Янв. 6, 2018 16:31:53

 button = int(input())
norm_press_button = list(map(int, input().split()))
number_press = int(input())
spb = list(map(int, input().split()))
dict_clic = {}
for i in range(number_press):
    dict_clic[spb[i]] = dict_clic.get(spb[i],0)+1
for i in range(button):
    print(('NO','YES')[dict_clic[i+1] > norm_press_button[i]])

FishHook · Янв. 6, 2018 17:03:38

marvellik
Тебя просили давать решение?

Здравствуйте. Прошу навести на мысль

Навел, да? Ну нафига ты лезешь, когда даже не просят? Патологическое желание похвастаться интеллектом?

Dragonfly · Янв. 7, 2018 20:10:22

Спасибо) Пришлось “покопаться” в теории - и все получилось! Признаюсь, со словарями еще не была знакома

Doccregland · Апрель 8, 2019 18:11:46

 def keyCount(n, actualClicks, maxClicks):
    clickCount = [0] * n
    for click in actualClicks:
        clickCount[click - 1] += 1
    for i in range(n):
        if maxClicks[i] < clickCount[i]:
            print('YES')
        else:
            print('NO')
n = int(input())
maxClicks = [int(i) for i in input().split()]
k = int(input())
actualClicks = [int(i) for i in input().split()]
keyCount(n, actualClicks, maxClicks)

держите, без словарей и прочего. Если вы проходите python на курсере, со словарями вы к тому моменту еще не знакомы

Python-сообщество

Уведомления

#1 Янв. 6, 2018 11:24:30

Не получается "вложится" по времени в коде

#2 Янв. 6, 2018 12:43:19

Не получается "вложится" по времени в коде

#3 Янв. 6, 2018 16:31:53

Не получается "вложится" по времени в коде

#4 Янв. 6, 2018 17:03:38

Не получается "вложится" по времени в коде

#5 Янв. 7, 2018 20:10:22

Не получается "вложится" по времени в коде

#6 Апрель 8, 2019 18:11:46

Не получается "вложится" по времени в коде

Board footer