Главная
Каталог задач
Каталог заданий по ЕГЭ - Информатика
Цепочки, выбор подпоследовательности, префиксные суммы

Тема 27. Программирование – оптимизация по времени и по памяти

27.03 Цепочки, выбор подпоследовательности, префиксные суммы

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела программирование – оптимизация по времени и по памяти

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#15875

Пояснение: под префиксной суммой подразумеваются суммы вида pref[0] = a[0], pref[1] = a[0] + a[1], ..., pref[n] = a[0] + a[1] + ... + a[n]

Подается число $n$ , затем $n$ чисел. Требуется посчитать всевозможные префиксные суммы и вывести их на экран в порядке возрастания через пробел. Для ответа выведите все суммы через пробел для $n = 10$ и чисел $7328$ , $6024$ , $5008$ , $3531$ , $343$ , $1658$ , $5228$ , $9997$ , $833$ , $3592$ .

Показать ответ и решение

n = int(input())
pref = [0]*n
pref[0] = int(input())
for i in range(1, n):
    pref[i] = pref[i-1] + int(input())
print(*pref)

Ответ: 7328 13352 18360 21891 22234 23892 29120 39117 39950 43542

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#15876

Подается число n затем n чисел. Требуется посчитать все возможные префиксные суммы, затем посчитать разности рядом стоящих префиксных сумм (разность от элемента с бОльшим индексом) и вывести их на экран в порядке возрастания через пробел. Для ответа выведите все суммы для n = 10 и чисел 7328, 6024, 5008, 3531, 343, 1658, 5228, 9997, 833, 3592.

Показать ответ и решение

n = int(input())
pref = [0] * n
pref[0] = int(input())
diffs = [0] * n
for i in range(1, n):
pref[i] = pref[i - 1] + int(input())
diffs[i - 1] = abs(pref[i] - pref[i - 1])
print(*sorted(diffs[:-1]))

Ответ: 343 833 1658 3531 3592 5008 5228 6024 9997

Ошибка.
Попробуйте повторить позже

Задача 3#15877

Подается число $n$ , затем $n$ чисел. Требуется найти длину (количество входящих элементов) наибольшей префиксной суммы, сумма которой кратна $100$ . Если таких префиксных сумм нет, выведите $− 1$ . Напишите ответ для $n = 10$ и чисел $7328$ , $6024$ , $5008$ , $3531$ , $343$ , $1658$ , $5228$ , $9997$ , $833$ , $3592$ .

Показать ответ и решение

    n = int(input())
    pref = [0]*n
    pref[0] = int(input())
    ans = -1
    for i in range(1, n):
        pref[i] = pref[i-1] + int(input())
        if pref[i] % 100 == 0:
            ans = i+1
    print(ans)

Ответ: -1

Ошибка.
Попробуйте повторить позже

Задача 4#15878

Подается число $n$ , затем $n$ натуральных чисел. Требуется найти минимальную ненулевую префиксную сумму. Если она четна, то выведите ее на экран, если нет, то прибавьте минимально возможную префиксную сумму (если минимальной префиксной суммой является первое число последовательности, то прибавить нужно вторую по величине префиксную сумму), чтобы итоговая подсумма была кратна $2$ . Если такой суммы нет — выведите $− 1$ . Напишите через пробел два числа: ответ для $n = 10$ и чисел $7328,6024,5008,3531,343,1658,5228,9997,833,3592$ , а также ответ для $n = 10$ и чисел $733,313,956,100,546,33,3213,325,6232,745$ .

Показать ответ и решение

    n = int(input())
    pref = [0]*n
    pref[0] = int(input())
    ans = 10000000
    for i in range(1, n):
        pref[i] = pref[i-1] + int(input())
        if pref[i] % 2 == 1:
            ans = min(ans, pref[i])
    if pref[0] % 2 == 0:
        print(pref[0])
    else:
        print(pref[0] + ans if ans != 10000000 else -1)

