Тема (старое) 27. Программирование

04 Пары/тройки чисел, выбрать из каждой, кратность

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела (старое) 27. программирование

Решаем задачи

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

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

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

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

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

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

27_9A.txt

27_9B.txt

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

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

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

    mr1 = mr[:]  # Копия списка разностей
    # Перебираем обе разности
    for d in d1, d2:
        # Составляем суммы нескольких разностей для получения различных остатков
        for j in range(k):
            if d + mr1[j] < mr[(d + mr1[j]) % k]:
                mr[(d + mr1[j]) % k] = d + mr1[j]
        # Если сама по себе разность меньше, то заменяем соответствующую разность
        if d < mr[d % k]:
            mr[d % k] = d

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

print(s)

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

f = open(’27_9B.txt’)
n = int(f.readline())
#массив для хранения минимальных сумм
mr = [10000000000] * 37
#начальная сумма для 0 равна 0
mr[0] = 0
for i in range(n):
    a, b, c = list(map(int, f.readline().split()))
    #временный массив для хранения минимальных сумм
    mr1 = [10000000000] * 37
    #проходимся по всем суммам в массиве mr
    for j in range(37):
        #обновляем минимальную сумму для каждого остатка от деления суммы на 37,
        #добавляя к текущей сумме каждое из чисел из тройки и сохраняя минимальность
        mr1[(mr[j] + a) % 37] = min(mr1[(mr[j] + a) % 37], mr[j] + a)
        mr1[(mr[j] + b) % 37] = min(mr1[(mr[j] + b) % 37], mr[j] + b)
        mr1[(mr[j] + c) % 37] = min(mr1[(mr[j] + c) % 37], mr[j] + c)
    #обновляем массив mr новыми минимальными суммами по модулю 37
    mr = mr1.copy()
#выводим минимальную сумму для остатка 0
print(mr[0])

Ответ: 49395 46611305

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

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

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

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

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

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

27_10A.txt

27_10B.txt

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

f = open(’27_10B.txt’)
n = int(f.readline())
s = 0
#массив для хранения минимальных разностей
mr = [1000000000500000000000]*41
for i in range(n):
    #пара чисел из файла
    a, b = map(int, f.readline().split())
    #добавляем к сумме минимальное число из пары
    s += min(a, b)
    d = abs(a-b) #разница между числами в паре
    mr1 = mr[:]   #копия массива минимальных разностей
    #проходимся по всем остаткам от деления на 41
    for j in range(41):
        #если сумма разницы и элемента массива меньше элемента в массиве,
        #обновляем элемент в массиве
        if d + mr1[j] < mr[(d+mr1[j]) % 41]:
            mr[(d+mr1[j]) % 41] = d + mr1[j]
    #если разница меньше элемента в массиве, обновляем элемент
    if d < mr[d % 41]:
        mr[d % 41] = d
#если сумма делится на 41, выводим ее
if s % 41 == 0:
    print(s)
else:# проходимся по всем элементам массива минимальных разностей
    for i in range(41):
    #если сумма с текущим элементом массива делится на 41,
    #выводим это значение
        if (s + mr[i]) % 41 == 0:
            print(s + mr[i])

Ответ: 483759 2596328198

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

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

По каналу связи передается последовательность целых чисел — показания прибора. В течение $N$ минут ( $N$ — натуральное число) прибор ежеминутно регистрирует значение напряжения (в условных единицах) в электрической сети и передает его на сервер.

Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее $K$ мин, а сумма этих трех чисел была максимально возможной. Запишите в ответе найденную сумму.

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

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

Запишите в ответе два числа: сначала значение искомой величины для файла А, затем — для файла В.

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

150

-150

-200

-300

При таких исходных данных искомая величина равна 170 — это сумма значений, зафиксированных на первой, третьей и шестой минутах измерений.

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

Переборное решение

Будем перебирать три числа в тройном цикле на расстоянии K друг от друга и обновлять максимальную сумму.

# Открываем файл
file = open("27_A_2024.txt")

# Считываем K и N
k = int(file.readline())
n = int(file.readline())

# Считываем показания прибора
data = list(map(int, file))

# Задаём максимальную сумму очень маленьким числом
max_sum = -(10**100)

# Перебираем первое, второе и третье число на расстоянии k друг от друга
for i1 in range(n):
    for i2 in range(i1 + k, n):
        for i3 in range(i2 + k, n):
            # Обновляем максимальную сумму
            max_sum = max(max_sum, data[i1] + data[i2] + data[i3])

# Выводим ответ
print(max_sum)

Динамическое решение

Для начала посмотрим на немного упрощённую задачу: будем искать пару чисел с максимальной суммой. Числа у нас будут лежать в списке $data$ .

Первая возможная пара чисел — это $data[0]$ и $data[k]$ . К $data[k+ 1]$ надо взять $max (data[0],data[1])$ , к $data[k + 2]$ — $max(data[0],data[1],data[2])$ и так далее. То есть для любого индекса $i$ , $i ≥ k$ , следует брать $max(data[0 : i− k+ 1])$ .

Теперь добавим третье число. К нему мы хотим добавлять пару с максимальной суммой на подходящем расстоянии. При переборе третьего числа по $i$ , $i ≥ 2 ⋅k$ , мы хотим к нему брать два числа с максимальной суммой из $data[0 : i− 2⋅k + 1]$ с достаточным расстоянием между собой. И мы ведь уже научились находить пару чисел с максимальной суммой на правильном расстоянии.

# Открываем файл
file = open("27_B_2024.txt")

# Считываем K и N
k = int(file.readline())
n = int(file.readline())

# Считываем показания прибора
data = list(map(int, file))

# Максимальное число в data[0 : i - k * 2 + 1]
one = 0
# Максимальная сумма пары среди data[0 : i - k + 1]
two_sum = 0
# Максимальная сумма тройки
three_sum = 0

# Перебираем с минимального индекса, с которого можно взять тройку
for i in range(k * 2, n):
    # Обновляем максимальное число за k * 2 до текущего
    one = max(one, data[i - k * 2])
    # Обновляем максимальную сумму пары за k до текущего
    two_sum = max(two_sum, one + data[i - k])
    # Обновляем максимальную сумму тройки
    three_sum = max(three_sum, two_sum + data[i])

# Выводим ответ
print(three_sum)

Ответ: 189536 17210