Форум » Обработка числовых последовательностей » Задание 27. (Апробация 27 апреля 2021) » Ответить
Задание 27. (Апробация 27 апреля 2021)
daimon2006: Задание: Решение: [pre2] f = open('27_B.txt') n=int(f.readline()) c=[] d=[] g=[] k=103 for i in range(n): x1,x2,x3 =sorted((map(int,f.readline().split())))[::-1] c.append(x1) a=(x1-x2) b=(x1-x3) if a%k!=0 and b%k!=0: d.append(min(a,b)) else: if a%k!=0: d.append(a) if b%k!=0: d.append(b) s=sum(c) print('Максимально возможная сумма -',s) d=sorted(d) if s%k!=0: print('Максимально возможная сумма не кратная к-',s) else: for i in range(len(d)): if (s-d[ i])%k!=0: g.append((s-d[ i])) print('Максимально возможная сумма не кратная к-',max(g)) [/pre2] Собственно вопрос - будет ли данное решение достаточным при любом другом наборе исходных данных? Исходные файлы: [url=https://1drv.ms/t/s!ApKQsGxfHAHQgfYnbg0Mv7rk0QV0yg]https://1drv.ms/t/s!ApKQsGxfHAHQgfYnbg0Mv7rk0QV0yg[/url] [url=https://1drv.ms/t/s!ApKQsGxfHAHQgfcnJm_x2jJMVUmW5A]https://1drv.ms/t/s!ApKQsGxfHAHQgfcnJm_x2jJMVUmW5A[/url]
Ответов - 2
Поляков: daimon2006 пишет: [pre2] if a%k!=0 and b%k!=0: d.append(min(a,b))[/pre2] Не ясен смысл этого оператора. Если обе разности делятся на k, то нет смысла их использовать. Массивы не нужны. Вместо массива c можно просто считать сумму. Вместо массива d можно вести минимум (dmin). Если сумма s делится на k, то ответ s - dmin, и массив g тоже не нужен. Посмотрите разбор задачи Р-00 в файле ege27.doc.
Mike_Boone: Для решения этой задачи достаточно выдвинуть одну Лемму: Если максимально возможная сумма кратна k, то достаточно произвести одну замену, не кратную k и минимальную. Если мы произвели одну замену, то последующие замены лишь будут уменьшать нашу разность в пустую. Также стоит заметить, если такой замены нет, то сумма всегда кратна k для всех 2^n наборов, потому что sum == 0 (mod k) и замена во всех парах сравнима с нулём по модулю k <=> sum == 0 (mod k) для любого из 2^n наборов. Программа:[pre2] s = 0 d = 10 ** 18 k = 103 for i in range(int(input())): a, b, c = map(int, input().split()) a, b, c = max(a,b,c), (a + b + c) - (max(a, b, c) + min(a, b, c)), min(a, b, c) s += a if (a - b) % k != 0: d = min(d, a - b) if (a - c) % k != 0: d = min(d, a - c) if (s % k != 0): print(s) else: print(s - d)[/pre2]
полная версия страницы