№ 2663 (27 задание) ошибка или моя ошибка, что навряд ли

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

№ 2663 (27 задание) ошибка или моя ошибка, что навряд ли

hellprogram: № 2663 Ответ на сайте: 66228 203412732 Моя программа: with open('1.txt','r') as list: n = int(list.readline()) sum = 0 minraz = [10000 for i in range(3)] for i in range(n): x,y = map(int, list.readline().split()) if abs(x-y) < minraz[1] and abs(x-y) % 3 == 1: minraz[1] = abs(x-y) if abs(x-y) < minraz[2] and abs(x-y) % 3 == 2: minraz[2] = abs(x-y) sum += min(x,y) if sum % 3 == 0: print(sum) if sum % 3 == 1: sum += minraz[2] if sum % 3 == 2: sum += minraz[1] print(sum) Вывод моей программы: 66480 203412732 Выдаёт верный ответ только у файла Б, а у А файла ответ не подходит, хотя я проверил, что никаких ошибок здесь нет

Ответов - 10

Поляков: Это задача № 3 из основного сборника. На сайте есть решения всех 27-х задач, сравните авторское решение со своим.

hellprogram: for k in range(1, D): ----r0 = (r + k) % D ----dMinNew[r0] = min( d+dMin[k], dMinNew[r0] ) Можете ли вы пояснить, что делает это место программы в общем файле? Fin = open("27-3a.txt") D = 3 N = int( Fin.readline() ) s, dMin = 0, [10001]*D for i in range(N): ----a, b = map( int, Fin.readline().split() ) ----s += min( a, b ) ----d = abs( a-b ) ----r = d % D ----if r > 0: --------dMinNew = dMin[:] ----for k in range(1, D): --------r0 = (r + k) % D --------dMinNew[r0] = min( d+dMin[k], dMinNew[r0] ) ----dMinNew[r] = min( d, dMinNew[r] ) ----dMin = dMinNew[:] ----print(dMinNew) if s % D == 0: ----print( s ) else: ----print( s, s%D ) ----print( dMin ) ----print( s + dMin[D - s % D] ) Fin.close()

Поляков: hellprogram пишет: Можете ли вы пояснить, что делает это место программы в общем файле? Почитайте, пожалуйста, разбор в файле ege27.doc.

Поляков: Код программы оформляется с помощью тэга [ pre2 ].

Илья Женецкий: [pre2] for l in 'ab': ...f = open(f'data/2663{l}.txt') ...n = int(f.readline()) ...delta, s = [float('inf')]*3, 0 ...for i in range(n): ......a, b = map(int, f.readline().split()) ......s += min(a, b) ...delta[abs(a-b)%3]=min(delta[abs(a-b)%3], abs(a-b)) ...f.close() ...if s%3!=0: ......s-=delta[s%3] ...print(s, end=' => ') ...print(f'{s}%3={s%3}') [/pre2] Программа выходит: 65751 => 65751%3=0 203412729 => 203412729%3=0

Поляков: Илья Женецкий пишет: Программа выходит: 65751 => 65751%3=0 203412729 => 203412729%3=0 А как у вас получается результат, который меньше минимальной суммы БЕЗ дополнительных ограничений?

Илья Женецкий: [pre2] for l in 'ab': ...f = open(f'data/2663{l}.txt') ...n = int(f.readline()) ...delta, s = [float('inf')]*3, 0 ...for i in range(n): ......a, b = map(int, f.readline().split()) ......s += min(a, b) ...delta[abs(a-b)%3]=min(delta[abs(a-b)%3], abs(a-b)) ...f.close() ...if s%3!=0: ......s-=delta[s%3] ...print(s, end=' => ') ...print(f'{s}%3={s%3}')[/pre2] Программа выходит: 65751 => 65751%3=0 203412729 => 203412729%3=0

