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

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

    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)

Ответ: 30013820946

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

Задача 3#15896

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

В качестве ответа укажите сумму ответа файла А и ответа файла B.

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

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

f = open(’fileB__d8lv__tio3.txt’)
n = int(f.readline())
mx = 0 # максимальная сумма подпоследовательности кратной 4
s = 0 # сумма всех чисел файла
ln = 0 # длина подпоследовательности
D = 4 # наш делитель
tails = [10**30]*D # префиксные суммы под определенным остатком при делении на 4
len_tails = [0]*D # длина префиксной суммы под определенным остатком при делении на 4
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if s % D == 0: # если сумма кратна 4
        mx = s # перезаписываем максимальную сумму
        ln = i + 1 # перезаписываем длину последовательности
    s1 = s - tails[s % D] # если сумма s не кратна 4,
    # то убавляем префиксную сумму с остатком при делении на 4 равным остатку при делении на 4 у суммы s
    # тогда мы получим новую сумму s1, которая кратна 4

    ln1 = (i+1) - len_tails[s % D] # вычисляем длину последовательности суммы s1
    # если сумма s1 больше максимума или сумма s1 равна максимуму и при этом её длина меньше
    if s1 > mx or (s1 == mx and ln1 < ln):
        mx = s1 # перезаписываем максимум
        ln = ln1 # перезаписываем длину
    # если сумма s меньше той, что записана в списке tails с таким же остатком при делении на 4 как и у s
    if s < tails[s % D]:
        tails[s % D] = s # перезаписываем сумму
        len_tails[s % D] = i + 1 # указываем длину данной последовательности
print(ln)

Ответ: 1500023

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

Задача 4#15897

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

В качестве ответа укажите сумму ответа файла А и ответа файла B.

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

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

f = open(’fileB__d8lv__tio7.txt’)
n = int(f.readline())
mx = 0 # максимальная сумма подпоследовательности кратной 16
s = 0 # сумма всех чисел файла
ln = 0 # длина подпоследовательности
D = 16 # наш делитель
tails = [10**30]*D # префиксные суммы под определенным остатком при делении на 16
len_tails = [0]*D # длина префиксной суммы под определенным остатком при делении на 16
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if s % D == 0: # если сумма кратна 16
        mx = s # перезаписываем максимальную сумму
        ln = i + 1 # перезаписываем длину последовательности
    s1 = s - tails[s % D] # если сумма s не кратна 16,
    # то убавляем префиксную сумму с остатком при делении на 16 равным остатку при делении на 16 у суммы s
    # тогда мы получим новую сумму s1, которая кратна 16

    ln1 = (i+1) - len_tails[s % D] # вычисляем длину последовательности суммы s1
    # если сумма s1 больше максимума или сумма s1 равна максимуму и при этом её длина меньше
    if s1 > mx or (s1 == mx and ln1 < ln):
        mx = s1 # перезаписываем максимум
        ln = ln1 # перезаписываем длину
    # если сумма s меньше той, что записана в списке tails с таким же остатком при делении на 16 как и у s
    if s < tails[s % D]:
        tails[s % D] = s # перезаписываем сумму
        len_tails[s % D] = i + 1 # указываем длину данной последовательности
print(mx-ln)

Ответ: 7501964121

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

Задача 5#15898

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

В качестве ответа укажите сумму ответа файла А и ответа файла B.

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

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

f = open(’fileB__d8lv__tio9.txt’)
n = int(f.readline())
mn = 10**30 # минимальная сумма подпоследовательности кратной 17
s = 0 # сумма всех чисел файла
ln = 0 # длина подпоследовательности
D = 17 # наш делитель
tails = [-10**30]*D # префиксные суммы под определенным остатком при делении на 17
len_tails = [0]*D # длина префиксной суммы под определенным остатком при делении на 17
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if s % D == 0 and s < mn: # если сумма кратна 17 и меньше минимума
        mn = s # перезаписываем минимальную сумму
        ln = i + 1 # перезаписываем длину последовательности
    s1 = s - tails[s % D] # если сумма s не кратна 17,
    # то убавляем префиксную сумму с остатком при делении на 17 равным остатку при делении на 17 у суммы s
    # тогда мы получим новую сумму s1, которая кратна 17
    ln1 = (i+1) - len_tails[s % D] # вычисляем длину последовательности суммы s1
    # если сумма s1 меньше минимума или сумма s1 равна минимуму и при этом её длина меньше
    if s1 < mn or (s1 == mn and ln1 < ln):
        mn = s1 # перезаписываем минимум
        ln = ln1 # перезаписываем длину
    # если сумма s больше той, что записана в списке tails с таким же остатком при делении на 17 как и у s
    if s > tails[s % D]:
        tails[s % D] = s # перезаписываем сумму
        len_tails[s % D] = i + 1 # указываем длину данной последовательности