Ответ: 7328 3414

Ошибка.
Попробуйте повторить позже

Задача 5#15906

Пояснение: под префиксной суммой подразумеваются суммы вида pref[0] = a[0], pref[1] = a[0] + a[1], ..., pref[n] = a[0] + a[1] + ... + a[n]

Дан массив целых чисел $A = [2,− 3,4,− 5,6]$ . Напишите количество всевозможных префиксных сумм.

Показать ответ и решение

Решение 1 (ручками)

Количество префиксных сумм, которые можно получить в последовательности, равно количеству элементов в последовательности. Количество элементов в последовательности равно $5$ , поэтому количество префиксных сумм так же равно $5$ .

Решение 2 (программой)

# n - количество чисел в массиве А
n = int(input())
pref = [0]*1000
# создали массив "с запасом", потому что не знаем, сколько всего преф. сумм
pref[0] = int(input())
k = 1 #первая преф. сумма
for i in range(1, n):
    pref[i] = pref[i - 1] + int(input())
    k += 1
print(k)
# Можно заметить, что k == n, то есть число преф. сумм равно числу элементов в последовательности

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 6#15907

Пояснение: под префиксной суммой подразумеваются суммы вида pref[0] = a[0], pref[1] = a[0] + a[1], ..., pref[n] = a[0] + a[1] + ... + a[n]

Дан массив целых чисел $A = [9,− 1,3,6,− 7,8]$ . Найдите префиксную сумму $S3$ (индексация с 0).

Показать ответ и решение

Решение 1 (ручками)

Префиксная сумма $S3$ равна сумме всех элементов в массиве от индекса $0$ до индекса $3$ . Следовательно, префиксная сумма $S = 9+ (− 1)+ 3 + 6 = 17 3$ .

Решение 2 (программой)

# n - количество чисел в массиве A
n = int(input())
pref = [0]*n
pref[0] = int(input())
for i in range(1, n):
    pref[i] = pref[i-1] + int(input())
    if i == 3:
        print(pref[i])
        break

Ответ: 17

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#15908

Пояснение: под префиксной суммой подразумеваются суммы вида pref[0] = a[0], pref[1] = a[0] + a[1], ..., pref[n] = a[0] + a[1] + ... + a[n]

Дан массив целых чисел $A = [15,− 10,6,3,− 9,2]$ . Найдите максимальную префиксную сумму.

Показать ответ и решение

Решение 1 (ручками)

Найдём все префиксные суммы:

$S = 15 0$

$S1 = 5$

$S2 = 11$

$S3 = 14$

$S4 = 5$

$S5 = 7$

Следовательно, максимальная префиксная сумма равна $S0 = 15$ .

Решение 2 (программой)

# n - количество чисел в массиве A
n = int(input())
pref = [0]*n
pref[0] = int(input())
maxim = pref[0]
for i in range(1, n):
    pref[i] = pref[i-1] + int(input())
    if pref[i] > maxim:
        maxim = pref[i]
print(maxim)

Ответ: 15

Ошибка.
Попробуйте повторить позже

Задача 8#15910

Пояснение: под префиксной суммой подразумеваются суммы вида pref[0] = a[0], pref[1] = a[0] + a[1], ..., pref[n] = a[0] + a[1] + ... + a[n]

Дан массив целых чисел $A = [4,5,− 6,10,− 1,− 13]$ . Найдите разность максимальной и минимальной префиксных сумм.

Показать ответ и решение

Решение 1 (ручками)

Найдём все префиксные суммы:

$S = 4 0$

$S1 = 9$

$S2 = 3$

$S3 = 13$

$S4 = 12$

$S5 = − 1$

Максимальная префиксная сумма равна $S3 = 13$ , а минимальная $S5 = − 1$ . Поэтому $S3 − S5 = 13 − (− 1) = 14$ .

Решение 2 (программой)

