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

Привет! Сегодня поговорим, как искать количество подпоследовательностей чисел в 27 задании.

Мы уже рассматривали, как искать сумму и длину цепочек чисел, удовлетворяющих определённым условиям.

Приступим к примерным задачам из 27 задания ЕГЭ по информатике на количество подпоследовательностей чисел.

Дана последовательность натуральных чисел. Необходимо определить количество её непрерывных подпоследовательностей, сумма элементов которых кратна 13.

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

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

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

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

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

k_ost=[0]*13
k_ost[0]=1

k=0
s=0

for i in range(n):
    x=int(f.readline())
    s = s + x
    ost = s % 13
    k=k+k_ost[ost]
    k_ost[ost]=k_ost[ost]+1
    
print(k)

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

Когда мы первый раз получили некоторый остаток s%13, мы ещё не имеем такую цепочку чисел, сумма которой делится на 13. Поэтому и количество цепочек не меняется. Когда второй раз получили этот же конкретный остаток, то получается уже одна подпоследовательность чисел, которую нужно засчитать (об этом мы подробно говорили в этой статье).

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

Список k_ost хранит в себе количество значений s для всех остатков от деления на 13.

Таким образом, при получение очередного остатка ost, мы прибавляем к счётчику k то значение k_ost[ost], которое было уже сформировано до этого. И прибавляем в ячейку k_ost[ost] единицу, чтобы учесть это значение s с конкретным остатком ost для последующих подсчётов.

Для остатка ноль в список k_ost кладём в начале 1, т.к. при получении первого значение s, где s%13==0, мы получаем уже одну нужную цепочку автоматически.

Дана последовательность натуральных чисел. Необходимо определить количество её непрерывных подпоследовательностей, сумма элементов которых кратна 21, а количество чисел, оканчивающихся на 9, кратно 5.

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

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

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

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

Здесь на цепочки чисел налагается два условия: с одной стороны сумма элементов должна быть кратна 21, а с другой, количество чисел, оканчивающихся на 9, должно быть кратно 5.

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

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

Как и в прошлой задаче будем хранить в этом списке количество значений s, которое уже встречалось до этого момента, для параметров s%21 и count%5, где s, как всегда, сумма от 0-ого до i-ого элемента, а count - это количество чисел, оканчивающихся на 9, на данный момент времени.

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

# Заводим двумерный список 21 на 5
k_ost=[0]*21
for i in range(21):
    k_ost[i]=[0]*5

k_ost[0][0]=1

k=0
s=0
count=0

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

    if x%10==9: count=count+1
    
    k=k+k_ost[s % 21][count % 5]
    k_ost[s % 21][count % 5]=k_ost[s % 21][count % 5]+1
    
print(k)

Для начального значения, когда count%5=0 и s%21=0, кладём в список k_ost единицу, аналогично предыдущей задаче.

С помощью ввода двумерного массива, можно аналогично найти цепочку и с максимальной суммой.

Дана последовательность натуральных чисел. Рассматриваются все её непрерывные подпоследовательности длиной не менее 7 чисел, такие что сумма чисел каждой из них кратна 30. Найдите количество таких подпоследовательностей.

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

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

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

f=open('27_11b.txt')
n=int(f.readline())
q=[]
s=0
for i in range(6):
    x=int(f.readline())
    s=s+x
    q.append(s)

k_ost = [0]*30
k_ost[0] = 1
k=0

for i in range(n-6):
    x=int(f.readline())
    s=s+x

    k=k+k_ost[s%30]
    
    k_ost[q[0]%30] = k_ost[q[0]%30] + 1

    q.pop(0)
    q.append(s)

print(k)

Как мы говорили, чтобы найти количество подпоследовательностей, нужно для каждого остатка s%30 знать, а сколько таких значений s с этим же остатком было до этого.

Но здесь нельзя подсчитывать цепочки, которые по длине меньше 7. Т.е. нельзя брать во внимание те значения s, которые получились совсем недавно, на предыдущих 6 шагах.

На каждом шаге мы обрабатываем ячейку q[0], добавляя в список k_ost единицу для соответствующего остатка, как бы с задержкой в 6 шагов.

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

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