print(mn-ln)

Ответ: 32

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

Задача 6#17881

Дано число $N$ и $N$ натуральных чисел. Каждое число находится в диапазоне от 0 до 10000. Напишите программу, которая находит максимальную сумму подряд идущих чисел, кратную 3.

В качестве ответа запишите результат выполнения программы на прикрепленном файле.

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

1.txt

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

f = open(’1__xbnt.txt’)
n = int(f.readline())
mx = 0 # максимальная сумма подпоследовательности кратной 3
s = 0 # сумма всех чисел файла
D = 3 # наш делитель
tails = [10**30]*D # префиксные суммы под определенным остатком при делении на 3
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if s % D == 0 and s > mx: # если сумма кратна 3 и больше максимума
        mx = s # перезаписываем максимальную сумму
    s1 = s - tails[s % D] # если сумма s не кратна 3,
    # то убавляем префиксную сумму с остатком при делении на 3 равным остатку при делении на 3 у суммы s
    # тогда мы получим новую сумму s1, которая кратна 3
    # если сумма s1 больше максимума
    mx = max(mx,s1) # перезаписываем максимум
    # если сумма s меньше той, что записана в списке tails с таким же остатком при делении на 3 как и у s
    tails[s % D] = min(s,tails[s % D]) # перезаписываем сумму
print(mx)

Ответ: 131274

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

Задача 7#24282

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

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

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

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

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

Решение 1 (неэффективное)

f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = -100000000
for i in range(n):
    sum = 0
    for j in range(i, n):
        sum += a[j]
        if sum % 3 == 0:
            ans = max(ans, sum)
print(ans)

Решение 2 (эффективное)

f = open(’File_B__t7rh.txt’)
n = int(f.readline())
mx = 0 # максимальная сумма подпоследовательности кратной 3
s = 0 # сумма всех чисел файла
D = 3 # наш делитель
tails = [10**30]*D # префиксные суммы под определенным остатком при делении на 3
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if s % D == 0 and s > mx: # если сумма кратна 3 и больше максимума
        mx = s # перезаписываем максимальную сумму
    s1 = s - tails[s % D] # если сумма s не кратна 3,
    # то убавляем префиксную сумму с остатком при делении на 3 равным остатку при делении на 3 у суммы s
    # тогда мы получим новую сумму s1, которая кратна 3
    # если сумма s1 больше максимума
    mx = max(mx,s1) # перезаписываем максимум
    # если сумма s меньше той, что записана в списке tails с таким же остатком при делении на 3 как и у s
    tails[s % D] = min(s,tails[s % D]) # перезаписываем сумму
print(mx)

Ответ: 33105 129564

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

Задача 8#24283

Дана последовательность целых чисел. Рассматриваются все её непрерывные подпоследовательности, в которых сумма кратна $K = 42$ . Найдите наименьшую сумму такой последовательности.

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

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

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

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

Решение 1 (неэффективное)

f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 100000000
for i in range(n):
    sum = 0
    for j in range(i, n):
        sum += a[j]
        if sum % 42 == 0:
            ans = min(ans, sum)
print(ans)

Решение 2 (эффективное)

f = open(’File_B__t7rk.txt’)
n = int(f.readline())
mn = 10**20 # минимальная сумма подпоследовательности кратной 42
s = 0 # сумма всех чисел файла
D = 42 # наш делитель
tails = [-10**30]*D # префиксные суммы под определенным остатком при делении на 42
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if s % D == 0 and s < mn: # если сумма кратна 42 и меньше минимума
        mn = s # перезаписываем минимальную сумму
    s1 = s - tails[s % D] # если сумма s не кратна 42,
    # то убавляем префиксную сумму с остатком при делении на 42 равным остатку при делении на 42 у суммы s
    # тогда мы получим новую сумму s1, которая кратна 42
    mn = min(mn,s1) # перезаписываем минимум
    # если сумма s больше той, что записана в списке tails с таким же остатком при делении на 42 как и у s
    tails[s % D] = max(s,tails[s % D]) # перезаписываем сумму
print(mn)

Ответ: -7098 -188538

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

Задача 9#24284

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

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

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

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

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

Решение 1 (неэффективное)

f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = -1000000000
for i in range(n):
    cnt, sum = 0, 0
    for j in range(i, n):
        sum += a[j]
        if a[j] > 0:
            cnt += 1
        if cnt % 2 == 0:
            ans = max(ans, sum)
