Форум » Обработка числовых последовательностей » №3987 (27.64) ошибка в решении » Ответить

№3987 (27.64) ошибка в решении

beep: Здравствуйте! В решении предложенном Н. Гаязовой есть ошибка. Берем файл: [pre] 4 3 3 1 1 3 2 71 80 [/pre] Алгоритм выдает ответ 13, что неверно. Правильный ответ 157. Сортируем каждую строку: [pre] 3 3 1 1 2 3 71 80 [/pre] Меньшая сумма 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 способов преобразования сумм.

Ответов - 5

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

beep: ап

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


beep: Поляков, тогда могу предложить свой вариант, который учитывает этот недостаток: [pre2] 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) [/pre2]

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



полная версия страницы