Отправлено: 19.06.22 13:32. Заголовок: №3148 (27.42) вопрос по логике

Здравствуйте!

В каждой строчке дано 3 числа, каждое из них нужно положить в одно из подмножеств и в итоге должно получиться 2 подмножества, где сумма всех членов четная, и одно подмножество любой четности, где сумма максимальна (искомый результат).

В решении предложен алгоритм, который ищет минимальные расстояния от максимального числа отдельно для условно левой и правой колонки (первого и второго подмножества). А после прохождения всего файла встает важный вопрос, какие из подмножеств нужно корректировать, если ни одного, то все хорошо, если одно, то тоже не сложно найти какое число вычесть. Если оба подмножества нужно корректировать, то есть 2 варианта: удачный - это когда хотя бы в одной строке члены этих подмножеств имеют разную четность, тогда их просто можно поменять местами и снова все хорошо. Плохой же подразумевает, что на каждой строке члены корректируемых подмножеств всегда одной четности и тогда нужно найти такие строки, где член максимального подмножества имеет противоположную четность с корректируемыми подмножествами. И вот тут появляется мой вопрос и вся сложность задачи: главная проблема в том, что минимальное значение для корректировки может быть одновременно на одной строке для обоих корректируемых подмножеств. Этим и объясняется такая запутанная логика в решении.

Но ведь можно пойти намного проще. Нам всего лишь нужно найти первые 2 минимальных корректируемых значения и все. Если нужно скорректировать только 1 подмножество, то берем последний минимум, если оба - то последний + предпоследний. И все. Нам же никто не мешает менять местами члены каждой из корректируемых групп. Зачем искать отдельно для каждой группы по 2 минимума? Мы ведь всегда b можем поменять местами с a? И зачем вообще для минимального числа отслеживать минимум?

Например:

2 4 5
3 5 6

Нам ведь никто не мешает сделать так:

2 4 5
5 3 6

В чем смысл искать минимумы для самого маленького числа в строке, а потом через сложную логику искать правильную комбинацию, если самое маленькое число всегда можно поменять местами со средним и ничего не изменится с точки зрения четности?

Тогда мы просто на каждой строке сортируем числа, максимум прибавляем к результату, и сравниваем разницу между средним и максимальным числом в поисках двух минимумов, а потом уже либо ничего не вычитаем, либо первый минимум, либо оба и все?

Где я ошибаюсь? Как мы не старались бы, у нас всегда минимумы для левого столбца (множества) будут больше, чем для правого, только если нет строки где a1 == b1 и при этом еще должна найтись такая другая строка, где b1 == b2 и c1 == c2.

 Отправлено: 24.06.22 13:32. Заголовок: Здравствуйте! Честно..

Здравствуйте! Честно сказать, мне не совсем понятна ваша идея и объяснение. Приведите, пожалуйста, ваше решение в виде программы.

 Отправлено: 27.06.22 14:17. Заголовок: Проблемы с предложен..

Проблемы с предложенным решением в ответах:

1) Для случая когда обе суммы нечетные, есть 2 варианта, первый - когда есть хотя бы одна строка, где четность у a и b отличаются, тогда ничего делать ненужно, ведь a и b можно поменять местами для s1 и s2 и тогда обе суммы станут четными, и второй случай - когда ни одной такой строки нет. За проверку на наличие этой строки в решении отвечает переменная diff0. Если diff0 == False, то вступает в работу следующая секция:

 
 if s1 % 2 == 0  and  s2 % 2 == 0: 
   print( s3 ) 
 elif s1 % 2 != 0 and s2 % 2 != 0: 
   if diff0: 
     print( s3 ) 
   else: 
     d = min( diff1[0][0] + diff2[1][0], 
              diff1[1][0] + diff2[0][0], 
              diff1[0][0] + diff1[1][0], 
              diff2[0][0] + diff2[1][0] ) 
     if diff1[0][1] != diff2[0][1]: 
       d = min( d,  diff1[0][0] + diff2[0][0] ) 
     print( s3 - d ) 
 