print(ans)

Решение 2 (эффективное)

file = open("27B.txt")
n = int(file.readline())

s = 0
k = 0
mps = [0, 10000000]
ans = -1000000

for i in range(n):
    x = int(file.readline())
    s += x
    if x > 0:
        k += 1
    ans = max(ans, s - mps[k % 2])
    mps[k % 2] = min(mps[k % 2], s)
print(ans)

Ответ: 33229 129350

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

Задача 10#24285

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

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

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

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

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

Решение 1 (неэффективное)

f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 1000000000
for i in range(n):
    cnt, sum = 0, 0
    for j in range(i, n):
        sum += a[j]
        if a[j] < 0:
            cnt += 1
        if cnt % 2 == 0:
            ans = min(ans, sum)
print(ans)

Решение 2 (эффективное)

file = open("27B.txt")
n = int(file.readline())

s = 0
k = 0
mps = [0, -10000000]
ans = 1000000

for i in range(n):
    x = int(file.readline())
    s += x
    if x < 0:
        k += 1
    ans = min(ans, s - mps[k % 2])
    mps[k % 2] = max(mps[k % 2], s)
print(ans)

Ответ: -7248 -188466

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

Задача 11#24286

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

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

В ответ запишите два числа через пробел — сначала ответ для файла А, затем для файла Б.

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

Задание 27А.txt

Задание 27B.txt

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

Решение 1 (неэффективное)

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


f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
    cnt, sum = 0, 0
    for j in range(i, n):
        sum += a[j]
        if is_prime(a[j]):
            cnt += 1
        if cnt % 3 == 0:
            ans = max(ans, sum)
print(ans)

Решение 2 (эффективное)

def is_prime(n): # функция для проверки числа на простоту
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


f = open(’Задание_27B__1v50x.txt’)
n = int(f.readline())


mx = 0 # максимальная сумма подпоследовательности
s = 0 # сумма всех чисел файла
count = 0 # количество простых чисел всего файла
K = 3 # чему должно быть кратно количество простых чисел
tails = [10**30]*K # список, в котором под каждым индексом будут записаны минимальные префиксные суммы.
# определенный индекс обозначает остаток при делении на 3.
# Например, tails[2] - это префиксная сумма, у которой количество просто чисел даёт остаток 2 при делении на 3
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if is_prime(x): # если текущее число - простое
        count += 1 # увеличиваем счётчик
    if count % K == 0: # если счётчик кратен 3
        mx = max(mx,s) # перезаписываем максимум
    # если в сумме s количество простых чисел не кратно 3
    # тогда убавляем такую префиксную сумму,
    # после которой в полученной подпоследовательности количество простых чисел будет кратно 3
    s1 = s - tails[count % K]
    mx = max(mx,s1) # перезаписываем максимум
    # перезаписываем префиксные суммы под определенным остатком при делении на 3
    tails[count % K] = min(tails[count % K], s)
print(mx)

Ответ: 282613 38847371

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

Задача 12#26989

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

Дано число $N$ и последовательность из $N$ чисел.

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

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

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

Решение 1 (неэффективное)

f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
ans, maxim, end = 0, 0, 1000000000
for i in range(n):
    s = 0
    for j in range(i, n):
        s += a[j]
        if s % 15 == 0 and ((s > maxim) or (s == maxim and j < end)):
            maxim = s
            ans = j - i + 1
            end = j
print(ans)

Решение 2 (эффективное)

f = open(’27B__t72t.txt’)
n = int(f.readline())
mx = 0 # максимальная сумма подпоследовательности кратной 15
s = 0 # сумма всех чисел файла
ln = 0 # длина подпоследовательности
D = 15 # наш делитель
tails = [10**30]*D # префиксные суммы под определенным остатком при делении на 15
len_tails = [0]*D # длина префиксной суммы под определенным остатком при делении на 15
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if s % D == 0: # если сумма кратна 15
        mx = s # перезаписываем максимальную сумму
        ln = i + 1 # перезаписываем длину последовательности
    s1 = s - tails[s % D] # если сумма s не кратна 15,
    # то убавляем префиксную сумму с остатком при делении на 15 равным остатку при делении на 15 у суммы s
    # тогда мы получим новую сумму s1, которая кратна 15

    ln1 = (i+1) - len_tails[s % D] # вычисляем длину последовательности суммы s1
    # если сумма s1 больше максимума или сумма s1 равна максимуму и при этом её длина меньше
    if s1 > mx or (s1 == mx and ln1 < ln):
        mx = s1 # перезаписываем максимум
        ln = ln1 # перезаписываем длину
    # если сумма s меньше той, что записана в списке tails с таким же остатком при делении на 15 как и у s
    if s < tails[s % D]:
        tails[s % D] = s # перезаписываем сумму
        len_tails[s % D] = i + 1 # указываем длину данной последовательности
