Задача КИМ №27 (Решение на Питоне)

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные: Даны два входных файла: файл A (27-2a.txt) и файл B (27-2b.txt), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

Пример входного файла:

6
1 3
5 11
6 9
5 4
3 3
1 1

Для указанных входных данных значением искомой суммы должно быть число 30.

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

Решение:

f= open("27-2b.txt")

delit = 3

n = int( f.readline() )

s, dmn  = 0, [10001]*delit

for i in range(n):

  a, b = map( int, f.readline().split() )

  s += max( a, b )

  d = abs( a-b )

  r = d % delit

  if r > 0:

    dmin = dmn[:]

    for k in range(1, delit):

      r0 = (r + k) % delit

      dmin[r0] = min( d+dmn[k], dmn[r0] )

    dmin[r] = min( d, dmn[r] )

    dmn = dmin[:]

if s % delit == 0:

  print( s )

else:

   print( s - dmn[s % delit] )

f.close()

Вот соответственно эти числа: 109737 401536407