Здесь слишком избыточная логика, ведь если во всех строках a и b имеют одну и ту же четность, то в diff1 и diff2 будут заноситься одни и те же значения:

 
   if (c - a) % 2 == 1: 
     delta = c - a 
     if (c - b) % 2 == 1: 
       delta = c - b 
     if delta < diff1[0][0]: 
       diff1 = [ (delta, i), diff1[0] ] 
     elif delta < diff1[1][0]: 
       diff1[1] = (delta, i) 
   if (c - b) % 2 == 1: 
     delta = c - b 
     if delta < diff2[0][0]: 
       diff2 = [ (delta, i), diff2[0] ] 
     elif c - b < diff2[1][0]: 
       diff2[1] = (delta, i) 
 

Это значит, что diff1 всегда будет такой же, как diff2 и все, что нужно сделать, это просто вычесть оба элемента из любого из них.

2) Когда у нас нечетна только s1, то это может быть только в случае, если строк, где четность a и b отличается, нечетное количество. В любых других случаях у нас четность s1 и s2 будет совпадать. Тогда мы в любом случае попадаем в следующую секцию:

 
 elif s1 % 2 != 0: 
   diff = diff1[0][0] 
   if diff0: 
     if len(diff0) > 1 or diff2[0][1] != diff0[0]: 
       diff = min( diff, diff2[0][0] ) 
     elif diff2[1][1] != diff0[0]: 
       diff = min( diff, diff2[1][0] ) 
   print( s3 - diff ) 
 

Но поскольку diff0 это логическое значение, то алгоритм тут выдаст ошибку при попытке померить длину логического значения (а еще есть попытка обратиться к первому члену логического значения). Т.е. здесь уже алгоритм не работает. Далее я попытаюсь догадаться, что автор имел в виду.

Давайте разберемся, какие значения могут попасть в diff1 и diff2. Если у a и b одинаковая четность, то если у c четность такая же, алгоритм пропускает такую строку, а если другая, то в diff1 и diff2 попадает одно и то же значение (c - b, i) (если оно меньше тех, что уже есть в diff1/2). Если у a и b, четности разные, то в diff1 попадает c - a, если у c и a четности разные, а в diff2 попадает c - b, если у c и b четности разные.

Теперь давайте разберемся, какие случаи могут быть, если у a и b четности разные:

 
 a b c 
 1 0 0 
 0 1 1 
 1 0 1 
 0 1 0 
 

В итоге если c нечетное, то добавляется нечетное число в сумму и убирается четное (условно +1), а если c четное, то убирается нечетное число и добавляется четное (условно -1).

Поскольку у нас в diff1 хранится в первом элементе минимальная возможная разница для изменения четности s1, то сравнивать нужно 2 варианта: первый, изменение четности s1 с помощью diff1[0], и второй - изменение четности s2:
* с помощью diff2[0], при условии, что строк где четности a и b не совпадают больше одной,
* с помощью diff2[0], когда строка, где четности a и b не совпадают, одна и номер этой строки не совпадает с diff2[0][1],
* с помощью diff2[1], когда строка, где четности a и b не совпадают, одна и номер этой строки не совпадает с diff2[2][1].

Получается, что в diff0 должны храниться все i строк, у которых четности a и b не совпадают. Поскольку чтобы только одна сумма была нечетной, требуется нечетное количество строк, где четность у a и b не совпадают, то проверка на пустоту diff0 бессмысленна.

3) С суммой s2 все то же самое, что и с суммой s1 нужно делать. В diff2[0] лежит минимальный способ изменить четность s2. Это можно сделать либо помощью строки где a % 2 == b % 2 and b % 2 != c % 2, либо где a % 2 != b % 2 and b % 2 != c % 2. При этом не учитывается вариант, где s1 можно изменить с помощью diff1[0], в котором лежит c - a при a % 2 != b % 2 and a % 2 != c % 2, такое что diff1[0][0] < diff2[0][0] and len(diff0) > 1. Поэтому и файл со следующими данными

 
 3  
 2 5 10  
 4 7 15  
 2 3 5 
 

алгоритм обрабатывает неверно и дает неправильный результат (25, а на самом деле 27).

 Отправлено: 27.06.22 14:44. Заголовок: Если исправлять алго..

