вентилятор
Хорошего настроения!

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



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


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


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





Задача (Количество подпоследовательностей)

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


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

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


Вам даны два входных файла (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.


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

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


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




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


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


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


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


Ответ:
38320384613548




Задача (Наложено два условия)

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


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

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


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


Скачать файл

Решение:

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


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


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

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





ЕГЭ по информатике демоверсия 2023 - задание 26 (двумерный список)

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


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


Ответ:
482847627266




Задача (Длина подпоследовательности не менее 7)

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


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

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


Вам даны два входных файла (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. Он играет роль буфера. В нём сохраняем 7 значений s, которые получаются на последних 7 шагах.


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


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


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


Ответ:
16519166644298







06-03-2023 в 17:30:07





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


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

ЕГЭ по информатике 2022 - Задание 15 (Простым языком)

Сегодняшний урок посвящён 15 заданию из ЕГЭ по информатике 2022. Темой...

Категория: Информатика  Подкатегория: ЕГЭ
Дата: 15-12-2021 в 17:51:30 13



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



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


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




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