04 Пары/тройки чисел, выбрать из каждой, кратность - Каталог заданий по ЕГЭ

Ошибка.
Попробуйте повторить позже

Задача 41#25625Максимум баллов за задание: 2

Задание выполняется с использованием прилагаемых файлов

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

Входные файлы:

Файл 27 A

Файл 27 B

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

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

4

5 6

6 13

14 9

12 18

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

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

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

Вложения к задаче

Задание_27_A__cke2.txt

Задание_27_B__cke6.txt

Показать ответ и решение

Метод минимальных разностей

f = open(’Задание_27_B__cke6__rs77.txt’)  # Открываем нужный файл
n = int(f.readline())

k = 4  # Число, которому должна быть кратна сумма
mr = [10 ** 10] * k  # Список для хранения минимальных разностей по остаткам
s = 0  # Переменная для максимальной суммы
for i in range(n):
    a, b = map(int, f.readline().split())  # Считываем числа
    s += max(a, b)  # Прибавляем к сумме максимальное число из пары
    r = abs(a - b)  # Разность между элементами

    mr1 = mr[:]  # Создаём копию списка разностей
    for j in range(k):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % k]:
            mr[(r + mr1[j]) % k] = r + mr1[j]

    # Если текущая разность меньше разности в списке
    if r < mr[r % k]:
        mr[r % k] = r

# Если сумма в итоге не кратна k
if s % k != 0:
    # Отнимаем от макс. суммы разность с таким же остатком
    s -= mr[s % k]

print(s)

Метод частичных сумм

f = open(’Задание_27_B__cke6__rs77.txt’)
n = int(f.readline())
k = 4
m = [0]*k

for i in range(n):
    x, y = map(int, f.readline().split())
    m_n = [-10000]*k
    for j in range(k):
        t = (m[j] + x) % k
        m_n[t] = max(m_n[t], m[j] + x)
    for j in range(k):
        t = (m[j] + y) % k
        m_n[t] = max(m_n[t], m[j] + y)
    m = m_n.copy()
print(m[0])

Ответ: 133796 269597900

Ошибка.
Попробуйте повторить позже

Задача 42#26000Максимум баллов за задание: 2

Задание выполняется с использованием прилагаемых файлов

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

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

Первая строка входного файла содержит число $N$ — общее количество пар в наборе, не превышающее $100000$ . Каждая из следующих $N$ строк содержит два натуральных числа, не превышающих $10000$ .

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

$5$

$60 31$

$27 92$

$39 88$

$71 44$

$13 82$

Для указанных данных надо выбрать числа $60$ , $92$ , $88$ , $44$ и $82$ . Сумма выбранных чисел равна $366$ и она максимальна и чётна. В ответе надо записать число $366$ .

Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе укажите два числа через пробел: сначала значение искомой суммы для файла A, затем для файла B.

Вложения к задаче

Задание_27_A__g57u.txt

Задание_27_B__g57y.txt

Показать ответ и решение

f = open(’Задание_27_A__g57u.txt’)
n = int(f.readline())
ans = 0  # Переменная для максимальной суммы
diff = 10000000000  # Минимальная разность, некратная 2
for i in range(n):
    a = [int(i) for i in f.readline().split()]
    ans += max(a)  # Прибавляем максимальное число к сумме
    if abs(a[0] - a[1]) % 2 == 1:  # Если разность чисел некратна 2
        diff = min(diff, abs(a[0] - a[1]))  # Пробуем сохранить разность
if ans % 2 == 1:  # Если сумма в итоге некратна 2
    ans -= diff  # Вычитаем некратную разность, чтобы сумма в итоге стала кратной
print(ans)

Ответ: 13848 39383472

Ошибка.
Попробуйте повторить позже

Задача 43#26214Максимум баллов за задание: 2

Задание выполняется с использованием прилагаемых файлов

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

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

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

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

5

4 9

2 13

18 11

72 41

9 12

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

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

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

Вложения к задаче

Задание 27 A.txt

Задание 27 B.txt

Показать ответ и решение

f = open(’Задание 27 B.txt’)
n = int(f.readline())

