Форум » Обработка числовых последовательностей » Задача № 5278 » Ответить
Задача № 5278
ЖаннаШ: Еще раз добрый день! с заданием А разобралась. Ответ получаю верный. Задание В за обозримое время не выполняет... [pre2] f = open('c:/1.txt') n = int(f.readline()) s = [int(c) for c in f.readlines()] f.close() def ff(n): global s k = 0 for c in s: if c <= n: k = c else: break return k w = [(0, 0), (0, 0), (0, 0)] while s: h1 = [[c[0] + 15, s[0]] for c in w] h1 += [[c[0], c[1], s] for c in w if s[0] <= c[1]] h1 += [[c[0] + 40, ff(s[0] + 10)] for c in w] h1 += [[c[0] + 70, ff(s[0] + 20)] for c in w] w = h1 aa = [] for kol in range(max([c[1] for c in w]) + 1): ww = [c for c in w if c[1] == kol] if ww: aa.append(min(ww)) w = aa # print(len(s)) s = s[1::] if len(s) % 1000 == 0: print(len(s)) print(min(w)) [/pre2]
Ответов - 2
Максим Фирсов: В вашем коде есть 2 конструкции, которые не позволяют дождаться ответа для файла b. [pre2] def ff(n): global s; k = 0 for c in s: if c <= n: k = c else: break return k [/pre2] количество выполнений для каждого вызова растет до n, а этих вызовов у вас 2 [pre2]for kol in range(max([c[1] for c in w]) + 1): ww = [c for c in w if c[1] == kol] if ww: aa.append(min(ww)) [/pre2] тут количество выполнений в среднем для файла a 15 000 и для файла b 150 000 Сложность вашего алгоритма чуть выше чем O(n^2). Вам не нужно считывать сразу в массив весь файл, постарайтесь использовать память разумно. В условии есть подсказка, что вам нужно прибавлять значение только тогда, когда закончился пропуск (без этого замечания ответ будет таким же). Используйте метод префиксных сумм. Сложность алгоритма станет линейной. Мне кажется, что лучше переписать большую часть кода. Не злоупотребляйте генераторами там, где это не нужно, например тут [pre2] max([c[1] for c in w]) [/pre2] Также давайте соответствующие имена переменным или пишете комментарии, если отправляете на форум 27 задание. Желаю успехов!
ЖаннаШ: Спасибо большое!
полная версия страницы