# n - количество чисел в массиве A
n = int(input())
pref = [0]*n
pref[0] = int(input())
maxim = pref[0]
minim = pref[0]
for i in range(1, n):
    pref[i] = pref[i-1] + int(input())
    if pref[i] > maxim:
        maxim = pref[i]
    if pref[i] < minim:
        minim = pref[i]
print(maxim - minim)

Ответ: 14

Ошибка.
Попробуйте повторить позже

Задача 9#15911

Пояснение: под префиксной суммой подразумеваются суммы вида pref[0] = a[0], pref[1] = a[0] + a[1], ..., pref[n] = a[0] + a[1] + ... + a[n]

Дан массив целых чисел $A = [− 4,3,15,6,− 17,− 2]$ . Найдите разность префиксных сумм $S5$ и $S2$ (индексация с 0).

Показать ответ и решение

Решение 1 (ручками)

Разность префиксных сумм $S5$ и $S2$ равна сумме элементов последовательности с индексами $3,4$ и $5$ . Следовательно, $S − S = − 13 5 2$ .

Решение 2 (программой)

# n - количество чисел в массиве A
n = int(input())
pref = [0]*n
pref[0] = int(input())
s5, s2 = 0, 0
for i in range(1, n):
    pref[i] = pref[i-1] + int(input())
    if i == 2:
        s2 = pref[i]
    if i == 5:
        s5 = pref[i]
print(s5 - s2)

Ответ: -13

Ошибка.
Попробуйте повторить позже

Задача 10#24011

Задание выполняется с использованием прилагаемых файлов

Имеется набор данных, состоящий из положительных целых чисел $1$ или $2$ .

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

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

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке одно целое число $N (1 ≤ N ≤ 1000000)$ — количество чисел. Каждая из следующих $N$ строк содержит натуральное число $1$ или $2$ .

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

$5$

$1$

$2$

$1$

$2$

$1$

При таких исходных данных оптимально расположить числа следующим образом: $1 1 1 2 2$ или $2 1 2 1 1$ . Тогда префиксные суммы будут равны $1,2,3,5,7$ или $2,3,5,6,7$ соответственно. Ответ: $4$ .

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

Вложения к задаче

5_27A.txt

5_27B.txt

Показать ответ и решение

def is_prime(k):
    if k == 1:
        return False
    for j in range(2, int(k ** 0.5) + 1):
        if k % j == 0:
            return False
    return True


f = open(’Задание_27_B__loof.txt’)
n = int(f.readline())
ones, twos = 0, 0
for i in range(n):
    ones += (int(f.readline()) == 1)
twos = n - ones
# Если не существует единиц или двоек
if not ones or not twos:
    a = [1] * ones + [2] * twos
else:
    a = [2, 1] + [2] * (twos - 1) + [1] * (ones - 1)
# Простое число - нечетное. Первое простое - это 2. Далее 3, 5, 7, 11 и тд - все они нечетные.
# Но лучшего расположения мы добьемся при скачках сначала по нечетным, а потом все остальное.
ans = 0
s = 0
for i in range(len(a)):
    s += a[i]
    if is_prime(s):
        ans += 1
print(ans)

Ответ: 36 114163

Ошибка.
Попробуйте повторить позже

Задача 11#24066

Дан массив целых чисел $A = [2,− 3,4,− 5,6]$ . Напишите кол-во всевозможных префиксных сумм.

Показать ответ и решение

Количество префиксных сумм, которые можно получить в последовательности, на один больше количества элементов в последовательности (учитываем еще префиксную сумму 0). Количество элементов в последовательности равно $5$ , поэтому количество префиксных сумм равно $6$ .

Ответ: 6

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#24067

Дан массив целых чисел $A = [9,− 1,3,6,− 7,8]$ . Найдите префиксную сумму $S3$ .

Показать ответ и решение

Префиксная сумма $S3$ равна сумме всех элементов в массиве от индекса $0$ до индекса $3$ . Следовательно, префиксная сумма $S3 = 9+ (− 1)+ 3 + 6 = 17$ .