k = 8  # Число, которому должна быть некратна сумма
mr = 10 ** 10  # Минимальная разность, некратная k
s = 0  # Сумма выбранных чисел
for i in range(n):
    a, b = map(int, f.readline().split())
    s += max(a, b)  # Прибавляем максимальное число в паре
    r = abs(a - b)  # Разность между элементами для замены мин. числа на макс. число

    # Если новая разность меньше текущей минимальной разности
    if (r < mr) and (r % k != 0):
        mr = r

if s % k == 0:  # Если в итоге сумма кратна k
    s -= mr  # От макс. суммы отнимаем минимальную разность для изменения остатка

print(s)

Ответ: 134763 549405231

Ошибка.
Попробуйте повторить позже

Задача 44#26962Максимум баллов за задание: 2

Задание выполняется с использованием прилагаемых файлов

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

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

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

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

$5$

$5 10$

$6 2$

$3 11$

$12 9$

$7 4$

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

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

Вложения к задаче

Задание_27-A__odg9.txt

Задание_27-B__odgf.txt

Показать ответ и решение

f = open(’27.txt’)
n = int(f.readline())

k = 23  # Число, которому должна быть некратна сумма
mr = 10 ** 10  # Минимальная разность, некратная k
s = 0  # Сумма выбранных чисел
for i in range(n):
    a, b = map(int, f.readline().split())
    s += min(a, b)  # Прибавляем минимальное число в паре
    r = abs(a - b)  # Разность между элементами для замены мин. числа на макс. число

    # Если новая разность меньше текущей минимальной разности
    if (r < mr) and (r % k != 0):
        mr = r

if s % k == 0:  # Если в итоге сумма кратна k
    s += mr  # К мин. сумме прибавляем минимальную разность для изменения остатка

print(s)

Ответ: 67087 200157478

Ошибка.
Попробуйте повторить позже

Задача 45#27470Максимум баллов за задание: 2

Задание выполняется с использованием прилагаемых файлов

Имеется набор данных, состоящий из n пар натуральных чисел. Выбирается одно число из пары так, чтобы сумма всех таких чисел была максимальна и кратна $7$ или $11$ , но не $7$ и $11$ одновременно.Программа должна напечатать одно число — максимальную сумму удовлетворяющую условиям задачи.

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

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

Пример входных данных:

$3$

$77 40$

$10 77$

$77 30$

Максимальная сумма, которую можно получить равна $(77+ 77+ 77)$ , но она кратна одновременно и $7$ , и $11$ , что недопустимо по условию задачи. Сумма $40+ 77+ 30$ подходит по условиям задачи и является максимальной. Ответом для примера будет: $147$

Вложения к задаче

Задание_27_A__ozaw.txt

Задание_27_B__ozb1.txt

Показать ответ и решение

Метод минимальных разностей

f = open("Задание_27_A__ozaw.txt")
n = int(f.readline())

mr = [10 ** 10] * (7 * 11)  # Список для хранения минимальных разностей по остаткам
maxS = 0  # Максимальная сумма чисел
for i in range(n):
    a, b = map(int, f.readline().split())  # Считываем числа
    maxS += max(a, b)  # Прибавляем к сумме максимальное число из пары
    r = abs(a - b)  # Разность между элементами

    mr1 = mr[:]  # Создаём копию списка разностей
    for j in range(77):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % 77]:
            mr[(r + mr1[j]) % 77] = r + mr1[j]

    # Если текущая разность меньше разности в списке
    if r < mr[r % 77]:
        mr[r % 77] = r

# Сумма делится на оба числа
if maxS % 7 == 0 and maxS % 11 == 0:
    # Нужно найти такую мин. разность, которая изменит только один остаток:
    # либо остаток от деления на 7, либо остаток от деления на 11
    d = 10 ** 10
    for j in range(77):
        count = 0  # Количество чисел, на которое делится сумма
        if (maxS - mr[j]) % 7 != 0:
            count += 1
        if (maxS - mr[j]) % 11 != 0:
            count += 1
        if count == 1:  # Если сумма не делится на одно число, запоминаем разность
            d = min(mr[j], d)

    maxS -= d  # Вычитаем итоговую мин. разность

