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

Привет! Продолжаем готовится к ЕГЭ по информатике. Сегодня решим несколько задач на цепочки чисел.

Изучим интересные приёмы, как работать с цепочками чисел.

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

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

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

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

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

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

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

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

f=open('27_B.txt')
n=int(f.readline())

sum_ost=[-1]*43 #Массив, который содержит минимальные суммы для разных остатков
k=[0]*43 #Запоминаем, при каком i сохранили в sum_ost очередную сумму.

mx=0 #Максимальная сумма нужной цепочки в данный момент времени
ln=0 #Длина нужной цепочки

s=0 #Сумма цепочки с 1-го до i-ого элемента

sum_ost[0]=0 #Для остатка ноль ничего от s отнимать не нужно
k[0]=-1  #Для остатка ноль индекс равен -1, чтобы правильно считалась длина цепочки


for i in range(n):
    x=int(f.readline())
    s = s + x
    ost = s % 43

    if sum_ost[ost] != -1:
        
        if s-sum_ost[ost] >= mx:
            
            if s-sum_ost[ost] == mx:
                ln=min(ln, i-k[ost])
            else:
                mx = s - sum_ost[ost]
                ln = i - k[ost]
                

    if sum_ost[ost] == -1:
        sum_ost[ost] = s
        k[ost] = i
    
print(ln)

Переменная s - это сумма от 0-ого до текущего элемента i. На каждом шаге вычисляется остаток от деления s на 43. И записывается в массив sum_ost эта сумма s для каждого остатка.

Тогда кандидатом для ответа будет цепочка, которая получается, если от цепочки с суммой s "отрезать" цепочку с суммой из массива sum_ost, которая соответствует текущему остатку (переменная ost).

Ведь что такое остаток? Это лишние единицы, которые не смогли составить полноценное число 43. Если мы из цепочки удалим подцепочку, содержащую эти лишние единицы, то останется сумма, которая делится на 43.

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

В начале массив sum_ost инициализируется -1. Оно обозначает, что для данного остатка ещё не встречалась сумма s.

В процессе решения мы ищем среди кандидатов для ответа цепочку с максимальной суммой. Делаем это стандартным образом: кто больше, то и победил.

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

Для случая, когда остаток равен 0, устанавливаем сумму в массиве sum_ost равной нулю, потому что кандидатом на ответ будет цепочка от 0-ого до i-ого элемента. Это, можно сказать, исключительный случай. И чтобы правильно вычислялась длина цепочки, для случая, когда остаток равен нулю, индекс в массив k делаем равным -1. Стоит сказать, если бы присутствовали отрицательные числа,

На вход программе подается последовательность чисел и значение K. Рассматриваются все непрерывные подпоследовательности исходной последовательности, в которых количество отрицательных чисел, десятичная запись которых заканчивается на 3, кратно K. Программа должна вывести одно число – максимальную сумму такой последовательности.

Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 5000000) и значение K. Каждая из следующих N строк файлов содержит одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности по модулю не превышает 10⁹.

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

В этом наборе можно выбрать подпоследовательность (12, 7), которая имеет сумму 19 и не содержит ни одного отрицательных числа, оканчивающихся на 3. Ведь ноль тоже делится на 2. Ответ: 19.

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

Решим на языке Python.

def F(n):
    if n<0 and abs(n)%10==3:
        return True
    else:
        return False

f=open('27_7a.txt')
st = f.readline().split()
n, k = int(st[0]), int(st[1])

s=0
count=0
sum_ost_k = [10**10]*k

sum_ost_k[0] = 0

mx=-10**10

for i in range(n):
    x=int(f.readline())
    s=s+x
    if F(x):
        count=count+1

    ost=count%k

    if sum_ost_k[ost] != 10**10:
        mx=max(mx, s-sum_ost_k[ost])

    sum_ost_k[ost] = min(sum_ost_k[ost], s)

print(mx)

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

Здесь уже нужно запоминать минимальную сумму для каждого остатка, т.к. присутствуют отрицательные числа. Минимальные суммы запоминаем опять, т.к. от суммы s нужно "отрезать" цепочку с как можно меньшей суммой, тогда искомая сумма будет максимально большой.

В начале список sum_ost_k заполняем большими числами, т.к. хранить будем минимальные суммы.

Переменная count подсчитывает количество нужных чисел.

Если в ячейке списка sum_ost_k для конкретного остатка не начальное значение, то цепочка-кандидат для ответа готова, её проверяем на максимальность среди всех кандидатов.

Здесь опять работает тот же приём, мы "отрезаем" лишние единицы, и оставшаеся цепочка будет иметь количество нужных чисел, которое делится на k.

Дана последовательность натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество чисел, делящихся на 7, кратно K = 3. Найдите наибольшую сумму наибольшей такой подпоследовательности.

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

В этом наборе можно выбрать две непрерывные последовательности, содержащие по 3 числа, делящихся на 7 (21+14+4+28+6=73) и (14+4+28+6+35+8=95). Ответ: 95.

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

Используем изученные приёмы в предыдущих задачах.

def F(n):
    if n%7==0:
        return True
    else:
        return False

f=open('27_8b.txt')

n = int(f.readline())

k=3

s=0 # Сумма с 0-ого до i-ого элемента
count=0 # Количество нужных чисел в данный момент времени
sum_ost_k = [10**10]*k # Сумма элементов для остатков count%k при наименьшем количестве эл-тов

l=[0]*k # Сохраняем индексы для остатков count%k при наименьшем количестве эл-тов

sum_ost_k[0]=0 #Для остатка ноль, минимальное кол-во элементов равно нулю, значит, и сумма равна нулю
l[0]=-1 # Для остатка ноль устанавливаем индекс -1, чтобы правильно считалась длина

l_max=0 # Максимальная длина цепочки

mx=-10**10 # Максимальная сумма цепочки

for i in range(n):
    x=int(f.readline())
    s=s+x
    if F(x):
        count=count+1

    ost=count%k

    if sum_ost_k[ost] != 10**10:
        if i-l[ost] >= l_max:
            if i-l[ost] == l_max:
                mx=max(mx, s-sum_ost_k[ost])
            else:
                l_max=i-l[ost]
                mx=s-sum_ost_k[ost]

    if sum_ost_k[ost]==10**10:
        sum_ost_k[ost] = s
        l[ost] = i

print(mx)

В этой задачке будем подсчитывать количество чисел, которые делятся на 7, в переменную count. Для каждого остатка при делении этой переменной на 3, сохраняем сумму всех элементов (переменная s) и индекс i (чтобы можно было вычислить длину цепочки). Нас интересуют цепочки, как можно более длинные, поэтому для каждого остатка сохраняем вышеуказанные значения один раз (первый раз), чтобы сумму из списка sum_ost_k формировали как можно меньше элементов, и индекс i был как можно меньше.

Если элемент из списка sum_ost_k не равен первоначальному значению, то у нас есть цепочка-кандидат. В этой задаче нам нужно найти цепочку максимальной длины. Если длина цепочка-кандидата побеждает значение, которое считается максимальное в данный момент времени (l_max), то эта длина и заносится в l_max.

Если мы нашли цепочку равную по длине переменной l_max, то нужно брать именно с максимальной суммой.