print(ln)

Ответ: 13 1499994

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

Задача 13#28823

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

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

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

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел $N (2 ≤ N ≤ 100000).$

Каждая из следующих $N$ строк файлов содержит одно натуральное число, не превышающее $10000.$

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

Программа должна вывести целое число — максимальную сумму.

Пример входных данных:

$7$

$23$

$13$

$4$

$11$

$6$

$19$

$8$

В этом наборе можно выбрать две непрерывные последовательности, содержащие по $3$ простых числа $23 +13 + 4+ 11+ 6 = 57$ и $13 +4 + 11+ 6+ 19 +8 = 61.$

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

Задание_27_A__qjv9.txt

Задание_27_B__qjvf.txt

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

Решение 1 (неэффективное)

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


f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
    cnt = 0
    sum = 0
    for j in range(i, n):
        sum += a[j]
        if is_prime(a[j]):
            cnt += 1
        if cnt % 3 == 0:
            ans = max(ans, sum)
print(ans)

Решение 2 (эффективное)

def is_prime(n): # функция для проверки числа на простоту
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


f = open(’Задание_27_B__qjvf__t6o1.txt’)
n = int(f.readline())


mx = 0 # максимальная сумма подпоследовательности
s = 0 # сумма всех чисел файла
count = 0 # количество простых чисел всего файла
K = 3 # чему должно быть кратно количество простых чисел
tails = [10**30]*K # список, в котором под каждым индексом будут записаны минимальные префиксные суммы.
# определенный индекс обозначает остаток при делении на 3.
# Например, tails[2] - это префиксная сумма, у которой количество просто чисел даёт остаток 2 при делении на 3
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if is_prime(x): # если текущее число - простое
        count += 1 # увеличиваем счётчик
    if count % K == 0: # если счётчик кратен 3
        mx = max(mx,s) # перезаписываем максимум
    # если в сумме s количество простых чисел не кратно 3
    # тогда убавляем такую префиксную сумму,
    # после которой в полученной подпоследовательности количество простых чисел будет кратно 3
    s1 = s - tails[count % K]
    mx = max(mx,s1) # перезаписываем максимум
    # перезаписываем префиксные суммы под определенным остатком при делении на 3
    tails[count % K] = min(tails[count % K], s)
print(mx)

Ответ: 108 499979766

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

Задача 14#29246

Дано число $n$ , затем последовательность из $n$ целых чисел. Рассматриваются все её непрерывные подпоследовательности. Найдите наибольшую сумму такой подпоследовательности.

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

27pref.txt

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

Решение 1 (неэффективное)

f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
    cur = 0
    for j in range(i, n):
        cur += a[j]
        ans = max(ans, cur)
print(ans)

Решение 2 (эффективное)

file = open(’27pref.txt’, ’rt’)
n = int(file.readline())

s = 0
mps = 0
ans = -10000000

for i in range(n):
    x = int(file.readline())
    s += x
    ans = max(ans, s - mps)
    mps = min(mps, s)
print(ans)

Ответ: 139294

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

Задача 15#29247

Дана последовательность $N$ целых чисел. Рассматриваются все её непрерывные подпоследовательности, в которых сумма кратна $k = 50$ . Найдите среди них подпоследовательность с максимальной суммой. Гарантируется, что хотя бы одна такая сумма в последовательности есть.

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

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

3_27A.txt

3_27B.txt

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

Решение 1 (неэффективное)