# Сумма не делится ни на одно число
elif maxS % 7 != 0 and maxS % 11 != 0:
                                                                                                     
                                                                                                     
    # Также нужно найти мин. разность, которая даст кратность только одному числу
    d = 10 ** 10
    for j in range(77):
        count = 0  # Количество чисел, на которое делится сумма
        if (maxS - mr[j]) % 7 == 0:
            count += 1
        if (maxS - mr[j]) % 11 == 0:
            count += 1
        if count == 1:  # Если сумма делится на одно число, запоминаем разность
            d = min(mr[j], d)

    maxS -= d  # Вычитаем итоговую мин. разность

print(maxS)  # Выводим итоговую сумму выбранных чисел

Метод частичных сумм

file = open("Задание_27_A__ozaw.txt")
n = int(file.readline())
a = [-1000000000000] * 77
a[0] = 0

for i in range(n):
    x, y = [int(j) for j in file.readline().split()]
    a_new = [-1000000000000] * 77
    for j in range(77):
        t = (a[j] + x) % 77
        a_new[t] = max(a_new[t], a[j] + x)
    for j in range(77):
        t = (a[j] + y) % 77
        a_new[t] = max(a_new[t], a[j] + y)
    a = a_new.copy()
ans = -1000000000000
for i in range(77):
    if (i % 7 == 0 and i % 11 != 0) or (i % 7 != 0 and i % 11 == 0):
        ans = max(ans, a[i])
print(ans)

Ответ: 1485 666329867

Ошибка.
Попробуйте повторить позже

Задача 46#29243Максимум баллов за задание: 2

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

Вложения к задаче

4.txt

Показать ответ и решение

f = open(’4.txt’)
n = int(f.readline())
ans = 0  # Переменная для максимальной суммы
diff = 10000000000  # Минимальная разность, некратная 2
for i in range(n):
    a = [int(i) for i in f.readline().split()]
    ans += max(a)  # Прибавляем максимальное число к сумме
    if abs(a[0] - a[1]) % 2 == 1:  # Если разность чисел некратна 2
        diff = min(diff, abs(a[0] - a[1]))  # Пробуем сохранить разность
if ans % 2 == 1:  # Если сумма в итоге некратна 2
    ans -= diff  # Вычитаем некратную разность, чтобы сумма в итоге стала кратной
print(ans)

Ответ: 38891026

Ошибка.
Попробуйте повторить позже

Задача 47#29244Максимум баллов за задание: 2

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

Вложения к задаче

5.txt

Показать ответ и решение

Метод минимальных разностей

f = open(’5.txt’)  # Открываем нужный файл
n = int(f.readline())

k = 3  # Число, которому должна быть кратна сумма
mr = [10 ** 10] * k  # Список для хранения минимальных разностей по остаткам
s = 0  # Переменная для максимальной суммы
for i in range(n):
    a, b = map(int, f.readline().split())  # Считываем числа
    s += max(a, b)  # Прибавляем к сумме максимальное число из пары
    r = abs(a - b)  # Разность между элементами

    mr1 = mr[:]  # Создаём копию списка разностей
    for j in range(k):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % k]:
            mr[(r + mr1[j]) % k] = r + mr1[j]

    # Если текущая разность меньше разности в списке
    if r < mr[r % k]:
        mr[r % k] = r

# Если сумма в итоге не кратна k
if s % k != 0:
    # Отнимаем от макс. суммы разность с таким же остатком
    s -= mr[s % k]

print(s)

Метод частичных сумм

file = open(’5.txt’, ’rt’)

def f(a, a_new, k):
    for j in range(3):
        cur_summ = a[j] + k
        ost = cur_summ % 3
        if cur_summ > a_new[ost]:
            a_new[ost] = cur_summ


a = [-1000000] * 3
a[0] = 0
n = int(file.readline())
for i in range(n):
    x, y = map(int, file.readline().split())
    a_new = [-1000000] * 3
    f(a, a_new, x)
    f(a, a_new, y)
    for j in range(3):
        a[j] = a_new[j]
print(a[0])

Ответ: 39167997

Ошибка.
Попробуйте повторить позже

Задача 48#29245Максимум баллов за задание: 2

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

Вложения к задаче

27A.txt

Показать ответ и решение

Метод минимальных разностей

