вентилятор
Удачи на экзаменах!

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



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


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


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





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



Задача (Демонстрационный вариант 2021)

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

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


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

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

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


6
1 3
5 12
6 9
5 4
3 3
1 1

Для указанных входных данных значением искомой суммы должно быть число 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 - это минимальная разница между числами в парах, следовательно, сумма будет максимально возможной.



Ответ:
127127399762080




Задача (Тройки чисел)

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


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

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


Пример входного файла:
3
1 2 3
8 12 4
6 9 7

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

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

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


Скачать файлы




Решение:

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


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 будет минимально возможная сумма при данных обстоятельствах.


Ответ:
185100918194




Задача(Тройки чисел, тренируем мозги)

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

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


Пример входного файла:
3
1 3 8
9 12 4
7 11 10

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


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


Скачать файлы




Решение:

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


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])

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


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

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





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


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


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


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

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


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


Ответ:
2996454694482





13-02-2023 в 11:00:57






Поддержать сайт:


Похожая статья:

Разбор демоверсии ЕГЭ по информатике 2022 (6-10 Задание)

Продолжаем разбор демонстрационного варианта ЕГЭ по информатике 2022...

Категория: Информатика  Подкатегория: ЕГЭ
Дата: 30-08-2021 в 18:51:18 0


Комментарии:

Во второй задаче перед кодом написаны слова: "Запрограммируем задачу на языке программирования Pascal ABC." Думаю надо исправить.
Александр Литвиненко 14-04-2023 в 08:14:07

Спасибо, исправил!
Калужский Александр 14-04-2023 в 09:19:23

Задача 27. Кратность 3. Неправильная. Вот тест. Сам код неправильный: if sm%3 != 0: -- Нам наоборот нужно, что бы сумма была кратна 3, то есть делилась без остатка на 3. print(sm) else: print(sm-delta) 5 16 5 15 5 14 6 15 5 13 5
Алекс 02-07-2023 в 19:09:33

В задаче же сказано, чтобы сумма НЕ делилась на 3. Если НЕ делится, тогда печатаем сумму, если делится, то нужно сместить на delta.
Калужский Александр 03-07-2023 в 10:27:25

День добрый! Я прошу прощения - действительно я был невнимателен, поторопился и не заметил "не". Видимо потому, что в других источниках задача под таким же номером 27 была именно на кратность 3. И именно её я решал последнее время. Ещё раз прошу прощения.
Алекс 03-07-2023 в 21:39:55

Во второй задаче некритичная ошибка в задании: сказано, чтобы в первую кидались четные, во вторую - нечетные; в примере наоборот.
Кто-то там 28-12-2023 в 17:17:07

В этой задаче название групп условно.
Калужский Александр 28-12-2023 в 17:31:12



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:




Нажимая кнопку Отправить, Вы соглашаетесь с политикой конфиденциальности сайта.