Отправлено: 29.06.22 12:19. Заголовок: №3987 (27.64) ошибка в решении

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

В решении предложенном Н. Гаязовой есть ошибка.

Берем файл:

 
 4 
 3 3 
 1 1 
 3 2 
 71 80 
 

Алгоритм выдает ответ 13, что неверно. Правильный ответ 157.

Сортируем каждую строку:

 
 3 3 
 1 1 
 2 3 
 71 80 
 

Меньшая сумма s1 = 3 + 1 + 2 + 71 = 77, большая сумма s2 = 3 + 1 + 3 + 80 = 87. Биты сумм (1, 1) соответственно. Нам нужно получить (0, 1). Это можно сделать как с помощью (1, 1) - (1, 0) = (0, 1), так и с помощью (1, 1) - (1, 1) - (0 , 1) = (0, 0) - (0, 1) = (0, 1).

Строки соответствующие битам:

(1, 0): (71, 80)

(1, 1) : (1, 1), (3, 3)
(0, 1): (2, 3)

В первом случае: (77 - 71, 87 - 80) = (6, 7) = 6 + 7 = 13
Во втором случае: (77 - 1 - 2, 87 - 1 - 3) = (74, 83) = 74 + 83 = 157

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

 Отправлено: 29.06.22 15:15. Заголовок: В задаче №3988 (27.6..

В задаче №3988 (27.65) та же проблема. Даже если алгоритм просто запустить на предложенных в задаче файлах, алгоритм что на a файле, что на b файле выдаст неправильный ответ.

 Отправлено: 13.08.22 18:46. Заголовок: ап..

ап

 Отправлено: 18.08.22 12:53. Заголовок: Спасибо. По согласов..

Спасибо. По согласованию с автором ее решение удалено.

 Отправлено: 19.08.22 15:44. Заголовок: Поляков, тогда могу ..

Поляков, тогда могу предложить свой вариант, который учитывает этот недостаток:

 
 n = -1 
 res = [[] for i in range(3)] 
 s1 = 0 
 s2 = 0 
 s3 = 0 
  
 with open("27-64b.txt", "r") as f: 
 	 
 	n = int(f.readline()) 
 	 
 	for i, x in enumerate(f): 
  
 		arr = list(map(int, x.split())) 
 		 
 		if arr[0] % 2 != 1: continue 
 		 
 		arr.sort() 
 		 
 		a, b = arr 
 		c = a + b 
 		 
 		bit1 = a % 2 
 		bit2 = b % 2 
  
 		s1 += a 
 		s2 += b 
 		s3 += c 
 		 
 		index = bit1 + (bit2 << 1) - 1 
 		res[index].append(c) 
  
 for arr in res: 
 	arr.sort() 
 	 
 bit1 = s1 % 2 
 bit2 = s2 % 2 
 flag = (bit1 << 1) + bit2 
  
 if flag == 1: 
 	print(s3) 
  
 else: 
 	 
 	if flag: res[0], res[1] = res[1], res[0] 
 	if flag != 2: res[1], res[2] = res[2], res[1] 
 	 
 	delta = [] 
 	if res[2]: delta.append(res[2][0]) 
 	if res[0] and res[1]: delta.append(res[0][0] + res[1][0]) 
 	 
 	if delta: 
 		print(s3 - min(delta)) 
 	else: 
 		print("oops!", flag) 
 

 Отправлено: 20.08.22 16:10. Заголовок: Спасибо, добавил ваш..

Спасибо, добавил ваше решение.