ЕГЭ по информатике - Задание 27 (Делимость чисел)

Эта статья посвящена 27 заданию из ЕГЭ по информатике 2023.

В этой статье собраны некоторые задачи из 27 задания ЕГЭ по информатике, где нужно анализировать делимость чисел.

Приятного чтения!

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

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

Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.

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

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

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

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

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

Напишем программу на языке программирования Python для решения этого 27 задание из Демонстрационного варианта ЕГЭ по информатике.

f=open('27-B.txt')

n=int(f.readline())
delta=10001
sm=0

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

    if x>y:
        sm=sm+x
    else:
        sm=sm+y

    if (abs(x-y) < delta) and (abs(x-y) % 3 != 0):
        delta = abs(x-y)

if sm%3 != 0:
    print(sm)
else:
    print(sm-delta)

Найдём максимальную сумму в переменную sm, выбирая из каждой пары максимальное число. В переменной delta будем хранить минимальную разницу между числами в паре, которая НЕ делится на 3.

Если максимальная сумма делится на 3, то мы должны отнять переменную delta от максимальной суммы. Это означает, что мы заменили какое-то число суммы на другой элемент из той же пары. При этом новое значение точно не будет делиться на 3, ведь delta не делится на 3. Значение delta - это минимальная разница между числами в парах, следовательно, сумма будет максимально возможной.

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

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

Для указанных данных искомая сумма равна 11, она соответствует такому распределению чисел по группам: (2, 8, 7), (3, 12, 9), (1, 4, 6).

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

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

Источник задачи: https://inf-ege.sdamgia.ru/

Запрограммируем задачу на языке программирования Pascal ABC.

f=open('27-A.txt')

n=int(f.readline())

delta=10001

sm1=0
sm2=0
sm3=0

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

    mn = min(x, y, z)

    sm1 = sm1 + mn

    if x == mn:
        sm2 = sm2 + y
        sm3 = sm3 + z
    else:
        if y == mn:
            sm2 = sm2 + x
            sm3 = sm3 + z
        else:
            if z == mn:
                sm2 = sm2 + x
                sm3 = sm3 + y

    if x != mn and x - mn < delta and (x - mn)%2 != 0:
        delta = x-mn
    
    if y != mn and y - mn < delta and (y - mn)%2 != 0:
        delta = y-mn

    if z != mn and z - mn < delta and (z - mn)%2 != 0:
        delta = z-mn

    
if (sm2 + sm3)%2 != 0:
    print(sm1)
else:
    print(sm1+delta)

В переменную sm1 будем суммировать минимальные числа из каждой тройки. В переменные sm2 и sm3 распределяем оставшиеся числа из каждой тройки в произвольном порядке.

Переменная delta - это минимальная разница между наименьшим элементом и двумя оставшимися числами в тройке. Переменная delta - это наименьшая вышеуказанная разница среди всех троек, причём, она должна быть нечётной.

Если сумма переменных sm2 и sm3 будет нечётной, то условие задачи уже выполняется. Пример: 3 + 2 = 5 (т.е. сумма чётного числа и нечётного числа даёт нечётное число). Или 4 + 3 = 7. Здесь название первой, второй и третей группы весьма условны.

Если же сумма переменных sm2 и sm3 чётная, то нужно заменить одно число из sm1 числом из sm2 или sm3. После замены наша сумма sm1 увеличится на значение delta. Нам не обязательно понимать, из какой группы сделали замену, т.к. всё равно мы меняем число из той группы, где получилось значение delta.

Из-за того, что delta - это нечётное число, то чётность суммы той группы, откуда мы сделали замену, изменится. Если у нас были две чётные группы, то одна станет чётной, а другая станет нечётной. Тоже самое касается и другого случая, когда у нас были две нечётные группы, то после замены опять одна станет чётная, а другая нечётная группа. Таким образом, после замены, условие задачи будет выполнено, и в переменной sm1 будет минимально возможная сумма при данных обстоятельствах.

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

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

Для указанных данных искомая сумма равна 31, она соответствует такому распределению чисел по группам: (1, 9, 7), (3, 4, 10), (8, 12, 11).

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

Источник задачи: https://kpolyakov.spb.ru/

Распределим числа на три группы, как в прошлой задаче. В первую и во вторую группу числа распределяем из тройки случайно, а в третью берём максимальное число.

1) Случай, когда в первой и второй группе разная чётность.

