Форум » Обработка числовых последовательностей » 7182(27-184) ошибка в решении » Ответить
7182(27-184) ошибка в решении
oval: [quote]Выберите четыре элемента последовательности так, чтобы расстояние между первым и последним числами было не меньше K, а их сумма была максимально возможной. В ответе запишите найденную сумму.[/quote] при n = 8 и k = 7 на последовательности [50, 1, 1, 100, 20, 1, 40, 1] получается не верный ответ Программа дает ответ 201 (i = 7 data = 1 maxK = 50 max1 = 100 max2 = 50 max3 = 40), т.е число 50 учитывается дважды, и как maxK, и как max2. Правильной будет проверка: если maxK равно какому-то максимуму(1, 2 или 3), то в сумме надо учитывать два других максимума.
Ответов - 3
Ж: [pre2] f=open('D:/27-184b.txt') [n,k]=list(map(int,f.readline().strip().split())) s=sorted([(int(c),i) for i,c in enumerate(f.readlines())],reverse=True) maxi=0 for c in s: maxi=max(maxi,max(c[0] for c in s[3:] if abs(c[1]-min(c[1] for c in s[:3]))>=k)+sum(c[0] for c in s[:3])) ss=s[1:] if sum(c[0] for c in s[:3])<maxi: break print(maxi) [/pre2]
oval: Извините, но я вашу программу сломала Программа с сайта:[pre2] with open("27-184b.txt") as F: N, K = map(int, F.readline().split()) data = [int(x) for x in F] sMax = float('-inf') maxK = float('-inf') max1 = max2 = max3 = float('-inf') for i in range(N): if i >= K: maxK = max(data[i - K], maxK) s = maxK + data[ i] s += max1 + max2 if maxK != max1 else max2 + max3 sMax = max(s, sMax) if data > max1: max1, max2, max3 = data[ i], max1, max3 elif data[ i] > max2: max2, max3 = data[ i], max2 elif data[ i] > max3: max3 = data[ i] print(sMax) [/pre2] Моя версия:[pre2]F = open("27-184b.txt") N, K = map(int, F.readline().split()) sMax = -10 ** 8 maxK = -10 ** 8 max1 = max2 = max3 = -10 ** 8 queue = [] for i in range(K): x = int(F.readline()) queue.append(x) if x > max1: max1, max2, max3 = x, max1, max2 elif x > max2: max2, max3 = x, max2 elif x > max3: max3 = x for i in range(K, N): x = int(F.readline()) y = queue[i % K] queue[i % K] = x maxK = max(y, maxK) s = maxK + x if maxK == max1: s += max2 + max3 elif maxK == max2: s += max1 + max3 else: s += max1 + max2 sMax = max(s, sMax) if x > max1: max1, max2, max3 = x, max1, max2 elif x > max2: max2, max3 = x, max2 elif x > max3: max3 = x print(sMax) [/pre2] Все три программы и на файле А и на файле В выдают одинаковые ответы. Если взять входные данные такие:[pre]8 7 50 1 1 100 20 1 40 1 [/pre] моя и ваша программа дают ответ 191 (50+100+40+1), программа с сайта дает ответ 201(50+100+50+1) Об этом и был пост выше. А вот на файле:[pre]11 7 20 1 1 50 40 1 100 1 90 1 150 [/pre] программа с сайта и моя выдают ответ 390(150+50+100+90), а ваша программа упала с ошибкой "max() arg is an empty sequence" Если последнее число в файле - 150 заменить на что-то маленькое, например 13 ваша программа выдает ответ 253, видимо, 13+50+90+100. Но есть сумма больше 90+20+100+50 = 260, этот ответ дают и моя программа и программа с сайта. Волшебная строчкаmaxi=max(maxi,max(c[0] for c in s[3:] if abs(c[1]-min(c[1] for c in s[:3]))>=k)+sum(c[0] for c in s[:3])) для меня осталась почти загадкой Компактные решения, конечно, прикольно смотрятся, но я думаю, что решение должно быть сначало понятно, а потом компактно.
Ж: oval пишет: Извините, но я вашу программу сломала Спасибо, что сломали!) Насчет компактных решений согласна, но я уже так привыкла (когда пишу развернуто, внимание рассеивается на большой объем кода, а в длинном тоже не просто разбираться... Дело вкуса) [pre2] f = open('D:/27-184b.txt') [n, k] = list(map(int, f.readline().strip().split())) s = sorted([(int(c), i) for i, c in enumerate(f.readlines())], reverse=True) maxi = 0 while s: maxind = max(c[1] for c in s[:3]) m1 = [c[0] for c in s[3:] if abs(c[1] - maxind) >= k] if m1: maxi = max(maxi, sum(c[0] for c in s[:3]) + max(m1)) minind = min(c[1] for c in s[:3]) m1 = [c[0] for c in s[3:] if abs(c[1] - minind) >= k] if m1: maxi = max(maxi, sum(c[0] for c in s[:3]) + max(m1)) ss = s[1:] if sum(c[0] for c in s[:3]) < maxi: break print(maxi) [pre2/]
полная версия страницы