Форум » Обработка числовых последовательностей » 3148 » Ответить
3148
Shein_DM: (№ 3148) Дана последовательность, которая состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел как в первой, так и во второй группе должна быть чётной. Определите максимально возможную сумму всех чисел в третьей группе. Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10000. Пример входного файла: 3 1 2 3 8 12 4 6 9 7 Для указанных данных искомая сумма равна 20, она соответствует такому распределению чисел по группам: (1, 4, 9), (3, 8, 7), (2, 12, 6). В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B. Ссылка на задание: https://kpolyakov.spb.ru/school/ege/gen.php?action=viewTopic&topicId=3148 Сомневаюсь в правильности ответа 607 для текстового файла А. Решил программой и решил вручную - получилось 633... Помогите разобраться, пожалуйста.
Ответов - 5
Шеин: Немного грубо решение написал, но вот:[pre2] f = open('27.txt', 'r') n = f.readline() # считали количество строк k1=0 # к - слагаемые в данный момент k2=0 k3=0 s1=0 # s - суммы s2=0 s3=0 r1=100000 # разница нечетная r2=100000 r3=100000 for i in range(int(n)): a, b, c = map(int, f.readline().split()) k1 = min(a, b, c) k3 = max(a, b, c) k2 = a + b + c - k3 - k1 s1 = s1 + k1 # наименьшая сумма s2 = s2 + k2 # средняя s3 = s3 + k3 # наибольшая if k3-k1<r2 and k3-k1==r1: r2=k3-k1 if k3-k2<r1 and k3-k2==r2: r1=k3-k2 if k3-k2<r2 and (k3-k2) % 2 != 0: r2=k3-k2 if k3-k1<r1 and (k3-k1) % 2 != 0: r1=k3-k1 if k2-k1<r3 and (k2-k1)%2!=0: r3=k2-k1 if s1%2!=0 and s2%2!=0: s1=s1+r3 s2=s2-r3 if s1%2!=0: s1=s1+r1 s3=s3-r1 if s2%2!=0: s2=s2+r2 s3=s3-r2 print(s3)[/pre2] Заполняю первые 2 группы наименьшими слагаемыми, при этом запоминаю для первой и второй группы наименьшие отдельные разности(чтобы можно было заменить сумму на чётную в случае её нечетности). Если нечётные 1 и 2 группы - меняю у них 2 элемента, чтобы нарушить чётность каждой. То есть в этом случае сумма третьей группы даже не меняется. Если нечётная только одна из групп - меняю элемент у этой группы с третьей. (На ту самую минимальную разность, что ищу ранее)
Т: Шеин, у вас не учтен вариант, что на одной и той же паре будет 2 разности, которые запишутся в минимальные разности,
Поляков: Shein_DM пишет: Решил программой и решил вручную - получилось 633... Попробуйте разбить числа на 3 группы так, чтобы у вас получилась такая сумма. Данные специально подобраны так, чтобы "лобовое" решение приводило к неверному ответу.Помогите разобраться, пожалуйста. Это задача 42 отсюда. А вот здесь можно посмотреть ее решение.
epp: Shein_DM пишет: Сомневаюсь в правильности ответа 607 для текстового файла А. Решил программой и решил вручную - получилось 633... У меня аналогично. На примере из условия у меня вручную получается другой ответ: Пример входного файла: 3 1 2 3 8 12 4 6 9 7 Формирую группы (2,4,6), (1,8,7), (3,12,9). Им соответствуют суммы 12, 16, 24, все четные, максимальная из них - 24. Я не понимаю, почему эта сумма не является ответом, хотя подходит под все условия.
Поляков: Коллеги, вы правы. Я не учел один вариант, который как раз тут и случился. Задачи 42-45 переделаны, изменены файлы с данными и ответы. Спасибо!
полная версия страницы