Задание 27 из реального ЕГЭ по информатике 2021

Привет! Сегодня рассмотрим 27 задание из реального экзамена ЕГЭ по информатике 2021 (вариант Евгения Джобса).

Приведу собственное решение данной задачи.

Именно эта задача вызвала немало трудностей у выпускников и даже преподавателей.

Более эффективное решение данной задачи смотрите в ЕГЭ по информатике - Задание 27 (Цепочки чисел)

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

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 68000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10000. Программа должна вывести длину найденной последовательности.

Для делителя 50 при указанных входных данных значением искомой суммы должно быть число 100 (3 + 4 + 93 или 5 + 95). Следовательно, ответ на задачу — 2. В ответе укажите два числа: сначала значение искомой суммы для файла A, затем для файла B.

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

Напишем код на Python.

f=open('27_B.txt')

#Считываем количество чисел
n=int(f.readline())

sm=0
a=[]

#Записываем все числа в массив
#Cуммируем все элементы в sm
for i in range(1, n+1):
    x=int(f.readline())
    a.append(x)
    sm=sm+x

#Найдём количество "лишних" единиц.
lishnie_edinici = sm % 89

#Количество элементов, которые нужно отнять от всей суммы
count=0

################# 1 Эпизод #################
sm1 = 0
k1=0

for i in range(0, n):
    sm1=sm1+a[i]
    k1=k1+1
    if sm1%89==lishnie_edinici:
        break


################# 2 Эпизод #################
sm2=0
k2=0
for i in range(n-1, -1, -1):
    sm2=sm2+a[i]
    k2=k2+1
    if sm2%89==lishnie_edinici:
        break


################# 3 Эпизод #################
if sm1 < sm2:
    mn=sm1
    count=k1
else:
    mn=sm2
    count=k2

if sm1==sm2:
    count=max(k1, k2)


sm3_1=0

k3_1=0
k3_2=0

for i in range(0, n):
    if sm3_1 > mn: break
    sm3_1=sm3_1+a[i]
    k3_1=k3_1+1

    k3_2=0
    sm3_2=0

    for j in range(n-1, -1, -1):
        sm3_2=sm3_2+a[j]
        k3_2=k3_2+1
        if (sm3_1+sm3_2)%89==lishnie_edinici:
            if (sm3_1+sm3_2) < mn:
                mn=sm3_1+sm3_2
                count=k3_1+k3_2

            if sm3_1+sm3_2==mn:
                count=max(count, k3_1+k3_2)
            
            break


################# 4 Эпизод #################
sm4_1=0

k4_1=0
k4_2=0

for i in range(n-1, -1, -1):
    if sm4_1 > mn: break
    sm4_1=sm4_1+a[i]
    k4_1=k4_1+1

    k4_2=0
    sm4_2=0

    for j in range(0, n):
        sm4_2=sm4_2+a[j]
        k4_2=k4_2+1
        if (sm4_1+sm4_2)%89==lishnie_edinici:
            if (sm4_1+sm4_2) < mn:
                mn=sm4_1+sm4_2
                count=k4_1+k4_2

            if sm4_1+sm4_2==mn:
                count=max(count, k4_1+k4_2)

            break


#Распечатываем ответ
if lishnie_edinici==0:
    print(n)
else:
    print(n-count)

В начале мы суммируем все числа в переменную sm. Это и есть самая большая сумма, которую мы можем получить. Но наша сумма так же должна делится на число 89.

Узнаем, а что мешает нашей сумме делиться на 89. Т.е. узнаем, сколько "лишних" единиц в этой сумме. Для этого найдём остаток от деления суммы на 89 и занесём результат в переменную lishnie_edinici.

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

1 Эпизод. Смотрим, сколько нужно "снять" элементов сверху из нашей цепочки, чтобы сумма снятых элементов содержала в себе нужно количество "лишних" единиц.

Как только мы это найдём, в переменной sm1 будет сумма элементов, которые можно снять сверху, чтобы сумма основной цепочки делилась на 89. В переменной k1 будет количество этих элементов.

2 Эпизод. Всё аналогично первому эпизоду, только пробуем снять элементы снизу основной цепочки.

3 Эпизод. Нам нужно убрать элементы, у которых сумма будет как можно меньше, ведь в основной цепочке сумма должна быть, как можно больше! После двух эпизодов мы кладём наименьшую сумму убранных элементов в переменную mn.

Мы можем снимать элементы и сверху, и снизу одновременно. Берём сначала один элемент сверху, а остальные снизу. Как только в сумме убранных элементов накопились "лишние" единицы, проверяем, может этот результат и будет претендовать на ответ? Т.е. сравниваем сумму убранных элементов с переменной mn.

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

Если сумма убранных элементов меньше (и там есть нужное количество "лишних" единиц), то это значение перезаписывается в mn.

Затем, мы продолжаем третий эпизод до тех пор, пока сумма элементов, которые мы берём сверху, не превысит переменную mn. Ведь, если эта сумма превысит переменную mn, то мы точно не получим сумму убранных элементов меньшую, чем уже имеющийся результат.

4 Эпизод. Делаем аналогично 3 эпизоду, только верх и низ меняем местами.

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

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