Автор | Сообщение |
|
Отправлено: 11.05.22 17:20. Заголовок: Задание 27 (задача 70)
Здравствуйте! Подскажите, пож., в чем ошибка алгоритма? С файлом А получается правильный ответ, с файлом B - 1365905, в таблице - 1365890. При этом, условие задачи выполняется: полученная разница делится на 5 и является максимальной. 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)
|
|
|
Ответов - 5
[только новые]
|
|
|
Отправлено: 13.05.22 09:28. Заголовок: В этой задаче необхо..
В этой задаче необходимо применять "метод частичных сумм". Через минимальную разность не получится найти ответ.
|
|
|
|
Отправлено: 13.05.22 09:37. Заголовок: Доброе утро. Предлож..
Доброе утро. Предложенный алгоритм дает правильные ответы по задачам такого типа. Конкретно в этой задаче я не учел, что минимальную разницу пары надо вычитать дважды. 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
|
|
|
|
Отправлено: 13.05.22 10:41. Заголовок: Проблема в том, что ..
Проблема в том, что метод разностей учитывает только одну минимальную разность с нужным остатком, но еще меньшая разность может быть сформирована из нескольких разностей с другими остатками. Вам повезло, что используемый метод дал правильный ответ. Это моя недоработка! Надо будет сгенерировать новый набор данных. Кстати, первый раз вижу решение на основе метода минимальных разностей для этой задачи. Креативно!
|
|
|
|
Отправлено: 13.05.22 10:49. Заголовок: Вы правы. В этом слу..
Вы правы. В этом случае я делаю перебор разных вариантов с предварительным определением остатка в задачах, где сумма должна быть кратна заданному параметру. Если не должна быть кратна, еще проще. ... 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()
|
|
|
|
Отправлено: 13.05.22 11:20. Заголовок: > В этом случае..
> В этом случае я использую перебор разных вариантов с предварительным определением остатка в задачах... Много случаев нужно рассматривать. Сложно вручную все перебрать. Можно из двух, трех, четырех и даже пяти собрать нужную разность. И разными способами. И это кроме очевидной одной разности
|
|
|
|