Е27.29 сумма всех выбранных чисел имела такую же последнюю цифру

Дана последовательность, которая состоит из пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел имела такую же последнюю цифру, как наибольшая возможная, и при этом была минимальной возможной.
Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — минимальную возможную сумму, соответствующую условиям задачи.

Входные данные: Даны два входных файла: файл А и файл В, каждый из которых содержит в первой строке количество чисел N (1 <_ N <_ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10000.

Пример входного файла:
6
2 7
1 8
10 2
6 4
3 3
3 10
Для указанных данных максимальная сумма — 44 (7 + 8 + 10 + 6 + 3 + 10), её последняя цифра 4. Искомая минимальная сумма, имеющая последнюю цифру 4, равна 24, она соответствует выбору чисел (2 + 8 + 2 + 6 + 3 + 3).
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла В.
Предупреждение: для обработки файла В не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Ответ:

(полученное из первого файла)

(полученное из второго файла)

27-A 27-B

«Некрыловские варианты» от Евгения Джобса — Вариант 5

Решение:

f = open('27-B.txt')
n = int(f.readline())
s = f.readlines()
num = []
nmin = nmax = 0
for i in s:
    a, b = map(int, i.split())
    num.append(abs(a - b))
    nmax += max(a, b)
    nmin += min(a, b)
if nmax % 10 != nmin % 10:
    k = nmax % 10
    num.sort()
    for i in num:
        if (nmin +i )%10 == k:
            print(nmin + i)
            break

f = open('27-B.txt')

n = int(f.readline())

s = f.readlines()

num = []

nmin = nmax = 0

for i in s:

a, b = map(int, i.split())

num.append(abs(a - b))

nmax += max(a, b)

nmin += min(a, b)

if nmax % 10 != nmin % 10:

k = nmax % 10

num.sort()

for i in num:

if (nmin +i )%10 == k:

print(nmin + i)

break

Другое решение только на 27-A (Каримов Минтимер)

from itertools import product as pr

input = open('27-A.txt').readline
n = int(input())
q = [sorted(map(int, input().split())) for _ in range(n)]
mx = 0
for i in range(n): mx += q[i][1]
ans = float('inf')
for m in pr((0, 1), repeat=n):
    s = 0
    for i in range(n): s += q[i][m[i]]
    if s % 10 == mx % 10: ans = min(ans, s)
print(ans)

from itertools import product as pr

input = open('27-A.txt').readline

n = int(input())

q = [sorted(map(int, input().split())) for _ in range(n)]

mx = 0

for i in range(n): mx += q[i][1]

ans = float('inf')

for m in pr((0, 1), repeat=n):

s = 0

for i in range(n): s += q[i][m[i]]

if s % 10 == mx % 10: ans = min(ans, s)

print(ans)

Еще одно решение (Каримов Минтимер)

def f(s, i, j):
    global ans
    if s % 10 == mx % 10: ans = min(ans, s)
    if i == 10: return
    for l in range(min(j, len(q[i])) + 1):
        f(s + q[i][l], i + 1, j - l)

input = open('27-B.txt').readline
n = int(input())
mx = mn = 0
q = [[] for _ in range(10)]
for _ in range(n):
    a, b = sorted(map(int, input().split()))
    c = b - a
    mn += a
    mx += b
    q[c % 10].append(c)
q = [sorted(i) for i in q]
ans = float('inf')
for i in range(10):
    q[i]=[0]+q[i]
    for j in range(1,len(q[i])):
        q[i][j]+=q[i][j-1]
f(mn, 0, 10)
print(ans)

def f(s, i, j):

global ans

if s % 10 == mx % 10: ans = min(ans, s)

if i == 10: return

for l in range(min(j, len(q[i])) + 1):

f(s + q[i][l], i + 1, j - l)

input = open('27-B.txt').readline

n = int(input())

mx = mn = 0

q = [[] for _ in range(10)]

for _ in range(n):

a, b = sorted(map(int, input().split()))

c = b - a

mn += a

mx += b

q[c % 10].append(c)

q = [sorted(i) for i in q]

ans = float('inf')

for i in range(10):

q[i]=[0]+q[i]

for j in range(1,len(q[i])):

q[i][j]+=q[i][j-1]

f(mn, 0, 10)

print(ans)

Ответ: 64573
189977078