Отправлено: 11.04.21 16:39. Заголовок: № 2663 (27 задание) ошибка или моя ошибка, что навряд ли

№ 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
Выдаёт верный ответ только у файла Б, а у А файла ответ не подходит, хотя я проверил, что никаких ошибок здесь нет

 Отправлено: 11.04.21 16:48. Заголовок: Это задача № 3 из ос..

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

 Отправлено: 11.04.21 17:27. Заголовок: for k in range(1, D)..

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()

 Отправлено: 11.04.21 17:35. Заголовок: hellprogram пишет: М..

hellprogram пишет:

цитата:

Можете ли вы пояснить, что делает это место программы в общем файле?

Почитайте, пожалуйста, разбор в файле ege27.doc.

 Отправлено: 11.04.21 17:36. Заголовок: Код программы оформл..

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

 Отправлено: 12.04.21 15:18. Заголовок: думаю в ответе опечатка

 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}') 
 

Программа выходит:
65751 => 65751%3=0
203412729 => 203412729%3=0

 Отправлено: 12.04.21 15:46. Заголовок: Илья Женецкий пишет:..

Илья Женецкий пишет:

цитата:

Программа выходит: 65751 => 65751%3=0 203412729 => 203412729%3=0

А как у вас получается результат, который меньше минимальной суммы БЕЗ дополнительных ограничений?

 Отправлено: 16.04.21 09:35. Заголовок: думаю в ответе опечатка

 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}')

Программа выходит:
65751 => 65751%3=0
203412729 => 203412729%3=0

 Отправлено: 08.06.21 08:20. Заголовок: Ошибки в авторских решениях

В 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

 Отправлено: 08.06.21 08:36. Заголовок: Прохоренко В.С. пише..

Прохоренко В.С. пишет:

цитата:

Итого получам самую минимальную разнуцу по трём остаткам [738, 127, 602]

Вы не учитываете, что оптимальное решение может быть получено несколькими заменами. В данном случае мы можем использовать строки с разницей 127 и 223.

 Отправлено: 15.06.21 06:50. Заголовок: Пишу чисто для того, кто задал эту тему

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