Прохоренко В.С.: В 27 задании №3 (или №2663 из генератора) из основного сборника ответ для файла А 66228 неверный. Правельный ответ 66480. Я сравнил оба авторских решения со своим в них есть ошибки. ---------------------------------------------- Первое авторское решение: Fin = open("27-3b.txt") N = int( Fin.readline() ) B = 3 INF = 10**10 sums = [0 for i in range(B)] for i in range(N): ----ab = list(map( int, Fin.readline().split() )) ----sumsNext = [INF]*B ----for s in sums: --------for x in ab: ------------r = s + x ------------if r < sumsNext[r%B]: ----------------sumsNext[r%B] = r ----sums = sumsNext[:] Fin.close() print( sums[0] ) ************************************* В этом решении строка "r = s + x" суммирует без условия каждое из входных чисел, а далее по условию "if r < sumsNext[r%B]:", которое не проверяет остаток, приравнивает полученную сумму не взирая на различный остаток к элементу из списка (массива из трёх элементов с разными остатками) -------------------------------------------- Второе авторское решение: Fin = open("27-3b.txt") D = 3 N = int( Fin.readline() ) s, dMin = 0, [10001]*D for i in range(N): ----a, b = map( int, Fin.readline().split() ) ----s += min( a, b ) ----d = abs( a-b ) ----r = d % D ----if r > 0: --------dMinNew = dMin[:] --------for k in range(1, D): ------------r0 = (r + k) % D ------------dMinNew[r0] = min( d+dMin[k], dMinNew[r0] ) --------dMinNew[r] = min( d, dMinNew[r] ) --------dMin = dMinNew[:] if s % D == 0: ----print( s ) else: ----print( s, s%D ) ----print( dMin ) ----print( s + dMin[D - s % D] ) Fin.close() ******************************************* В этом решении цикл for k in range(1, D): ----r0 = (r + k) % D ----dMinNew[r0] = min( d+dMin[k], dMinNew[r0] ) неверно обрабатывает элементы массива, хранящий в себе минимальную разницу чисел по остаткам, из за этого в итоге находит [660, 127, 350]. А должен был получить [738, 127, 602] Это лекго проверить даже решением в ручную [3381, 1043] Разница - 2338 Остаток - 1 [4212, 7995] Разница - 3783 Остаток - 0 [5930, 2891] Разница - 3039 Остаток - 0 [5053, 1528] Разница - 3525 Остаток - 0 [4694, 479] Разница - 4215 Остаток - 0 [4225, 3448] Разница - 777 Остаток - 0 [2233, 5994] Разница - 3761 Остаток - 2 [6464, 5389] Разница - 1075 Остаток - 1 [7084, 6070] Разница - 1014 Остаток - 0 [222, 824] Разница - 602 Остаток - 2 минимальная разница для остатка 2 [7994, 610] Разница - 7384 Остаток - 1 [7748, 8103] Разница - 355 Остаток - 1 [9789, 9051] Разница - 738 Остаток - 0 минимальная разница для остатка 0 [3897, 8342] Разница - 4445 Остаток - 2 [3709, 6536] Разница - 2827 Остаток - 1 [3127, 3437] Разница - 310 Остаток - 1 [3362, 3489] Разница - 127 Остаток - 1 минимальная разница для остатка 1 [3859, 3112] Разница - 747 Остаток - 0 [2396, 2173] Разница - 223 Остаток - 1 [4275, 1574] Разница - 2701 Остаток - 1 Итого получам самую минимальную разнуцу по трём остаткам [738, 127, 602] Минимальная сумма из 20 строк 65878, но она не кратная трём (остаток 1), делаем вывод что нужно прибавить 602 (число с отстаком 2). Ответ 66480 ------------------------------------------------------------------------------------------------- МОЁ РЕШЕНИЕ (автор Прохоренко Владимир Сергеевич) для всех задач такого типа. Из пары (тройки, четверки и т.д.) чисел выбрать ОДНО число так, чтобы сумма выбранных была min и кратная k. p = 2 # количество чисел в строке k = 3 # кратность этому числу x = 10000 # максимальное значение входных чисел s, ost = 0, [x + 1] * k m = x + 1 with open('input.txt') as f: ----for i in range(int(f.readline())): --------arr = sorted(map(int, f.readline().split())) --------s += arr[0] --------for j in range(1, p): # количество чисел в строке ------------ost[(arr[j] - arr[0]) % k] = min(arr[j] - arr[0], ost[(arr[j] - arr[0]) % k]) for i in range(1, k - 2): ----for j in range(i + 1, k - 1): --------if i + j == k - s % k: ------------print(i, j) ------------m = min(m, ost[i] + ost[j], ost[k - s % k]) m = min(m, ost[k - s % k]) print(s + m) Ответ 66480

Поляков: Прохоренко В.С. пишет:Итого получам самую минимальную разнуцу по трём остаткам [738, 127, 602] Вы не учитываете, что оптимальное решение может быть получено несколькими заменами. В данном случае мы можем использовать строки с разницей 127 и 223.

VectorASD: Моё решение задачи с учётом бесконечного множества замен на основе массива разниц :S https://egekp.unoforum.pro/?1-16-0-00000256-000-0-0-1623728180 Конечно в реальных условиях можно на дурачка найти ответ, просто вывев сортированный массив разниц и там будет видно, что САМЫЕ первые 2 числа разниц и будут давать верный ответ (но не по отдельности), но мой вариант круче XD

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