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

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

f = open(’27A.txt’)
n = int(f.readline())
maxs = [-10e16] * 11
ind = [-100] * 11
ind[0] = -1
maxs[0] = 0
summ, minim = 0, 10e10
for i in range(n):
    x = int(f.readline())
    summ += x
    ost = summ % 11
    if summ - maxs[ost] < minim:
        minim = summ - maxs[ost]
        dlina = i - ind[ost]
    elif summ - maxs[ost] == minim and i - ind[ost] <= dlina:
        dlina = i - ind[ost]
    if summ >= maxs[ost]:
        maxs[ost] = summ
        ind[ost] = i
print(minim - dlina)

Ответ: 21 10

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

Задача 5#37813

Последовательность натуральных чисел характеризуется числом $X$ , равным наибольшей длине цепочки, сумма чисел которой максимальна и делится на $751$ . Найдите результат произведения такой суммы на $X$ . Не гарантируется, что хотя бы одна такая сумма в последовательности есть. Если такой суммы нет, выведите $− 1$ . Цепочкой называется подпоследовательность символов, идущих подряд в исходной последовательности.

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

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

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

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

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

    f = open(’fileB.txt’)
    n = int(f.readline())
    mins = [10e16] * 751
    mins[0] = 0
    ind = [-100] * 751
    ind[0] = -1
    maxim, summ = 0, 0
    for i in range(n):
        x = int(f.readline())
        summ += x
        ost = summ % 751
        if summ - mins[ost] > maxim:
            maxim = summ - mins[ost]
            dlina = i - ind[ost]
        if summ < mins[ost]:
            mins[ost] = summ
            ind[ost] = i
     if maxim != 0:
         print(maxim * dlina)
     else:
         print(-1)

Ответ: 3848977136 3240942998336680

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

Задача 6#37812

