Решение 27 задачи 9 варианта с сайта Константина Полякова

Сейчас трудно найти новые задачи КЕГЭ по информатике 2021. Однако Константин Поляков придумал несколько интересных. И одну из таких я сегодня разберу

Условие задачи

Полный текст условия можно прочитать по ссылке на сайте автора: https://kpolyakov.spb.ru/school/ege/gen.php?action=viewVar&answers=on&varId=9

Короткое условие

Есть файл с данными, где на первой строчке указано количество последующих строк, а затем строки с парами чисел.

В каждой паре необходимо выбрать одно число так, чтобы сумма всех выбранных чисел была максимальной и в восьмеричной записи заканчивалась на 3.

Объяснение решения

Код на языке программирования Python: ссылка

Алгоритм такой:

1. Выбираем из пары самое большое число и добавляем его к сумме
   
2. "восьмеричная запись оканчивается на 3" означает, что остаток от деления суммы на 8 должен быть равен 3
   
3. Если она не три, то мы должны в какой-то из пар выбрать другое число так, чтобы теперь остаток был 3.
4. То есть мы должны на все варианты остатков (их будет 8) предусмотреть варианты компенсации.
   Например, если остаток 4, то мы должны его привести к 3, то есть взять другое число в паре, при том такое, что изменение суммы приведёт к изменению остатка от деления на 1. Для этого при построчном чтении файла мы будем запоминать разность между большим и меньшим элементом в паре. Мы создали список d для хранения 8-и минимальных разностей в паре на каждый остаток от деления на 8 и храним их по индексу равному остатку. В элементе d[4] хранится минимальная разность в паре, которая даёт остаток 4 при делении на 8.
5. После получения итоговой суммы мы сравниваем её остаток с 3.
   Если они равны то выводим сумму, если не равны то вычитаем из полученного остатка 3 и узнаем какой элемент из списка d нужно вычесть их итоговой суммы. Чтобы не допустить отрицательного индекса (хотя в Python можно) мы к остатку добавим 8, а потом от общего результата получим остаток от деления на 8.