f = open(’6.txt’)  # Открываем нужный файл
n = int(f.readline())

k = 10  # Число, которому должна быть кратна сумма
mr = [10 ** 10] * k  # Список для хранения минимальных разностей по остаткам
s = 0  # Переменная для максимальной суммы
for i in range(n):
    a, b = map(int, f.readline().split())  # Считываем числа
    s += max(a, b)  # Прибавляем к сумме максимальное число из пары
    r = abs(a - b)  # Разность между элементами

    mr1 = mr[:]  # Создаём копию списка разностей
    for j in range(k):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % k]:
            mr[(r + mr1[j]) % k] = r + mr1[j]

    # Если текущая разность меньше разности в списке
    if r < mr[r % k]:
        mr[r % k] = r

# Если сумма в итоге не кратна k
if s % k != 0:
    # Отнимаем от макс. суммы разность с таким же остатком
    s -= mr[s % k]

print(s)

Метод частичных сумм

file = open(’6.txt’, ’rt’)

def f(a, a_new, k):
    for j in range(10):
        cur_summ = a[j] + k
        ost = cur_summ % 10
        if cur_summ > a_new[ost]:
            a_new[ost] = cur_summ


a = [-1000000] * 10
a[0] = 0
n = int(file.readline())
for i in range(n):
    x, y = map(int, file.readline().split())
    a_new = [-1000000] * 10
    f(a, a_new, x)
    f(a, a_new, y)
    for j in range(10):
        a[j] = a_new[j]
print(a[0])

Ответ: 61590

Ошибка.
Попробуйте повторить позже

Задача 49#29374Максимум баллов за задание: 2

Имеется набор данных, состоящий из пар положительных целых чисел и нулей. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на $17$ и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – минимально возможную сумму, соответствующую условиям задачи. В ответе укажите два числа через пробел: сначала сумму для файла А, затем для файла Б.

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

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

Пример входных данных:

$6$

$106 16$

$56 57$

$13 5$

$96 57$

$19 2$

$111 112$

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

Вложения к задаче

Задание_27_A__ra55.txt

Задание_27_B__ra54.txt

Показать ответ и решение

Метод минимальных разностей

f = open("3B.txt")
n = int(f.readline())

k = 17  # Число, которому должна быть кратна сумма
mr = [10 ** 10] * k  # Список для хранения минимальных разностей по остаткам
s = 0  # Переменная для минимальной суммы
for i in range(n):
    a, b = map(int, f.readline().split())  # Считываем числа
    s += min(a, b)  # Прибавляем к сумме минимальное число из пары
    r = abs(a - b)  # Разность между элементами

    mr1 = mr[:]  # Создаём копию списка разностей
    for j in range(k):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % k]:
            mr[(r + mr1[j]) % k] = r + mr1[j]

    # Если текущая разность меньше разности в списке
    if r < mr[r % k]:
        mr[r % k] = r

# Если сумма в итоге не кратна k
if s % k != 0:
    s += mr[k - s % k]  # Прибавляем к мин. сумме разность с недостающим остатком

print(s)

Метод частичных сумм

f = open("3B.txt")

n = int(f.readline())
INF = 100000000000000000
a = [INF] * 17
a[0] = 0

for i in range(n):
    x, y = map(int, f.readline().split())
    a_new = [INF] * 17
    for j in range(17):
        t = (a[j] + x) % 17
        a_new[t] = min(a_new[t], a[j] + x)
    for j in range(17):
        t = (a[j] + y) % 17
        a_new[t] = min(a_new[t], a[j] + y)
    a = a_new.copy()

print(a[0])

Ответ: 5763 16760980

Ошибка.
Попробуйте повторить позже

Задача 50#29992Максимум баллов за задание: 2

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

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

Пример входных данных:

5

3 8

35 29

13 31

4 4

44 44

Для таких входных данных значением искомое суммы будет число 122

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

Вложения к задаче

27PA.txt

27PB.txt

Показать ответ и решение

f = open("27.txt")
n = int(f.readline())
ans = 0  # Переменная для максимальной суммы
diff = 10 ** 10  # Минимальная разность, некратная 4
for i in range(n):
    a = [int(i) for i in f.readline().split()]
    ans += max(a)  # Прибавляем максимальное число к сумме
    if abs(a[0] - a[1]) % 4 != 0:  # Если разность чисел некратна 4
        diff = min(diff, abs(a[0] - a[1]))  # Пробуем сохранить разность

