Отправлено: 22.12.20 11:20. Заголовок: 3148

(№ 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...
Помогите разобраться, пожалуйста.

 Отправлено: 22.12.20 12:34. Заголовок: Немного грубо решени..

Немного грубо решение написал, но вот:

 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)

Заполняю первые 2 группы наименьшими слагаемыми, при этом запоминаю для первой и второй группы наименьшие отдельные разности(чтобы можно было заменить сумму на чётную в случае её нечетности).
Если нечётные 1 и 2 группы - меняю у них 2 элемента, чтобы нарушить чётность каждой. То есть в этом случае сумма третьей группы даже не меняется.

Если нечётная только одна из групп - меняю элемент у этой группы с третьей. (На ту самую минимальную разность, что ищу ранее)

 Отправлено: 10.04.21 12:47. Заголовок: Шеин, у вас не учтен..

Шеин, у вас не учтен вариант, что на одной и той же паре будет 2 разности, которые запишутся в минимальные разности,

 Отправлено: 22.12.20 12:59. Заголовок: Shein_DM пишет: Реши..

Shein_DM пишет:

цитата:

Решил программой и решил вручную - получилось 633...

Попробуйте разбить числа на 3 группы так, чтобы у вас получилась такая сумма. Данные специально подобраны так, чтобы "лобовое" решение приводило к неверному ответу.

цитата:

Помогите разобраться, пожалуйста.

Это задача 42 отсюда. А вот здесь можно посмотреть ее решение.

 Отправлено: 22.12.20 13:33. Заголовок: Shein_DM пишет: Сом..

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. Я не понимаю, почему эта сумма не является ответом, хотя подходит под все условия.

 Отправлено: 22.12.20 15:31. Заголовок: Коллеги, вы правы. Я..

Коллеги, вы правы. Я не учел один вариант, который как раз тут и случился.
Задачи 42-45 переделаны, изменены файлы с данными и ответы.
Спасибо!