f = open("3.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
    sum = 0
    for j in range(i, n):
        sum += a[j]
        if sum % 50 == 0:
            ans = max(ans, sum)
print(ans)

Решение 2 (эффективное)

f = open(’3_27B__vxpf.txt’)
n = int(f.readline())
mx = 0 # максимальная сумма подпоследовательности кратной 50
s = 0 # сумма всех чисел файла
D = 50 # наш делитель
tails = [10**30]*D # префиксные суммы под определенным остатком при делении на 50
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if s % D == 0 and s > mx: # если сумма кратна 50 и больше максимума
        mx = s # перезаписываем максимальную сумму
    s1 = s - tails[s % D] # если сумма s не кратна 50,
    # то убавляем префиксную сумму с остатком при делении на 50 равным остатку при делении на 50 у суммы s
    # тогда мы получим новую сумму s1, которая кратна 50
    # если сумма s1 больше максимума
    mx = max(mx,s1) # перезаписываем максимум
    # если сумма s меньше той, что записана в списке tails с таким же остатком при делении на 50 как и у s
    tails[s % D] = min(s,tails[s % D]) # перезаписываем сумму
print(mx)

Ответ: 350 302300

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

Задача 16#29248

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

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

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

6_27A.txt

6_27B.txt

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

Решение 1 (неэффективное)

f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = -1000000000
for i in range(n):
    cnt = 0
    sum = 0
    for j in range(i, n):
        sum += a[j]
        if a[j] < 0:
            cnt += 1
        if cnt % 10 == 0:
            ans = max(ans, sum)
print(ans)

Решение 2 (эффективное)

file = open(’27B.txt’, ’rt’)
n = int(file.readline())

s = 0
k = 0
mps = [0] + [10000000 for _ in range(9)]
ans = -1000000

for i in range(n):
    x = int(file.readline())
    s += x
    if x < 0:
        k += 1
    ans = max(ans, s - mps[k % 10])
    mps[k % 10] = min(mps[k % 10], s)
print(ans)

Ответ: 394 243750

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

Задача 17#29435

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

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

Формат входных данных

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

Каждая из следующих $N$ строк файлов содержит одно натуральное число, не превышающее $10000$ .

Формат выходных данных

Программа должна вывести целое число — максимальную сумму.

Пример:

7

23

13

4

11

6

19

8

Ответом для примера будет: 61

Рассмотрим пример из условия.

В этом наборе можно выбрать две непрерывные последовательности, содержащие по $3$ простых числа $(23+ 13 +4 + 11+ 6 = 57)$ и $(13 + 4+ 11+ 6 +19 + 8 = 61)$ .

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

7_27A.txt

7_27B.txt

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

Решение 1 (неэффективное)

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


f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
    cnt = 0
    sum = 0
    for j in range(i, n):
        sum += a[j]
        if is_prime(a[j]):
            cnt += 1
        if cnt % 3 == 0:
            ans = max(ans, sum)
print(ans)

Решение 2 (эффективное)

def is_prime(n): # функция для проверки числа на простоту
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


f = open(’7_27B__w3rr.txt’)
n = int(f.readline())


mx = 0 # максимальная сумма подпоследовательности
s = 0 # сумма всех чисел файла
count = 0 # количество простых чисел всего файла
K = 3 # чему должно быть кратно количество простых чисел
tails = [10**30]*K # список, в котором под каждым индексом будут записаны минимальные префиксные суммы.
# определенный индекс обозначает остаток при делении на 3.
# Например, tails[2] - это префиксная сумма, у которой количество просто чисел даёт остаток 2 при делении на 3
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if is_prime(x): # если текущее число - простое
        count += 1 # увеличиваем счётчик
    if count % K == 0: # если счётчик кратен 3
        mx = max(mx,s) # перезаписываем максимум
    # если в сумме s количество простых чисел не кратно 3
    # тогда убавляем такую префиксную сумму,
    # после которой в полученной подпоследовательности количество простых чисел будет кратно 3
    s1 = s - tails[count % K]
    mx = max(mx,s1) # перезаписываем максимум
    # перезаписываем префиксные суммы под определенным остатком при делении на 3
    tails[count % K] = min(tails[count % K], s)
print(mx)

Ответ: 49903 6228487

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

Задача 18#30012

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

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

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

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

f = open(’27B__tckb.txt’)
n = int(f.readline())
mx = 0 # максимальная сумма подпоследовательности кратной 5
s = 0 # сумма всех чисел файла
D = 5 # наш делитель
tails = [10**30]*D # префиксные суммы под определенным остатком при делении на 5
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if s % D == 0: # если сумма кратна 5
        mx = s # перезаписываем максимальную сумму
    s1 = s - tails[s % D] # если сумма s не кратна 5,
    # то убавляем префиксную сумму с остатком при делении на 5 равным остатку при делении на 5 у суммы s
    # тогда мы получим новую сумму s1, которая кратна 5
    # если сумма s1 больше максимума
    mx = max(mx,s1) # перезаписываем максимум
    # если сумма s меньше той, что записана в списке tails с таким же остатком при делении на 5 как и у s
    tails[s % D] = min(s,tails[s % D]) # перезаписываем сумму
print(mx)

Ответ: 10710 24960005

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

Задача 19#30013

Последовательность натуральных чисел характеризуется числом X и Y, где X – максимальная сумма цепочки, кратная 17, а Y – максимальная сумма цепочки, кратная 6. Найдите сумму 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)

Ответ: 21924 49911775

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

Задача 20#30014

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

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

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