if ans % 4 == 0:  # Если сумма в итоге делится на 4
    if diff != 10 ** 10:
        ans -= diff  # Вычитаем некратную разность, чтобы сумма в итоге стала некратной
    else:
        ans = 0  # Иначе присваиваем 0 для вывода
print(ans)

Ответ: 10726 32718210

Ошибка.
Попробуйте повторить позже

Задача 51#29993Максимум баллов за задание: 2

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

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

Пример входных данных:

4

6 12

7 45

3 45

2 7

Для таких входных данных значением искомое суммы будет число 104

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

Вложения к задаче

27PA.txt

27PB.txt

Показать ответ и решение

f = open("27.txt")
n = int(f.readline())
ans = 0  # Переменная для максимальной суммы
diff = 10 ** 10  # Минимальная разность, некратная 2
for i in range(n):
    a = [int(i) for i in f.readline().split()]
    ans += max(a)  # Прибавляем максимальное число к сумме
    if abs(a[0] - a[1]) % 2 == 1:  # Если разность чисел некратна 2
        diff = min(diff, abs(a[0] - a[1]))  # Пробуем сохранить разность

if ans % 2 == 1:  # Если сумма в итоге некратна 2
    if diff != 10 ** 10:
        ans -= diff  # Вычитаем некратную разность, чтобы сумма в итоге стала кратной
    else:
        ans = 0  # Иначе присваиваем 0 для вывода
print(ans)

Ответ: 10756 32719168

Ошибка.
Попробуйте повторить позже

Задача 52#29994Максимум баллов за задание: 2

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

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

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

6

1 3

5 11

6 9

5 4

3 3

1 1

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

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

Вложения к задаче

27PA.txt

27PB.txt

Показать ответ и решение

f = open(’1.txt’)
n = int(f.readline())
krat = 4
mr = [100000000500000000]*krat
s = 0
for i in range(n):
    a,b = map(int, f.readline().split())
    s += max(a, b)
    d = abs(a-b)
    mr1 = mr[:] #копия mr
    for j in range(krat):
        #берем разность и складываем с каждым элементом списка mr1
        #сравниваем получившуюся сумму с mr
        #если она меньше, то записываем данную сумму в mr
        if d + mr1[j] < mr[(d+mr[j]) % krat]:
            mr[(d+mr[j]) % krat] = d + mr1[j]
    #проверка, что если разность меньше соответствующего элемента в списке
    #то записываем эту разность в список
    if d < mr[d % krat]:
        mr[d % krat] = d

#Если сумма s не делится на krat, то сумма корректируется
#путем вычитания значения из mr[s % krat]
if s % krat != 0:
    s -= mr[s % krat]
print(s)

Ответ: 10756 32719168

Ошибка.
Попробуйте повторить позже

Задача 53#29995Максимум баллов за задание: 2

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

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

Пример входных данных:

6

7 3

5 2

6 5

6 4

3 2

1 2

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

Вложения к задаче

27PA.txt

27PB.txt

Показать ответ и решение

Метод минимальных разностей

f = open("4B.txt")  # Открываем нужный файл
n = int(f.readline())

k = 3  # Число, которому должна быть кратна сумма
mr = [10 ** 10] * k  # Список для хранения минимальных разностей по остаткам
s = 0  # Переменная для минимальной суммы
for i in range(n):
    a, b = map(int, f.readline().split())  # Считываем числа
    s += min(a, b)  # Прибавляем к сумме минимальное число из пары
    r = abs(a - b)  # Разность между элементами

    mr1 = mr[:]  # Создаём копию списка разностей
    for j in range(k):
        # Ищем минимальную сумму нескольких разностей
        if r + mr1[j] < mr[(r + mr1[j]) % k]:
            mr[(r + mr1[j]) % k] = r + mr1[j]

    # Если текущая разность меньше разности в списке
    if r < mr[r % k]:
        mr[r % k] = r

