Постановка задачи
Найти три числа из последовательности так, чтобы:
- Их сумма делилась на 102
- Сумма была максимально возможной
Математическая основа
Если сумма трех чисел делится на 102, то:
(a + b + c) ≡ 0 (mod 102)
Это равносильно:
(a mod 102 + b mod 102 + c mod 102) ≡ 0 (mod 102)
Алгоритм
Шаг 1: Подготовка данных
f = open("27.txt", "r")
N = int(f.readline())
a = [[] for _ in range(102)]
Создаем 102 списка - по одному для каждого возможного остатка от 0 до 101.
Шаг 2: Распределение чисел по остаткам
for i in range(N):
x = int(f.readline())
a[x % 102].append(x)
Каждое число попадает в список, соответствующий его остатку от деления на 102.
Пример:
- Число 205 → 205 % 102 = 1 → попадает в a[1]
- Число 408 → 408 % 102 = 0 → попадает в a[0]
Шаг 3: Выбор максимальных чисел для каждого остатка
for i in range(102):
a[i].sort(reverse=True)
a[i] = a[i][:3] # оставляем только 3 наибольших
Для каждого остатка берем только 3 наибольших числа. Это достаточно, потому что нам нужна максимальная сумма из трех чисел.
Почему 3 числа?
- Может понадобиться взять все три числа с одинаковым остатком
- В худшем случае нам нужно 2 числа с одним остатком и 1 с другим
Шаг 4: Перебор всех возможных комбинаций остатков
for i in range(102):
for j in range(i, 102):
k = (102 - (i + j) % 102) % 102
if k < j:
continue
Здесь мы перебираем все возможные тройки остатков (i, j, k), где i ≤ j ≤ k.
Как вычисляется k?
Мы ищем такой остаток k, чтобы:
i + j + k ≡ 0 (mod 102)
Следовательно
k ≡ - (i + j) (mod 102)
k ≡ (102 - (i + j) % 102) % 102
Зачем условие k < j?
Чтобы избежать дублирования комбинаций. Мы рассматриваем только упорядоченные тройки i ≤ j ≤ k.
Шаг 5: Обработка различных случаев
Случай 1: Все три остатка одинаковые (i = j = k)
if i == j == k:
if len(a[i]) >= 3:
mx = max(mx, a[i][0] + a[i][1] + a[i][2])
Если 3*i ≡ 0 (mod 102), то берем три наибольших числа с этим остатком.
Пример: i = 0, j = 0, k = 0
- 0 + 0 + 0 = 0 ≡ 0 (mod 102)
- Берем 3 наибольших числа из a[0]
Случай 2: Два остатка одинаковые (i = j)
elif i == j:
if len(a[i]) >= 2 and len(a[k]) >= 1:
mx = max(mx, a[i][0] + a[i][1] + a[k][0])
Берем два наибольших числа с остатком i и одно наибольшее с остатком k.
Пример: i = 1, j = 1, k = 100
- 1 + 1 + 100 = 102 ≡ 0 (mod 102)
Случай 3: Два других остатка одинаковые (j = k)
elif j == k:
if len(a[j]) >= 2 and len(a[i]) >= 1:
mx = max(mx, a[i][0] + a[j][0] + a[j][1])
Берем одно наибольшее число с остатком i и два наибольших с остатком j.
Пример: i = 1, j = 50, k = 50
- 1 + 50 + 50 = 101 ≠ 0 (mod 102) - такой комбинации не будет
- Правильный пример: i = 1, j = 50, k = 51 (но это другой случай)
Случай 4: Все остатки разные
else:
if len(a[i]) >= 1 and len(a[j]) >= 1 and len(a[k]) >= 1:
mx = max(mx, a[i][0] + a[j][0] + a[k][0])
Берем по одному наибольшему числу с каждого из трех остатков.
Пример: i = 10, j = 20, k = 72
- 10 + 20 + 72 = 102 ≡ 0 (mod 102)
Почему алгоритм работает корректно?
- Полнота: Мы перебираем все возможные комбинации остатков (i, j, k) такие, что i + j + k ≡ 0 (mod 102)
- Оптимальность: Для каждого набора остатков берем максимально возможные числа с этими остатками
- Эффективность: Храним только 3 числа для каждого остатка, что значительно сокращает перебор
- Отсутствие дубликатов: Условия i ≤ j ≤ k гарантируют, что каждая комбинация остатков рассматривается ровно один раз
Программа
f = open("27-B (1).txt", "r")
N = int(f.readline())
a = [[] for _ in range(102)]
for i in range(N):
x = int(f.readline())
a[x % 102].append(x)
# Для каждого остатка берем 3 максимальных числа
for i in range(102):
a[i].sort(reverse=True)
a[i] = a[i][:3] # оставляем только 3 наибольших
mx = 0
# Перебираем все возможные комбинации остатков
for i in range(102):
for j in range(i, 102):
k = (102 - (i + j) % 102) % 102
if k < j:
continue
if i == j == k:
if len(a[i]) >= 3:
mx = max(mx, a[i][0] + a[i][1] + a[i][2])
elif i == j:
if len(a[i]) >= 2 and len(a[k]) >= 1:
mx = max(mx, a[i][0] + a[i][1] + a[k][0])
elif j == k:
if len(a[j]) >= 2 and len(a[i]) >= 1:
mx = max(mx, a[i][0] + a[j][0] + a[j][1])
else:
if len(a[i]) >= 1 and len(a[j]) >= 1 and len(a[k]) >= 1:
mx = max(mx, a[i][0] + a[j][0] + a[k][0])
print(mx)
27 задание ЕГЭ Информатика
Задания для отработки
Задание 1
Дана последовательность натуральных чисел. Необходимо выбрать из последовательности четыре числа так, чтобы их сумма делилась на 75 и при этом была максимально возможной.
В ответе запишите найденную сумму.
(Пояснение: Усложнение за счет увеличения количества чисел с 3 до 4 и изменения делителя.)
Задание 2
Дана последовательность натуральных чисел. Необходимо выбрать из последовательности три числа так, чтобы их сумма делилась на 11, и при этом была минимально возможной (но положительной).
В ответе запишите найденную сумму.
(Пояснение: Изменена цель с поиска максимума на поиск минимума, используется простой делитель.)
Задание 3
Дана последовательность натуральных чисел. Необходимо выбрать из последовательности пять чисел так, чтобы их сумма при делении на 8 давала остаток 3 и при этом была максимально возможной.
В ответе запишите найденную сумму.
(Пояснение: Усложнение за счет условия на остаток, а не на полную делимость, и увеличения количества чисел.)
Задание 4
Дана последовательность натуральных чисел. Необходимо выбрать из последовательности три числа так, чтобы разность между наибольшим и наименьшим из них делилась на 15 и при этом была максимально возможной.
В ответе запишите найденную разность.
(Пояснение: Полностью изменен критерий — вместо суммы работает с разностью, что требует другого алгоритма решения.)
Задание 5
Дана последовательность натуральных чисел. Необходимо выбрать из последовательности четыре числа так, чтобы произведение двух наибольших из них делилось на 12 и при этом была максимальна сумма всех четырех чисел.
В ответе запишите найденную сумму.
(Пояснение: Комбинированное условие, где ограничение накладывается на часть выбранных чисел (произведение двух наибольших), а оптимизируется другая часть (общая сумма).)
Присоединяйтесь к нашему каналу в ДЗЕН «Учитель версии 4.0»!
Будем рады видеть вас среди наших подписчиков. На канале вас ждет эксклюзивный контент:
- Разборы сложных задач по Информатике.
- Советы по использованию Digital-инструментов в учебе.
- Актуальные новости из мира образовательных технологий.
Подписывайтесь, чтобы быть в курсе!
Учитель Информатики
Халтурина Надежда Вячеславовна