Если исправлять алгоритм в решении, то он должен выглядеть как-то так

 
 Fin = open("27-42a.txt") 
  
 N = int(Fin.readline()) 
 s1 = s2 = s3 = 0 
 diff0 = [] 
 diff1 = [ (1e10, -1), (1e10, -1) ] 
 diff2 = [ (1e10, -1), (1e10, -1) ] 
 for i in range(N): 
   a, b, c = map( int, Fin.readline().split() ) 
   a, b, c = sorted( [a, b, c] ) 
   s1 += a 
   s2 += b 
   s3 += c 
   if (b - a) % 2 == 1: 
     diff0.append(i) 
   if (c - a) % 2 == 1: 
     delta = c - a 
     if (c - b) % 2 == 1: 
       delta = c - b 
     if delta < diff1[0][0]: 
       diff1 = [ (delta, i), diff1[0] ] 
     elif delta < diff1[1][0]: 
       diff1[1] = (delta, i) 
   if (c - b) % 2 == 1: 
     delta = c - b 
     if delta < diff2[0][0]: 
       diff2 = [ (delta, i), diff2[0] ] 
     elif c - b < diff2[1][0]: 
       diff2[1] = (delta, i) 
   #print( s1, s2, s3, diff1, diff2 ) 
  
 Fin.close() 
  
 print( 's1 =', s1, 's2 =', s2 ) 
 print( 's3 =', s3 ) 
 print( 'b <-> a:', diff0 ) 
 print( 'c <-> a:', diff1 ) 
 print( 'c <-> b:', diff2 ) 
  
 print("Ответ:") 
 if s1 % 2 == 0  and  s2 % 2 == 0: 
   print( s3 ) 
 elif s1 % 2 != 0 and s2 % 2 != 0: 
   if diff0: 
     print( s3 ) 
   else: 
     print( s3 - diff1[0][0] - diff1[1][0]) 
 elif s1 % 2 != 0: 
   diff = diff1[0][0] 
   if diff0: 
     if len(diff0) > 1 or diff2[0][1] != diff0[0]: 
       diff = min( diff, diff2[0][0] ) 
     elif diff2[1][1] != diff0[0]: 
       diff = min( diff, diff2[1][0] ) 
   print( s3 - diff ) 
 elif s2 % 2 != 0: 
   d = diff2[0][0] 
   if len(diff0) > 1: d = min(d, diff1[0][0]) 
   print( s3 - d ) 
 

 Отправлено: 27.06.22 15:04. Заголовок: И вот мой итоговый в..

И вот мой итоговый вариант, который выглядит проще, как мне кажется:

 
 Fin = open("27-42a.txt") 
  
 N = int(Fin.readline()) 
 s1 = s2 = s3 = 0 
 swap = [[], []] 
 diff = [ 1e10, 1e10 ] 
 flag = 0 
  
 for i in range(N): 
   a, b, c = map( int, Fin.readline().split() ) 
   a, b, c = sorted( [a, b, c] ) 
   s1 += a 
   s2 += b 
   s3 += c 
   if b % 2 != a % 2: 
     swap[c % 2].append(c - (a if a % 2 != c % 2 else b)) 
   elif b % 2 != c % 2: 
     flag += b 
     delta = c - b 
     if delta < diff[0]: 
       diff = [ delta, diff[0] ] 
     elif c - b < diff[1]: 
       diff[1] = delta 
  
 Fin.close() 
  
 for a in swap: 
   a.sort() 
  
 if s1 % 2 == 0  and  s2 % 2 == 0: 
   print( s3 ) 
 elif s1 % 2 != 0 and s2 % 2 != 0: 
   if swap[0] or swap[1]: 
     print( s3 ) 
   else: 
     print(s3 - sum(diff)) 
 else: 
     delta = [diff[0]] 
     if flag % 2: swap[0], swap[1] = swap[1], swap[0] 
     if swap[0]: delta.append(swap[0][0]) 
     if swap[1] and (swap[0] or len(swap[1]) > 1): delta.append(swap[1][0]) 
     print(s3 - min(delta)) 
 

 Отправлено: 29.06.22 13:56. Заголовок: Спасибо. Действитель..

Спасибо. Действительно, решение получилось проще. С удовольствием добавлю его. Как сослаться на авторство?

 Отправлено: 29.06.22 15:20. Заголовок: Поляков, спасибо! Та..

Поляков, спасибо! Так и можно "beep". У меня и для других задач бывают решения, которые и проще (понятнее, ну для меня, естественно) выглядят и/или существенно быстрее работают. Есть смысл их выкладывать, чтобы Вы добавляли их к ответам?

 Отправлено: 29.06.22 15:40. Заголовок: beep пишет: Есть смы..

beep пишет:

цитата:

Есть смысл их выкладывать, чтобы Вы добавляли их к ответам?