# Если сумма в итоге не кратна k
if s % k != 0:
    if mr[k - s % k] != 10 ** 10:  # Если нужная разность есть
        s += mr[k - s % k]  # Прибавляем к мин. сумме разность с недостающим остатком
    else:
        s = 0  # Делаем сумму 0 для вывода по условию

print(s)

Метод частичных сумм

f = open("4B.txt")
n = int(f.readline())
ans = [0]*3
for i in range(n):
    a = list(map(int, f.readline().split()))
    ans_new = [100000000]*3

    for k in range(2):
        for j in range(3):
            ost = (a[k] + ans[j]) % 3
            ans_new[ost] = min(ans_new[ost], a[k] + ans[j])
    ans = ans_new[:]
print(ans[0])

Ответ: 5634 16765950

Ошибка.
Попробуйте повторить позже

Задача 54#29996Максимум баллов за задание: 2

Набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. В первой группе должна быть максимальная сумма всех чисел, во второй – минимальная сумма всех чисел, в третьей - сумма оставшихся чисел. Выведите все полученные три суммы на экран. В ответе укажите найденные суммы через пробел сначала для файла А, затем для файла Б.

Пример входных данных:

Первая строка входного файла содержит число $N$ – общее количество троек в наборе. Каждая из следующих N строк содержит три натуральных числа, не превышающих $10000$ .

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

$3$

$7$ $15$ $17$

$11$ $25$ $5$

$4$ $12$ $16$

Для указанных данных искомые суммы равны $58$ $16$ $38$ , они соответствует такому распределению чисел по группам: ( $17$ , $25$ , $16$ ), ( $7$ , $5$ , $4$ ), ( $15$ , $11$ , $12$ ).

Вложения к задаче

27A3.txt

27B3.txt

Показать ответ и решение

f = open(’27A3.txt’)
n = int(f.readline())
maxim, average, minim = 0, 0, 0
for i in range(n):
    a, b, c = [int(x) for x in f.readline().split()]
    maxim += max(a, b, c)
    minim += min(a, b, c)
    average += a + b + c - min(a, b, c) - max(a, b, c)
print(maxim, minim, average)

Ответ: 16204 5248 11412 37317213 12700807 25001629

Ошибка.
Попробуйте повторить позже

Задача 55#29997Максимум баллов за задание: 2

Набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. Сумма всех чисел в первой группе должна быть чётной, во второй – нечётной. Определите максимально возможную сумму всех чисел в третьей группе. Если искомую сумму получить невозможно, то в ответе укажите 0.

Пример входных данных:

Первая строка входного файла содержит число N – общее количество троек в наборе. Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

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

3

8 9 16

20 21 7

5 24 16

Для указанных данных искомая сумма равна 61, она соответствует такому распределению чисел по группам: (8, 20, 5), (9, 7, 16), (16, 21, 24).

Вложения к задаче

27A3.txt

27B3.txt

Показать ответ и решение

f = open(’27A3.txt’)
n = int(f.readline())

mr = 10 ** 10  # Минимальная разность
s1 = 0  # Первая сумма
s2 = 0  # Вторая сумма
s3 = 0  # Максимальная сумма
for i in range(n):
    # Считывание чисел по возрастанию с помощью сортировки sorted()
    x, y, z = sorted(map(int, f.readline().split()))
    s1 += x  # Прибавляем минимальное число тройки
    s2 += y  # Прибавляем среднее число тройки
    s3 += z  # Прибавляем наибольшее число тройки
    d1 = z - x  # Разность для возможной замены на макс. числа на мин. число
    d2 = z - y  # Разность для возможной замены на макс. числа на ср. число

    # В любом случае одна из сумм будет иметь остаток 0 или 1,
    # так что достаточно будет поменять остаток второй суммы.
    # Для этого нужно искать минимальную нечётную разность.
    if (d1 < mr) and (d1 % 2 != 0):
        mr = d1
    if (d2 < mr) and (d2 % 2 != 0):
        mr = d2

if (s1 % 2 == 0 and s2 % 2 == 1) or (s1 % 2 == 1 and s2 % 2 == 0):
    print(s3)
else:
    if mr == 10 ** 10:  # Если нечётная разность не была найдена
        print(0)
    else:  # Иначе вычитаем найденную разность для изменения остатка
        print(s3 - mr)