Ответ: 17

Ошибка.
Попробуйте повторить позже

Задача 13#24068

Дан массив целых чисел $A = [15,− 10,6,3,− 9,2]$ . Найдите максимальную префиксную сумму.

Показать ответ и решение

Найдём все префиксные суммы:

$S0 = 15$

$S = 5 1$

$S2 = 11$

$S3 = 14$

$S4 = 5$

$S5 = 7$

Следовательно, максимальная префиксная сумма равна $S0 = 15$ .

Ответ: 15

Ошибка.
Попробуйте повторить позже

Задача 14#24069

Дан массив целых чисел $A = [4,5,− 6,10,− 1,− 13]$ . Найдите разность максимальной и минимальной префиксных сумм.

Показать ответ и решение

Найдём все префиксные суммы:

$S0 = 4$

$S = 9 1$

$S2 = 3$

$S3 = 13$

$S4 = 12$

$S5 = − 1$

Максимальная префиксная сумма равна $S3 = 13$ , а минимальная $S5 = − 1$ . Поэтому $S3 − S5 = 13 − (− 1) = 14$ .

Ответ: 14

Ошибка.
Попробуйте повторить позже

Задача 15#32958

Пояснение: под префиксной суммой подразумеваются суммы вида pref[0] = a[0], pref[1] = a[0] + a[1], ..., pref[n] = a[0] + a[1] + ... + a[n]

Подается число $n$ , затем $n$ чисел. Требуется найти длину (количество входящих элементов) наибольшей префиксной суммы, сумма которой кратна $100$ . Если таких префиксных сумм нет, выведите $− 1$ . Напишите ответ для $n = 10$ и чисел $7392$ , $2345$ , $263$ , $8372$ , $372$ , $1836$ , $8326$ , $9736$ , $822$ , $6183$ .

Показать ответ и решение

n = int(input())
pref = [0]*n
pref[0] = int(input())
ans = -1
maxim = pref[0]
if pref[0] % 100 == 0:
    ans = 1
for i in range(1, n):
    pref[i] = pref[i-1] + int(input())
    if pref[i] % 100 == 0 and pref[i] > maxim:
        ans = i+1
        maxim = pref[i]
print(ans)

Ответ: 3

Ошибка.
Попробуйте повторить позже

Задача 16#36034

Подается число n затем n чисел. Требуется посчитать всевозможные префиксные суммы, затем посчитать разности рядом стоящих префиксных сумм (разность от элемента с бОльшим индексом) и вывести их на экран через пробел. Для ответа выведите все суммы для n $= 10$ и чисел $7328,6024,5008,3531,343,1658,5228,9997,833,3592$ .

Показать ответ и решение

n = int(input())
pref = [0] * n
pref[0] = int(input())
diffs = [0] * (n - 1) # всего n-1 пар подряд идущих чисел и n-1 разностей
for i in range(1, n):
    pref[i] = pref[i - 1] + int(input())  # Заполнение преф. сумм
    diffs[i - 1] = pref[i] - pref[i - 1]  # Разность ближних преф. сумм
print(diffs)

Ответ: 6024 5008 3531 343 1658 5228 9997 833 3592

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#36035

Подается число n затем n чисел. Требуется найти длину (из скольких элементов она состоит) наибольшей префиксной суммы, чья сумма кратна $100$ . Если таких префиксных сумм нет, выведите $− 1$ . Напишите ответ для n $= 10$ и чисел $2500,6024,5008,3531,343,1658,5228,9997,833,3592$ .

Показать ответ и решение

n = int(input())
pref = [0] * n
pref[0] = int(input())
ans = -1
if pref[0] % 100 == 0:
    ans = 1
for i in range(1, n):
    pref[i] = pref[i - 1] + int(input())
    if pref[i] % 100 == 0:
        ans = i + 1  # Индексация с 0
print(ans)

Ответ: 1

Предыдущий раздел

Следующий раздел