Форум » Обработка числовых последовательностей » Задание 27 (задача 70) » Ответить
Задание 27 (задача 70)
dim18: Здравствуйте! Подскажите, пож., в чем ошибка алгоритма? С файлом А получается правильный ответ, с файлом B - 1365905, в таблице - 1365890. При этом, условие задачи выполняется: полученная разница делится на 5 и является максимальной. [pre2] a = open('27-70a.txt') n = int(a.readline()) c = [] for i in range(n): c.append(list(map(int, a.readline().split()))) d_max = [max(i) for i in c] d_min = [min(i) for i in c] s_max = sum(d_max) s_min = sum(d_min) diff = [max(i) - min(i) for i in c] diff.sort() # нахождение в diff мин. разницы чисел (i) с остатком от деления на 5, # равным остатку от деления на 5 разницы сумм макс. и мин. чисел for i in diff: if i % 5 == (s_max - s_min) % 5: print(s_max - s_min - i) break # 115 1365890 (1365905) [/pre2]
Ответов - 5
Danov: В этой задаче необходимо применять "метод частичных сумм". Через минимальную разность не получится найти ответ.
dim18: Доброе утро. Предложенный алгоритм дает правильные ответы по задачам такого типа. Конкретно в этой задаче я не учел, что минимальную разницу пары надо вычитать дважды. [pre2] a = open('27-70a.txt') n = int(a.readline()) c = [] for i in range(n): c.append(list(map(int, a.readline().split()))) # c = [[13,18], [18,10],[15,8],[19,11],[7,15]] d_max = [max(i) for i in c] d_min = [min(i) for i in c] s_max = sum(d_max) s_min = sum(d_min) diff = [max(i) - min(i) for i in c] diff.sort() for i in diff: if (s_max - s_min - 2 * i) % 5 == 0: print(s_max - s_min - 2 * i) break # 115 1365890 [/pre2]
Danov: Проблема в том, что метод разностей учитывает только одну минимальную разность с нужным остатком, но еще меньшая разность может быть сформирована из нескольких разностей с другими остатками. Вам повезло, что используемый метод дал правильный ответ. Это моя недоработка! Надо будет сгенерировать новый набор данных. Кстати, первый раз вижу решение на основе метода минимальных разностей для этой задачи. Креативно!
dim18: Вы правы. В этом случае я делаю перебор разных вариантов с предварительным определением остатка в задачах, где сумма должна быть кратна заданному параметру. Если не должна быть кратна, еще проще. [pre2] ... s = sum([max(i) for i in c]) print(s%5) # = 3 ost_1 = [i for i in d if i % 5 == 1] ost_2 = [i for i in d if i % 5 == 2] ost_3 = [i for i in d if i % 5 == 3] print(max(s - ost_3[0], s - ost_2[0] - ost_1[0], s - ost_1[0] - ost_1[1] - ost_1[2])) a.close() [/pre2]
Danov: > В этом случае я использую перебор разных вариантов с предварительным определением остатка в задачах... Много случаев нужно рассматривать. Сложно вручную все перебрать. Можно из двух, трех, четырех и даже пяти собрать нужную разность. И разными способами. И это кроме очевидной одной разности
полная версия страницы