ЕГЭ по информатике - Задание 27 (Набираем форму)

Привет! Продолжаем набирать форму к ЕГЭ по информатике 2023.

Сегодня рассмотрим некоторые тренировочные задачи из 27 задания ЕГЭ по информатике.

Изучим приём, как решать некоторые типы задач из 27 задания.

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

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

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

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

Напишем программу на языке Python.

f=open('27_4a.txt')

n=int(f.readline())

sm = [0]*10

for i in range(n):
    a = f.readline().split()
    x, y = int(a[0]), int(a[1])

    sm2=[10**9]*10

    for j in range(10):

        r1=sm[j]+x
        r2=sm[j]+y

        sm2[r1%10] = min(r1, sm2[r1%10])
        sm2[r2%10] = min(r2, sm2[r2%10])

    sm=sm2

print(sm[6])

Чтобы проверить на что оканчивается положительное число, можно воспользоваться остатком от деления на 10.

Список sm - это минимальные суммы, для каждого остатка от деления на 10. Первая ячейка sm[0] - отвечает за минимальную сумму, которая может получится с остатком от деления на 10 равным нулю, вторая ячейка sm[1] - отвечает за минимальную сумму, которая может получится с остатком от деления на 10 равным единице и т.д.

Переменные x и y - числа очередной пары.

Для каждой пары заводим список sm2. Это минимальные суммы, которые могут получится с учётом конкретной пары для каждого остатка. Эти значения опираются на предыдущие значения sm. Приём похож на задание 18 из ЕГЭ по информатике. Там мы тоже опирались на два минимальных значения. Они уже минимальны, нет смысла перебирать все варианты, начиная с самого начала.

r1 - это прибавляем число x к сумме каждого остатка. r2 - это прибавляем число y к сумме каждого остатка.

Но числа r1 и r2 могут попасть не в ту же ячейку, которая была использована при получении этих чисел. Числа r1 и r2 могут обладать другими остатками при делении на 10.

В ячейку для конкретного остатка r1%10 мы выбираем минимальное значение из того, что там было, и нового претендента r1. Ведь r1 может "не победить" старое значение. Старые значения могли получится, когда мы это число x прибавляли к другим ячейкам списка sm. Нам нужно среди всех таких вариантов выбрать самое минимальное значение для ячейки конкретного остатка.

С переменной r2 делаем те же действия. Если у r2 будет такой же остаток (r2%10), как и r1, то всё равно в ячейку запишется самое маленькое значение.

В начале кладём в ячейки списка sm2 очень большое число (10**9), т.к. ищём минимальные значения.

Большие числа (10**9) могут перезаписаться в sm, если для какого-то остатка не удалось собрать сумму. Роли они не сыграют, т.к. проиграют всем по минимальности.

Таким образом, и число x, и число y пробуют провзаимодействовать с каждой из 10 ячеек списка sm. Два числа одновременно не смогут попасть в одну ячейку, и попадёт в эту ячейку самое маленькое значение.

Здесь используется именно новый список sm2 для каждой пары. Мы не можем и отталкиваться от списка sm и сразу обновлять этот список.

После окончания "ЦИКЛА с дестью остатками", список sm2 и будет содержать актуальную информацию для каждого остатка. В sm присваиваем sm2.

Шаг за шагом анализируем каждую пару. Раскладывать её "по спектру" на все 10 остатков. Списки sm и sm2 напоминают 17 задание из ЕГЭ по информатике, когда анализировали пары чисел.

Чтобы получить ответ, достаточно посмотреть в списке sm ячейку с индексом 6.

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

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

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

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

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

Напишем программу.

f=open('27_5a.txt')

n=int(f.readline())

sm = [0]*9

for i in range(n):
    a = f.readline().split()
    x, y, z = int(a[0]), int(a[1]), int(a[2])

    sm2=[0]*9

    for j in range(9):

        r1=sm[j]+x+y
        r2=sm[j]+x+z
        r3=sm[j]+y+z
        
        if i==0 or sm[j]!=0:
            sm2[r1%9] = max(r1, sm2[r1%9])
            sm2[r2%9] = max(r2, sm2[r2%9])
            sm2[r3%9] = max(r3, sm2[r3%9])

    sm=sm2

print(sm[0])

Решение похоже на программу из предыдущей задачи. В прошлой раз нас интересовали остатки от деления на 10. Здесь нужно собирать максимальные суммы с разными остатками от деления на 9. В нулевой ячейке списка sm будет сидеть максимальная сумма, которая делится на 9.

Теперь мы заставляем провзаимодействовать два числа из каждой тройки с предыдущими суммами. Перебираем все варианты. Вместо функции min(), уже пишем max().

В начале кладём в ячейки списка sm2 нули, т.к. ищем максимальные значения.

Здесь так же добавлено условие: мы обновляем список sm2, если в ячейках sm, на которые опираемся, не ноль (это касается всех троек, кроме первой). Когда анализируем первую тройку во всех ячейках списка sm как раз и должны быть нули.

Зачем мы это делаем ? Дело в том, что ноль в ячейке sm на втором и последующих шагах говорит о том, что мы не получили результата для данного остатка на предыдущем шаге, а значит, от него нельзя отталкиваться.

Это условие можно не писать, когда ищем минимальную сумму. Там после первого шага все нули перезапишутся большими числами из списка sm2. Они не будут порождать результаты, которые смогут соревноваться с реальными суммами по минимальности.

Заметим, что в этих задачах решение отличается от задач, когда нам нужно, чтобы сумма НЕ делилась на какое-то число. Как решать, когда сумма НЕ должна делится на какое-то число, можно почитать в этой статье.

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

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

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

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

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

Отработаем приём из 27 задания ЕГЭ по информатике.

f=open('27_6b.txt')

n=int(f.readline())

sm = [0]*6

for i in range(n):
    a = f.readline().split()
    x, y, z = int(a[0]), int(a[1]), int(a[2])

    sm2=[0]*6

    for j in range(6):

        r1=sm[j]+x
        r2=sm[j]+y
        r3=sm[j]+z
        
        if i==0 or sm[j]!=0:
            sm2[r1%6] = max(r1, sm2[r1%6])
            sm2[r2%6] = max(r2, sm2[r2%6])
            sm2[r3%6] = max(r3, sm2[r3%6])

    sm=sm2

print(sm[0])

Мы сегодня посмотрели интересный приём, как решать некоторые задачи из ЕГЭ по информатике 27-ого задания. Удачи!