Ответ: 0 37311110

Ошибка.
Попробуйте повторить позже

Задача 56#29998Максимум баллов за задание: 2

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

Пример входных данных:

Первая строка входного файла содержит число $N$ — общее количество троек в наборе. Каждая из следующих $N$ строк содержит три натуральных числа, не превышающих $10000$ .

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

6

1 3 7

5 12 6

6 9 11

5 4 8

3 5 4

1 1 1

Для указанных данных искомая сумма равна 44.

Вложения к задаче

27A3.txt

27B3.txt

Показать ответ и решение

f = open(’27.txt’)
n = int(f.readline())

k = 55 # Число, которому сумма не должна быть кратна
mr = 10 ** 10  # Минимальная разность
s = 0  # Максимальная сумма
for i in range(n):
    # Считывание чисел по возрастанию с помощью сортировки sorted()
    x, y, z = sorted(map(int, f.readline().split()))
    s += z  # Прибавляем наибольшее число тройки
    d1 = z - x  # Разность для возможной замены на макс. числа на мин. число
    d2 = z - y  # Разность для возможной замены на макс. числа на ср. число

    # Потенциальную замену разностью можно сделать, если:
    # 1) разность меньше минимальной в mr
    # 2) разность не кратна k, чтобы остаток суммы при её вычитании изменился
    if (d1 < mr) and (d1 % k != 0):
        mr = d1
    if (d2 < mr) and (d2 % k != 0):
        mr = d2

if s % k == 0:  # Если в итоге сумма кратна k
    if mr == 10 ** 10:  # Если некратная разность не была найдена
        s = 0  # Делаем сумму равной 0 для вывода
    else:
        s -= mr  # Иначе вычитаем найденную разность для изменения остатка

print(s)

Ответ: 16204 37317213

Ошибка.
Попробуйте повторить позже

Задача 57#30000Максимум баллов за задание: 2

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

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

Пример входных данных:

6

1 3

5 12

6 9

5 4

3 3

5 1

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

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

Вложения к задаче

27B.txt

27A.txt

Показать ответ и решение

Метод минимальных разностей

# Примечание: последняя цифра в 8-ричной записи - это остаток от деления на 8
f = open("6B.txt")
n = int(f.readline())

mr = 10 ** 10  # Минимальные нечётная разность, чтобы поменять остаток
s = 0  # Сумма выбранных чисел
for i in range(n):
    a, b = map(int, f.readline().split())
    s += max(a, b)  # Прибавляем максимальное число в паре
    r = abs(a - b)  # Разность между элементами для замены мин. числа на макс. число

    if (r < mr) and ((r % 8) % 2 != 0):  # Если новая разность меньше и при этом нечётна
        mr = r  # Сохраняем её

# Если в итоге сумма в 8-ричной записи оканчивается на чётную цифру,
# то нужно попробовать вычесть разность
if (s % 8) % 2 == 0:
    if mr == 10 ** 10:  # Если разность не найдена (равна заданному изначально значению)
        s = 0  # Меняем сумму на 0 (как просят в условии)
    else:
        s -= mr  # Иначе вычитаем найденную разность для изменения остатка

print(s)

Метод частичных сумм

f = open("6B.txt")
n = int(f.readline())
ans = [0] * 8
for i in range(n):
    a = [int(i) for i in f.readline().split()]
    ans_new = [-1000000000] * 8
    for k in range(len(a)):
        for j in range(8):
            ost = (ans[j] + a[k]) % 8
            if ans[j] + a[k] > ans_new[ost]:
                ans_new[ost] = ans[j] + a[k]
    ans = ans_new.copy()
print(max(ans[i] for i in range(1, 8, 2)))

Ответ: 0 32719169

Ошибка.
Попробуйте повторить позже

Задача 58#30001Максимум баллов за задание: 2

Имеется набор данных, состоящий из пар натуральных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы шестнадцатеричная запись суммы всех выбранных чисел не оканчивалась на A, B и C и при этом была максимально возможной. Если искомую сумму получить нельзя, то напечатайте 0. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи, записанную в десятичной системе счисления.

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

Пример входных данных:

5

3 8

35 29

13 31

4 4