В этом случае нет смысла менять числа из первой и второй группы. Если мы заменим два чётных числа, сумма первой и второй группы никак не поменяется. Если поменяем два числа с разной чётностью, то обе группы поменяют свою чётность. Где-то "лишняя единица" добавится, а где-то уберётся.

Когда меняем числа, имеем в виду, что речь идёт в пределах одной тройки.

Поэтому в этом случае нужно менять число из группы с максимальной суммой.

2) Случай, когда в первой и второй группе сумма чётная.

Здесь мы можем поменять два числа из первой и второй группы между собой, но эти два числа должны быть разной чётности (разность чисел по модули должна быть нечётной). Тогда из одной суммы уйдёт "лишняя единица", а в другую добавится, и тогда обе суммы станут нечётной.

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

Узнаём какие же будут суммы в первой и второй группе.

f=open('27a.txt')

n=int(f.readline())

sm1=0
sm2=0
sm3=0

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

    mx = max(x, y, z)

    sm3 = sm3 + mx

    if x == mx:
        sm2 = sm2 + y
        sm1 = sm1 + z
    else:
        if y == mx:
            sm2 = sm2 + x
            sm1 = sm1 + z
        else:
            if z == mx:
                sm2 = sm2 + x
                sm1 = sm1 + y

    
print(sm1%2, sm2%2)

Программа распечатала два нуля.

В файле a получается, что первая и вторая группа имеют чётные суммы. Теперь посмотрим, есть ли нечётная разница двух чисел в этих группах в пределах одной тройки.

f=open('27a.txt')

n=int(f.readline())

sm1=0
sm2=0
sm3=0

delta = 0

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

    mx = max(x, y, z)

    sm3 = sm3 + mx

    if x == mx:
        sm2 = sm2 + y
        sm1 = sm1 + z
        if abs(y-z)%2!=0:
            delta=abs(x-z)
    else:
        if y == mx:
            sm2 = sm2 + x
            sm1 = sm1 + z
            if abs(x-z)%2!=0:
                delta=abs(x-z)
        else:
            if z == mx:
                sm2 = sm2 + x
                sm1 = sm1 + y
                if abs(x-y)%2!=0:
                    delta=abs(x-y)
    
    
print(sm1%2, sm2%2, delta)

Получается, что переменная delta осталась равной нулю, следовательно, нет такой пары, где числа были бы разной чётности в пределах одной тройки.

Переменную delta ищем не обязательно минимальной.

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

Разница между заменяемыми числами должна быть минимальной и нечётной. Минимальной она должна быть из-за того, что мы хотим оставить сумму в третьей группе как можно большей.

f=open('27a.txt')

n=int(f.readline())

sm1=0
sm2=0
sm3=0

a1=[]
a2=[]

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

    mx = max(x, y, z)

    sm3 = sm3 + mx

    if x == mx:
        sm2 = sm2 + y
        sm1 = sm1 + z
        if (x-y)%2!=0:
            a1.append((x-y, i))
        if (x-z)%2!=0:
            a2.append((x-z, i))

    else:
        if y == mx:
            sm2 = sm2 + x
            sm1 = sm1 + z

            if (y-x)%2!=0:
                a1.append((y-x, i))
            if (y-z)%2!=0:
                a2.append((y-z, i))


        else:
            if z == mx:
                sm2 = sm2 + x
                sm1 = sm1 + y

                if (z-x)%2!=0:
                    a1.append((z-x, i))
                if (z-y)%2!=0:
                    a2.append((z-y, i))


a1.sort()
a2.sort()

    
print(sm3)
print(a1[:10])
print(a2[:10])

Получается следующий результат.

Первый список a1 отвечает за первую группу. Второй список a2 за вторую группу. В них кладём разницу между элементами из первой, второй группы и максимальным элементом тройки. При добавлении сохраняем ещё номер тройки, чтобы не заменить в итоге одно число для первой и второй группы.

После этого сортируем по первому числу списки a1 и a2, для того чтобы найти минимальную разницу для каждой группы.

Максимальная сумма до замен равна 3032. После замены элемента из первой группы наша сумма sm3 уменьшится на 17. После замены элемента из второй группы наше сумма sm3 уменьшится на 19. Мы видим, что производим замены из разных троек, поэтому ответ для файла a получается 3032 - 19 - 17 = 2996.

В третьей программе получается:

В файле b получается 454694534 - 27 - 25 = 454694482.

Второе число в списке гарантирует, что мы делаем замены из разных троек.