Как можно реализовать решение подобной задачи на python?

Question

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

Входные данные.

Файл A
Файл B

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

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

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

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

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

Answer 1

Нужно считать просто максимальную сумму (1) и в этом же цикле найти пару с минимальной разницей неделящейся на три(2). Если конечная сумма (1) делится на три, просто вычти найденную разницу (2). И получишь ответ.

Answer 2

Думаю, с чтением/записью из/в файл(а) разберетесь сами:

def find_max_sum(pairs):
    max_sum = 0
    min_diff = None
    for pair in pairs:
        max_sum += max(pair)
        diff = abs(pair[1]-pair[0])
        if (diff%3) and ((min_diff is None) or (diff < min_diff)):
            min_diff = diff
    if max_sum%3:
        return max_sum
    if min_diff is not None:
        return max_sum-min_diff
    return -1

Пример использования:

pairs = [
    [1, 3],
    [5, 12],
    [6, 9],
    [5, 4],
    [3, 3],
    [1, 1],
]
print(find_max_sum(pairs))

Answer 3

Вот код для обоих файлов:

with open('27-A_demo.txt') as f:
    N = int( f.readline() )
    s, dMin  = 0, 10001
    for i in range(N):
        a, b = map( int, f.readline().split() )
        s += max( a, b )
        d = abs( a-b )
        if d % 3 > 0:
            dMin = min( d, dMin )
    if s % 3 != 0:
        print( s )
    else:
        print( s-dMin )

БЛОГ НА HUSL

Как можно реализовать решение подобной задачи на python?

Ответы (3 шт):