Если они принципиально лучше, чем те, что выложены на сайте, то, конечно, выкладывайте. Или лучше присылайте на почту (не всегда успеваю просматривать форум).

 Отправлено: 14.12.22 12:39. Заголовок: У меня получилось со..

У меня получилось совсем просто
Гарантируется ли, что рабиение на три суммы существует?
Не смогла придумать пример, где ответ моей программы отличается от ответа программ, представленных на сайте. Интересуют случаи когда одна из сумм нечетная.

 
 Fin = open("27.txt") 
  
 N = int(Fin.readline()) 
 s1 = s2 = s3 = 0 
 count_ab = 0 
 delta_bc1 = delta_bc2 = delta_ac = 10 ** 10 
  
 for i in range(N): 
     a, b, c = map(int, Fin.readline().split()) 
     a, b, c = sorted([a, b, c]) 
     s1 += a 
     s2 += b 
     s3 += c 
     count_ab += (b - a) % 2 
     if (c - a) % 2 == 1 and (c - b) % 2 == 0: 
         delta_ac = min(c - a, delta_ac) 
  
     if (c - b) % 2 == 1: 
         if c - b < delta_bc1: 
             delta_bc2 = delta_bc1 
             delta_bc1 = c - b 
         else: 
             delta_bc2 = min(delta_bc2, c - b) 
 print(s1, s2, s3, count_ab, delta_ac, delta_bc1, delta_bc2) 
  
 if s1 % 2 == 0 and s2 % 2 == 0: 
     print(s3) 
 elif s1 % 2 != 0 and s2 % 2 != 0: 
     if count_ab == 0: 
         s3 -= (delta_bc2 + delta_bc1) 
     print(s3) 
 else: 
     s3 -= min(delta_bc1, delta_ac) 
     print(s3) 
 

 Отправлено: 08.07.23 17:32. Заголовок: f=open('d:/1/27..

 
 f=open('d:/1/27-42b.txt') 
 n=int(f.readline()) 
 s=[sorted(list(map(int,c.split()))) for c in f.readlines()] 
 maxi=sum(c[2] for c in s) 
  
 raz=[c for c in s if (c[1]-c[0])%2==1] 
 t1=sorted([(abs(c[2]-c[0]),i) for i,c in enumerate(s) if (c[2]+c[0])%2==1]) 
 t2=sorted([(abs(c[2]-c[1]),i) for i,c in enumerate(s) if (c[2]+c[1])%2==1]) 
 t3=sorted(t1[:2]+t2[:2]) 
  
 if (sum(c[0] for c in s)%2==0 and  sum(c[1] for c in s)%2==0) or raz: print(maxi) 
 elif t3[0][1]!=t3[1][1]: print(maxi-t3[0][0]-t3[1][0]) 
 else : print(maxi-t3[0][0]-t3[2][0]) 
 

То же самое с комментариями

 
 f=open('d:/1/27-42b.txt') 
 n=int(f.readline()) 
 s=[sorted(list(map(int,c.split()))) for c in f.readlines()] 
 maxi=sum(c[2] for c in s) 
  
 raz=[c for c in s if (c[1]-c[0])%2==1]  #проверяем наличие чисел разнгой четности среди двух минимальрных в тройке 
 t1=sorted([(abs(c[2]-c[0]),i) for i,c in enumerate(s) if (c[2]+c[0])%2==1])  # ищем минимальную нечетную разницу между наибольшим и наименьшим в тройке 
 t2=sorted([(abs(c[2]-c[1]),i) for i,c in enumerate(s) if (c[2]+c[1])%2==1])  # ищем минимальную нечетную разницу между наибольшим и средним в тройке 
 t3=sorted(t1[:2]+t2[:2]) # выбираем  4 тройки - кандидаты на замену 
  
 if sum(c[0] for c in s)%2==0 and  sum(c[1] for c in s)%2==0: print('ответ - сумма максимальных элементов троек чисел',maxi) 
 elif raz: print('есть тройка, в которой пара меньших чисел разной четности, если их поменять друг с другом, то сумм станут четными ',maxi) 
 elif t3[0][1]!=t3[1][1]: print(maxi-t3[0][0]-t3[1][0]) # замена происходит в разных тройках 
 else : print(maxi-t3[0][0]-t3[2][0]) # в одной тройке нельзя сделать две замены, поэтому вторую тройку пропускаем