44 44

Для таких входных данных значением искомой суммы будет число $117$

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

Вложения к задаче

27PA.txt

27PB.txt

Показать ответ и решение

Метод минимальных разностей

# Примечание: последняя цифра в 16-ричной записи - это остаток от деления на 16
f = open(’27.txt’)
n = int(f.readline())

# Минимальные разности, чтобы поменять остаток при оканчивании на какое-то число
mrA = 10 ** 10
mrB = 10 ** 10
mrC = 10 ** 10
s = 0  # Сумма выбранных чисел
for i in range(n):
    a, b = map(int, f.readline().split())
    s += max(a, b)  # Прибавляем максимальное число в паре
    r = abs(a - b)  # Разность между элементами для замены мин. числа на макс. число

    # Если новая разность меньше сохраненных разностей
    if (r < mrA) and (r % 16 != 10):
        mrA = r
    if (r < mrB) and (r % 16 != 11):
        mrB = r
    if (r < mrC) and (r % 16 != 12):
        mrC = r

# Если в итоге сумма в 16-ричной записи оканчивается на цифру,
# то вычитаем соответствующую разность
if s % 16 == 10:
    s -= mrA
if s % 16 == 11:
    s -= mrB
if s % 16 == 12:
    s -= mrC

print(s)

Метод частичных сумм

f = open(’27.txt’)
n = int(f.readline())
ans = [0] * 16
for i in range(n):
    a = [int(i) for i in f.readline().split()]
    ans_new = [-1000000000] * 16
    for k in range(len(a)):
        for j in range(16):
            ost = (ans[j] + a[k]) % 16
            if ans[j] + a[k] > ans_new[ost]:
                ans_new[ost] = ans[j] + a[k]
    ans = ans_new.copy()
maxim = 0
for i in range(16):
    if not(i in [10, 11, 12]):
        maxim = max(maxim, ans[i])
print(maxim)

Ответ: 10756 32719168

Ошибка.
Попробуйте повторить позже

Задача 59#30002Максимум баллов за задание: 2

Имеется набор данных, состоящий из пар натуральных чисел. Каждая пара чисел представляет собой баллы за ЕГЭ по информатике(1 число) и физике(2 число), соответственно 100 баллов максимум. Необходимо выбрать из каждой пары число такое что, если баллы по физике меньше 70, то взять из пары баллы по информатике, иначе взять баллы по физике. Необходимо найти сумму этих баллов. Программа должна напечатать одно число — сумму, соответствующую условиям задачи.

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

Пример входных данных:

5

100 50

30 49

88 79

90 90

79 48

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

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

Вложения к задаче

27Apoints.txt

27Bpoints.txt

Показать ответ и решение

f = open("1.txt")
n = int(f.readline())
ans = 0
for i in range(n):
    a, b = map(int, f.readline().split())
    if b < 70:
        ans += a
    else:
        ans += b
print(ans)

Ответ: 1432 297366

Ошибка.
Попробуйте повторить позже

Задача 60#36730Максимум баллов за задание: 2

Набор данных состоит из троек натуральных чисел. Необходимо распределить все числа на три группы, при этом в каждую группу должно попасть ровно одно число из каждой исходной тройки. В первой группе должна быть максимальная сумма всех чисел, во второй –– сумма «средних» по значению в тройке чисел, в третьей — минимальная сумма всех чисел. Выведите все полученные три суммы на экран.

Пример входных данных:

Первая строка входного файла содержит число N – общее количество троек в наборе. Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.

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

3

7 15 17

11 25 5

4 12 16

Для указанных данных искомые суммы равны 58 38 16, они соответствует такому распределению чисел по группам: (17, 25, 16), (15, 11, 12), (7, 5, 4).

Вложения к задаче

A4.txt

B4.txt

Показать ответ и решение

f = open(’A4.txt’)
n = int(f.readline())
maxim, average, minim = 0, 0, 0
for i in range(n):
    a, b, c = [int(x) for x in f.readline().split()]
    maxim += max(a, b, c)
    minim += min(a, b, c)
    average += a + b + c - min(a, b, c) - max(a, b, c)
print(maxim, average, minim)

Ответ: 16204 11412 5248 37317213 25001629 12700807