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

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

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

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

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

f = open(’27B__tckn.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(ln)

Ответ: 14 4995

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

Задача 22#30016Максимум баллов за задание: 2

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

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

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

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

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

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

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

f = open(’27B__tckq.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)

Ответ: 287 16

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

Задача 23#30020Максимум баллов за задание: 2

Дано натуральное число n, затем последовательность из $n$ целых чисел. Из нее необходимо выбрать несколько подряд идущих чисел так, чтобы каждое следующее число было больше предыдущего. Какую максимальную сумму может иметь подпоследовательность из выбранных чисел?

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

$|--| -1-- |2 | |--| |6-| -4-- |7 | |--| -9--$

Для указанных входных данных ответом должно быть число $20$ – максимальная сумма элементов возрастающей последовательности. В ответе укажите только целую часть числа.

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

1_domino.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):
    sum = a[i]
    for j in range(i + 1, n):
        if a[j] > a[j - 1]:
            sum += a[j]
        else:
            break
    ans = max(ans, sum)
print(ans)

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

f = open("27B.txt")
n = int(f.readline())
ans = 0
last = -1000000000
summa = 0

for i in range(n):
    cur = int(f.readline())
    if cur > last:
        summa += cur
        if summa > ans:
            ans = summa
    else:
        summa = cur
    last = cur

f.close()
print(ans)

Ответ: 22

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

Задача 24#30025Максимум баллов за задание: 2

Подается число $N$ , затем $N$ чисел, нужно найти максимальную сумму подряд идущих чисел, так что среди нет отрицательных.

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

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

1_27A.txt

1_27B.txt

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

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

f = open("1.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):
        if a[j] >= 0:
            sum += a[j]
        else:
            break
    ans = max(ans, sum)
print(ans)
f.close()

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

f = open("1.txt")
n = int(f.readline())
summa = 0
ans = 0
for i in range(n):
    x = int(f.readline())
    if x >= 0:
        summa += x
        ans = max(ans, summa)
    else:
        summa = 0
print(ans)
f.close()

Ответ: 42 9588

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

Задача 25#32959Максимум баллов за задание: 2

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

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

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

2_27A.txt

2_27B.txt

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

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

f = open(’27.txt’)
n = int(f.readline())
a = [int(f.readline()) for i in range(n)]
maxim = 0
for i in range(n):
    s = 0
    for j in range(i, n):
        s += a[j]
        if s % 3 == 0:
            maxim = max(maxim, s)
print(maxim)

Переборное решение будет обрабатывать более $90000$ чисел в файле слишком долго, поэтому напишем эффективное решение.

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

f = open(’2_27B__vxok.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)

Ответ: 393 303348

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

Задача 26#33878Максимум баллов за задание: 2

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

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

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

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

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

Задание_27-A__aht0.txt

Задание_27-B__aht7.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):
    cnt, sum = 0, 0
    for j in range(i, n):
        sum += a[j]
        if a[j] % 2 == 0:
            cnt += 1
        if cnt % 10 == 0:
            ans = max(ans, sum)
print(ans)

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

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

Ответ: 4779554 979258630

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

Задача 27#33879Максимум баллов за задание: 2

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

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

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

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

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

Задание_27-A__aht0.txt

Задание_27-B__aht7.txt

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

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

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

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

f = open("27A.txt")
a = [int(x) for x in f]
maxim = -10000000000000
for i in range(n):
    count_odd = 0
    s = 0
    for j in range(i, n):
        s += a[j]
        count_odd += (a[j] % 2 == 1)
        if count_odd % 10 == 0:
            maxim = max(maxim, s)
print(maxim)

Ответ: 4777208 979268310

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

Задача 28#36037Максимум баллов за задание: 2

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

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

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

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

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

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

Ответ: 1150 7503441880

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

Задача 29#36039Максимум баллов за задание: 2

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

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

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

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

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

f = open("27B.txt")
n = int(f.readline())
# Создаём 2 списка с минимальными суммами, дающими различные остатки от деления на 17 и 6 соответственно
# Нулевые суммы должны быть равны 0, чтобы ничего не вычитать в случае, когда S подходит целиком
pref_x = [10 ** 100] * 17
pref_x[0] = 0
pref_y = [10 ** 100] * 6
pref_y[0] = 0
s = mx = my = 0  # # Общая сумма / Макс. сумма для X / Макс. сумма для Y
for i in range(n):
    x = int(f.readline())
    s += x  # Прибавляем новое число из файла
    px = s % 17  # Остаток от деления на 17 текущей суммы
    py = s % 6  # Остаток от деления на 6 текущей суммы
    if s - pref_x[px] > mx:
        mx = s - pref_x[px]  # Вычитаем подходящий префикс и записываем макс. сумму X
    if s < pref_x[px]:
        pref_x[px] = s  # После всех проверок записываем текущую сумму в качестве префикса для X
    if s - pref_y[py] > my:
        my = s - pref_y[py]  # Вычитаем подходящий префикс и записываем макс. сумму Y
    if s < pref_y[py]:
        pref_y[py] = s  # После всех проверок записываем текущую сумму в качестве префикса для Y
print(mx, my, mx + my)  # Выводим X, Y, (X + Y)

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

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

Задача 30#36040Максимум баллов за задание: 2

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

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

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

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

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

f = open(’fileB__uc3k.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)

Ответ: 24 1499999

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

Задача 31#36042Максимум баллов за задание: 2

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

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

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

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

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

f = open(’fileB__uc3w.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)

Ответ: 16 16

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

Задача 32#37651Максимум баллов за задание: 2

Дано натуральное число $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

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

Задача 33#37652Максимум баллов за задание: 2

Дано натуральное число $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

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

Задача 34#37809Максимум баллов за задание: 2

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

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

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

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

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

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

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

    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 с таким же остатком при делении на 36 как и у s
    if s < tails[s % D]:
        tails[s % D] = s # перезаписываем сумму
        len_tails[s % D] = i + 1 # указываем длину данной последовательности
print(ln)

Ответ: 915 1897370

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

Задача 35#37810Максимум баллов за задание: 2

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

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

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

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

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

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

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

    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 с таким же остатком при делении на 92 как и у s
    if s < tails[s % D]:
        tails[s % D] = s # перезаписываем сумму
        len_tails[s % D] = i + 1 # указываем длину данной последовательности
print(ln)

Ответ: 918 1897358

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

Задача 36#37811Максимум баллов за задание: 2

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

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

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

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

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

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

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

Ответ: 4601050 1708866620

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

Задача 37#37812Максимум баллов за задание: 2

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

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

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

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

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

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

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

Ответ: 5033 900

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

Задача 38#37813Максимум баллов за задание: 2

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

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

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

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

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

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

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

Ответ: 3848977136 3240942998336680

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

Задача 39#37815Максимум баллов за задание: 2

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

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

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

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

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