Последовательность натуральных чисел характеризуется числом $X$ , равным длине цепочки, сумма чисел которой максимальна и делится на $24$ . Найдите результат целочисленного деления такой суммы на $X$ . Гарантируется, что хотя бы одна такая сумма в последовательности есть. Если подходящих цепочек несколько, то найдите длину той, что заканчивается раньше. Цепочкой называется подпоследовательность символов, идущих подряд в исходной последовательности.

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

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

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

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

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

    f = open(’fileA.txt’)
    n = int(f.readline())
    mins = [10e16] * 24
    mins[0] = 0
    ind = [-100] * 24
    ind[0] = -1
    maxim, summ = 0, 0
    for i in range(n):
        x = int(f.readline())
        summ += x
        ost = summ % 24
        if summ - mins[ost] > maxim:
            maxim = summ - mins[ost]
            dlina = i - ind[ost]
        if summ < mins[ost]:
            mins[ost] = summ
            ind[ost] = i
    print(maxim // dlina)

Ответ: 5033 900

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

Задача 7#37811

Последовательность натуральных чисел характеризуется числом $X$ , равным длине цепочки, сумма чисел которой максимальна и делится на $54$ . Найдите такую сумму и число $X$ , деленное на $3$ нацело. В ответе укажите их сумму. Гарантируется, что хотя бы одна такая сумма в последовательности есть. Если подходящих цепочек несколько, то найдите длину той, что заканчивается раньше. Цепочкой называется подпоследовательность символов, идущих подряд в исходной последовательности.

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

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

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

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

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

    f = open(’fileA.txt’)
    n = int(f.readline())
    mins = [10e16] * 54
    mins[0] = 0
    ind = [-100] * 54
    ind[0] = -1
    maxim, summ = 0, 0
    for i in range(n):
        x = int(f.readline())
        summ += x
        ost = summ % 54
        if summ - mins[ost] > maxim:
            maxim = summ - mins[ost]
            dlina = i - ind[ost]
        if summ < mins[ost]:
            mins[ost] = summ
            ind[ost] = i
    print(maxim + dlina // 3)

Ответ: 4601050 1708866620

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

Задача 8#37810

Последовательность натуральных чисел характеризуется числом $X$ , равным длине цепочки, сумма чисел которой максимальна и делится на 92. Найдите $X$ . Гарантируется, что хотя бы одна такая сумма в последовательности есть. Если подходящих цепочек несколько, то найдите длину той, что заканчивается раньше. Цепочкой называется подпоследовательность символов, идущих подряд в исходной последовательности.

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

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

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

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

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

    f = open(’fileA.txt’)
    n = int(f.readline())
    mins = [10e16] * 92
    mins[0] = 0
    ind = [-100] * 92
    ind[0] = -1
    maxim, summ = 0, 0
    for i in range(n):
        x = int(f.readline())
        summ += x
        ost = summ % 92
        if summ - mins[ost] > maxim:
            maxim = summ - mins[ost]
            dlina = i - ind[ost]
        if summ < mins[ost]:
            mins[ost] = summ
            ind[ost] = i
    print(dlina)

Ответ: 918 1897358

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

Задача 9#37809

Последовательность натуральных чисел характеризуется числом $X$ , равным длине цепочки, сумма чисел которой максимальна и делится на $36$ . Найдите $X$ . Гарантируется, что хотя бы одна такая сумма в последовательности есть. Если подходящих цепочек несколько, то найдите длину той, что заканчивается раньше. Цепочкой называется подпоследовательность элементов, идущих подряд в исходной последовательности.

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

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

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

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

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

    f = open(’fileA.txt’)
    n = int(f.readline())
    mins = [10e16] * 36
    mins[0] = 0
    ind = [-100] * 36
    ind[0] = -1
    maxim, summ = 0, 0
    for i in range(n):
        x = int(f.readline())
        summ += x
        ost = summ % 36
        if summ - mins[ost] > maxim:
            maxim = summ - mins[ost]
            dlina = i - ind[ost]
        if summ < mins[ost]:
            mins[ost] = summ
            ind[ost] = i
    print(dlina)

Ответ: 915 1897370

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

Задача 10#37652

Дано натуральное число $N$ , затем дана последовательность $N$ целых чисел. Необходимо найти максимально возможную сумму её непрерывной подпоследовательности, в которой количество положительных нечётных элементов кратно $50$ .

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

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

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

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

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

Неэффективное решение

f = open("7A.txt")
n = int(f.readline())
ans = 0
a = []
for i in range(n):
    a.append(int(f.readline()))

for i in range(n):
    s = 0
    counter = 0  # счетчик полож. нечет. эл-ов
    for j in range(i, n):
        s += a[j]
        if (a[j] > 0) and (a[j] % 2 != 0):
            counter += 1
        if counter % 50 == 0:
            ans = max(ans, s)
print(ans)

Эффективное решение

f = open("7B.txt")
n = int(f.readline())
minpref = [0] + [100000000] * 49  # преф суммы по кол-ву полож.неч. чисел
ans, counter, s = 0, 0, 0
for i in range(n):
    x = int(f.readline())
    s += x
    if x > 0 and x % 2 != 0:
        counter += 1
    ans = max(ans, s - minpref[counter % 50])
    minpref[counter % 50] = min(s, minpref[counter % 50])
print(ans)

Ответ: 62164 25057

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

Задача 11#37651

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

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

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

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

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

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

Неэффективное решение

f = open("6A.txt")
n = int(f.readline())
a = []
ans = 0
for i in range(n):
    a.append(int(f.readline()))

for i in range(n):
    s = 0
    for j in range(i, n):
        s += a[j]
        if s % 1000 == 0:
            ans += 1
print(ans)

Эффективное решение

f = open("6B.txt")
n = int(f.readline())
prefs = [0] * 1000  # кол-во преф. сумм по остаткам
ans, s = 0, 0
for i in range(n):
    x = int(f.readline())
    s += x
    if s % 1000 == 0:
        ans += 1
    ans += prefs[s % 1000]
    prefs[s % 1000] += 1
print(ans)

Ответ: 448 1800131825

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

Задача 12#36042

Последовательность натуральных чисел характеризуется числом $X$ , равным длине цепочки, сумма чисел которой минимальна и делится на $17$ . Найдите разность минимальной суммы и $X$ . Гарантируется, что хотя бы одна такая сумма в последовательности есть. Если существует несколько подпоследовательностей с равной минимальной суммой, нужно выбрать последовательность, которая заканчивается раньше т.е. последний элемент имеет меньший индекс. Цепочкой называется подпоследовательность символов, идущих подряд в исходной последовательности.

В файле первым числом идет количество чисел, а далее сами числа.

В качестве ответа укажите через пробел ответ для файла А и ответ для файла B.

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

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

f = open(’fileA.txt’)
n = int(f.readline())
maxs = [-10e16] * 17
ind = [-100] * 17
ind[0] = -1
maxs[0] = 0
dlina = 0
summ, minim = 0, 10e10  # Мин. сумму не нашли - обозначаем большим числом
for i in range(n):
    x = int(f.readline())
    summ += x
    ost = summ % 17
    if summ - maxs[ost] < minim:
        minim = summ - maxs[ost]
        dlina = i - ind[ost]
    if summ > maxs[ost]:
        maxs[ost] = summ
        ind[ost] = i
print(minim - dlina)

Ответ: 16 16

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

Задача 13#36040

Последовательность натуральных чисел характеризуется числом $X$ , равным длине цепочки, сумма чисел которой максимальна и делится на $4$ . Найдите $X$ . Гарантируется, что хотя бы одна такая сумма в последовательности есть. Если существует несколько подпоследовательностей с равной максимальной суммой, нужно выбрать последовательность, которая заканчивается раньше т.е. последний элемент имеет меньший индекс. Цепочкой называется подпоследовательность символов, идущих подряд в исходной последовательности.

В файле первым числом идет количество чисел, а далее сами числа.

В качестве ответа укажите через пробел ответ для файла А и ответ для файла B.

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

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

n = int(f.readline())
mins = [10e16] * 4
mins[0] = 0
ind = [-100] * 4  # Массив индексов по остатку
ind[0] = -1  # i = 0; 0 - (-1) = 1.
maxim, summ = 0, 0
dlina = -1
for i in range(n):
    x = int(f.readline())
    summ += x
    ost = summ % 4
    if summ - mins[ost] > maxim:
        maxim = summ - mins[ost]
        dlina = i - ind[ost]  # Сумма подходит - обновляем
    if summ < mins[ost]:
        mins[ost] = summ
        ind[ost] = i  # Сохраняем индекс наим. суммы по кратности
print(dlina)

Ответ: 24 1499999

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

Задача 14#36039

Последовательность натуральных чисел характеризуется числом $X$ и $Y$ , где $X$ —- максимальная сумма цепочки, кратная $17$ , а $Y$ –– максимальная сумма цепочки, кратная $6$ . Найдите $X,Y$ , сумму $X$ и $Y$ , разделяя их пробелом. Гарантируется, что обе суммы в последовательности есть. Цепочкой называется подпоследовательность символов, идущих подряд в исходной последовательности.

В файле первым числом идет количество чисел, а далее сами числа.

В качестве ответа укажите через пробел ответ для файла А и ответ для файла B.

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

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

f = open(’fileA.txt’)
n = int(f.readline())
minsx = [10e16] * 17
minsx[0] = 0
minsy = [10e16] * 6
minsy[0] = 0
summ, maximx, maximy = 0, 0, 0
for i in range(n):
    x = int(f.readline())
    summ += x
    ostx = summ % 17
    osty = summ % 6
    if summ - minsx[ostx] > maximx:
        maximx = summ - minsx[ostx]
    if summ < minsx[ostx]:
        minsx[ostx] = summ
    if summ - minsy[osty] > maximy:
        maximy = summ - minsy[osty]
    if summ < minsy[osty]:
        minsy[osty] = summ
print(maximx, maximy, maximx + maximy)

Ответ: 918 1314 2232 7503445329 7503462912 15006908241

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

Задача 15#36037

Последовательность натуральных чисел характеризуется числом $X$ , равным максимальной сумме цепочки, кратной $10$ . Найдите такую сумму. Гарантируется, что хотя бы одна такая сумма в последовательности есть. Цепочкой называется подпоследовательность символов, идущих подряд в исходной последовательности.

В файле первым числом идет количество чисел, а далее сами числа.

В качестве ответа укажите через пробел ответ для файла А и ответ для файла B.

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