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

f = open(’27B_09_1.txt’)
n = int(f.readline())
a = [int(i) for i in f]

# Чему кратны числа
k = 18
# Чему кратно количество чисел
d = 7

r = 0  # Количество встреченных чисел кратных k
# Для сумм с нулевым количеством нужных чисел изначально самая маленькая - начальная
tails = [0] + [10 ** 10] * (d - 1)
mx = 0
s = 0

for i in range(n):
    x = a[i]
    # Увеличиваем общую сумму
    s += x

    # Если нашли нужное число - увеличиваем на 1 их количество
    # перезаписываем хвост, выбирая наименьший для этого
    # количества кратных k чисел
    if x % k == 0:
        r += 1
    if s < tails[r % d]:
        tails[r % d] = s

    # Находим максимальную сумму, отсекая хвост с количеством кратных k чисел
    # равным остатку от деления на необходимое количество d
    if s - tails[r % d] > mx:
        mx = s - tails[r % d]

print(mx)

f = open(’27B_09_2.txt’)
n = int(f.readline())
a = [int(i) for i in f]

# На что оканчиваются числа
k = 31
# Чему кратно количество чисел
d = 12


r = 0  # Количество встреченных чисел оканчивающихся k
# Для сумм с нулевым количеством нужных чисел изначально самая маленькая - начальная
tails = [0] + [10 ** 10] * (d - 1)
mx = 0
s = 0

for i in range(n):
    x = a[i]
    # Увеличиваем общую сумму
    s += x

    # Если нашли нужное число - увеличиваем на 1 их количество
    # перезаписываем хвост, выбирая наименьший для этого
    # количества оканчивающихся k чисел
    if (abs(x) % 100) == k:
        r += 1
    if s < tails[r % d]:
        tails[r % d] = s

    # Находим максимальную сумму, отсекая хвост с количеством оканчивающихся k чисел
    # равным остатку от деления на необходимое количество d
    if s - tails[r % d] > mx:
        mx = s - tails[r % d]

print(mx)

f = open(’27B_09_3.txt’)
n = int(f.readline())
a = [int(i) for i in f]

# Общая сумма
s = 0
mx = 0
# Минимальный префикс
mn = 0

for i in range(n):
    x = a[i]
    # Увеличиваем общую сумму
    s += x
    # Если вычесть из суммы минимальный префикс - будет ли она больше максимума
    # если да - перезаписать максимум
    if s - mn > mx:
        mx = s - mn

    # При необходимости заменить префикс
    mn = min(mn, s)

print(mx)

f = open(’27B_09_4.txt’)
n = int(f.readline())
a = [int(i) for i in f]

# Общая сумма
s = 0
# Максимальный префикс
mx = 0
mn = 0

for i in range(n):
    x = a[i]
    # Увеличиваем общую сумму
    s += x
    # Если вычесть из суммы максимальный префикс - будет ли она меньше минимума
    # если да - перезаписать минимум
    if s - mx < mn:
        mn = s - mx

    # При необходимости заменить префикс
    mx = max(mx, s)

print(mn)

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


f = open(’27B_09_5.txt’)
n = int(f.readline())
a = [int(i) for i in f]

# Чему кратно количество чисел
d = 10

r = 0  # Количество встреченных простых чисел
# Для сумм с нулевым количеством нужных чисел изначально самая маленькая - начальная
tails = [0] + [10 ** 10] * (d - 1)
mx = 0
s = 0

for i in range(n):
    x = a[i]
    # Увеличиваем общую сумму
    s += x

    # Если нашли нужное число - увеличиваем на 1 их количество
    # перезаписываем хвост, выбирая наименьший для этого
    # количества оканчивающихся k чисел
    if simple(x):
        r += 1
        if s < tails[r % d]:
            tails[r % d] = s

    # Находим максимальную сумму, отсекая хвост с количеством оканчивающихся k чисел
    # равным остатку от деления на необходимое количество d
    if s - tails[r % d] > mx:
        mx = s - tails[r % d]

print(mx)


                                                                                                  
                                                                                                  

Решение для А пункта:
f = open(’27A_04_2__3knes.txt’)
n = int(f.readline())
a = [int(i) for i in f]
l = 0
for i in range(len(a)):
    s = 0
    k = 0
    for j in range(i,len(a)):
        s += a[j]
        k += 1
        if s == 0:
            l = max(l,k)
print(l)
Решение для Б пункта:
’’’
Префиксная сумма равна 0, только в том случае, если конец и начало префиксной суммы равны между собой.
Идея решения: мы создадим словарь, у которого в качестве ключа будет значение префиксной суммы,
а в качестве значения у нас будет список, который будет хранить номера индексов,
на которых встречалась такая сумма.
Затем мы сможем найти максимальную длину вычитав минимальный индекс из максимального индекса,
на котором встречалась данная сумма.
’’’
f = open(’27B_04_2__3knet.txt’)
n = int(f.readline())
l = 0
d = dict()#создаем словарь, в котором будем хранить значения префиксной суммы и номера индексов
s = 0
for i in range(n):
    x = int(f.readline())
    s += x
    if s not in d.keys():#если данная префиксная сумма ранее не встречалась,
#то добавляем первый индекс к данной сумме
        d[s] = [i]
    else:#в ином случае добавляем новый индекс в список
        d[s].append(i)
res = [x for x in d.values() if len(x) > 1] #получаем списки индексов,
#чьи префиксные сумма встречались более одного раза за файл.
l = max(max(x) - min(x) for x in res) #определяем максимальную длину подпоследовательности.
print(l)

Решение для А пункта:
f = open(’2_27A.txt’)
n = int(f.readline())
a = [int(i) for i in f]
mx = 0
for i in range(len(a)):
    s = 0
    for j in range(i,len(a)):
        s += a[j]
        if s % 317 == 0 and s % 2 == 0:
            mx = max(mx,s)
print(mx)
Решение для Б пункта:
f = open(’2_27B.txt’)
n = int(f.readline())
D = 317
k = [[10**20 for i in range(2)] for j in range(D)]#двумерный массив,
#в котором мы будем хранить минимальные префиксные суммы
#любой чётности любого возможного остатка при делении на D
mx = 0
s = 0
for i in range(n):
    x = int(f.readline())
    s += x
    if s % D == 0 and s % 2 == 0:
        mx = max(mx,s)
    s1 = s - k[s%D][s%2]#новая сумма с отрубленным хвостиком, которая является чётной и кратной 317
    mx = max(mx,s1)
    k[s%D][s%2] = min(k[s%D][s%2],s)#обновляем список k, храним минимальные префиксные суммы
print(mx)

Решение для А пункта:
f = open(’2_27A.txt’)
n = int(f.readline())
a = [int(i) for i in f]
mx = 0
l = 0
for i in range(len(a)):
    s = 0
    k = 0
    for j in range(i, len(a)):
        s += a[j]
        k += 1
        if s % 375 == 0 and s % 2 != 0:
            if s > mx or (s == mx and k < l):
                mx = s
                l = k
print(l)
Решение для Б пункта:
f = open(’2_27B.txt’)
n = int(f.readline())
mx = 0
l = 0
D = 375
k = [[10 ** 20 for i in range(2)] for j in range(D)]
ml = [[0 for i in range(2)] for j in range(D)]
s = 0
for i in range(n):
    x = int(f.readline())
    s += x
    if s % D == 0 and s % 2 != 0:
        mx = s
        l = i + 1
    s1 = s - k[s % D][1 - s % 2]
    l1 = (i + 1) - ml[s % D][1 - s % 2]
    if s1 > mx or (s1 == mx and l1 < l):
        mx = s1
        l = l1
    if s < k[s%D][s%2]:
        k[s%D][s%2] = s
        ml[s%D][s%2] = i+1
print(l)

Решение для А пункта:
def simple(x):#функция для проверки числа на простоту
    return x > 1 and all(x % y for y in range(2,int(x**0.5)+1))
f = open(’3_27A.txt’)
n = int(f.readline())
a = [int(i) for i in f]
max_simple = max(x for x in a if simple(x))
mx = 0
l = 0
for i in range(len(a)):
    s = 0
    k = 0
    for j in range(i,len(a)):
        s += a[j]
        k += 1
        if s % max_simple == 0:
            if s > mx or (s == mx and k < l):
                mx = s
                l = k
print(l)
Решение для Б пункта:
def simple(x):
    return x > 1 and all(x % y for y in range(2,int(x**0.5)+1))
f = open(’3_27B.txt’)
a = [int(i) for i in f]
max_simple = max(x for x in a if simple(x))
k = [10**20 for i in range(max_simple)]
ml = [0 for i in range(max_simple)]
mx = 0
l = 0
s = 0
for i in range(n):
    x = a[i]
    s += x
    if s % max_simple == 0:
        mx = s
        l = i + 1
    s1 = s - k[s % max_simple]
    l1 = (i+1) - ml[s % max_simple]
    if s1 > mx or (s1 == mx and l1 < l):
        mx = s1
        l = l1
    if s < k[s % max_simple]:
                                                                                                  
                                                                                                  
        k[s % max_simple] = s
        ml[s % max_simple] = i + 1
print(l)

f = open(’3_27B.txt’)
n = int(f.readline())
a = [int(i) for i in f]
fibb = [0,1]
while fibb[-1] < max(a):
    fibb.append(fibb[-1] + fibb[-2])
D = max(x for x in set(a) if x in fibb)
mx = 0
l = 0
k = [10**20 for i in range(D)]
ml = [0 for i in range(D)]
s = 0
for i in range(n):
    x = a[i]
    s += x
    if s % D == 0:
        mx = s
        l = i + 1
    s1 = s - k[s % D]
    l1 = (i+1) - ml[s % D]
    if s1 > mx or (s1 == mx and l1 < l):
        mx = s1
        l = l1
    if s < k[s % D]:
        k[s % D] = s
        ml[s % D] = i + 1
print(l)

Решение для А пункта:
f = open(’4_27A.txt’)
n = int(f.readline())
a = [int(i) for i in f]
mx = 0
l = 0
for i in range(len(a)):
    s = 0
    k = 0
    for j in range(i,len(a)):
        s += a[j]
        k += 1
        if s % 113 == 0:
            if s > mx or (s == mx and k > l):
                mx = s
                l = k
print(l)
Решение для Б пункта:
f = open(’4_27B.txt’)
n = int(f.readline())
D = 113
mx = 0
l = 0
k = [10**20 for i in range(D)]
ml = [0 for i in range(D)]
s = 0
for i in range(n):
    x = int(f.readline())
    s += x
    if s % D == 0:
        mx = s
        l = i + 1
    s1 = s - k[s % D]
    l1 = (i+1) - ml[s % D]
    if s1 > mx or (s1 == mx and l1 > l):
        mx = s1
        l = l1
    if s < k[s % D]:
        k[s % D] = s
        ml[s % D] = i+1
print(l)

Решение для пункта А:
f = open("4_27A.txt")
n = int(f.readline())
a = [int(i) for i in f]  # Считываем данные из файла и добавляем их в список
mx = 0  # Максимальная сумма чисел искомой последовательности
for i in range(len(a)):
    s = 0  # Сумма чисел для текущей последовательности
    k5 = 0  # Количество чисел, кратных 5
    for j in range(i, len(a)):
        s += a[j]  # Собираем искомую последовательность
        if a[j] % 5 == 0:  # Проверяем, кратно ли данное число 5, увеличиваем k5
            k5 += 1
        if s % 13 == 0 and k5 % 7 == 0:  # Проверяем, удовлетворяет ли текущая сумма всем условиям
            mx = max(mx, s)  # Записываем максимальную сумму
print(mx)  # Выводим ответ

Решение для пункта Б:
f = open("4_27B.txt")
n = int(f.readline())
k = 13
pref = [[10 ** 100] * k for i in range(7)]
# Мы создаём двумерный список для минимальных сумм с разными остатками от деления на k,
# учитывающий остатки от деления на 7 количества чисел, кратных 5
s = mx = k5 = 0  # Общая сумма / Максимальная сумма / Количество чисел, кратных 5
for i in range(n):
    x = int(f.readline())
    s += x  # Прибавляем новое число из файла
    if x % 5 == 0:  # Проверяем, кратно ли данное число 5, увеличиваем k5
        k5 += 1
    p = s % k  # Остаток от деления на k текущей суммы
    t = k5 % 7  # Остаток от деления на 7 количества чисел, кратных 5
    if p == 0 and k5 % 7 == 0:  # Проверяем, удовлетворяет ли общая сумма всем условиям
        mx = s  # Если да - записываем её как максимальную
    elif pref[t][p] != 10 ** 100:  # Если нет - проверяем, есть ли подходящий префикс
        mx = max(mx, s - pref[t][p])  # Записываем максимальную сумму, вычитая нужный префикс
    pref[t][p] = min(pref[t][p], s)  # После всех проверок записываем текущую общую сумму в качестве префикса
print(mx)  # Выводим ответ

Решение для пункта А:
def prime(b):  # Данная функция возвращает True или False в зависимости от того, простое число или нет
    for q in range(2, int(b ** 0.5) + 1):
        if b % q == 0:  # Проверяем, является ли q делителем числа b
            return False
    return b != 1  # Число 1 не является простым


f = open("5_27A.txt")
n = int(f.readline())
a = [int(i) for i in f]  # Считываем данные из файла и добавляем их в список
D = 169
M = 10
mx = 0  # Максимальная сумма чисел искомой последовательности
for i in range(len(a)):
    s = 0  # Сумма чисел для текущей последовательности
    kp = 0  # Количество простых чисел
    for j in range(i, len(a)):
        s += a[j]  # Собираем искомую последовательность
        if simple(a[j]):  # Проверяем, является ли число простым, увеличиваем kp
            kp += 1
        if s % D == 0 and kp % M == 0:  # Проверяем, удовлетворяет ли текущая сумма всем условиям
            mx = max(mx, s)  # Записываем максимальную сумму
print(mx)  # Выводим ответ

Решение для пункта Б:
def prime(b):  # Данная функция возвращает True или False в зависимости от того, простое число или нет
    for q in range(2, int(b ** 0.5) + 1):
        if b % q == 0:  # Проверяем, является ли q делителем числа b
            return False
    return b != 1  # Число 1 не является простым


f = open("5_27B.txt")
n = int(f.readline())
k = 169
pref = [[10 ** 100] * k for i in range(10)]
# Мы создаём двумерный список для минимальных сумм с разными остатками от деления на k,
# учитывающий остатки от деления на 10 количества простых чисел
s = mx = kp = 0  # Общая сумма / Максимальная сумма / Количество простых чисел
for i in range(n):
    x = int(f.readline())
    s += x  # Прибавляем новое число из файла
                                                                                                  
                                                                                                  
    if prime(x):  # Проверяем, является ли число простым, увеличиваем kp
        kp += 1
    p = s % k  # Остаток от деления на k текущей суммы
    t = kp % 10  # Остаток от деления на 10 количества простых чисел
    if p == 0 and kp % 10 == 0:  # Проверяем, удовлетворяет ли общая сумма всем условиям
        mx = s  # Если да - записываем её как максимальную
    elif pref[t][p] != 10 ** 100:  # Если нет - проверяем, есть ли подходящий префикс
        mx = max(mx, s - pref[t][p])  # Записываем максимальную сумму, вычитая нужный префикс
    pref[t][p] = min(pref[t][p], s)  # После всех проверок записываем текущую общую сумму в качестве префикса
print(mx)  # Выводим ответ

Решение для пункта А:
f = open("5_27A.txt")
n = int(f.readline())
a = [int(i) for i in f]  # Считываем данные из файла и добавляем их в список
mx = 0  # Максимальная сумма чисел искомой последовательности
for i in range(len(a)):
    s = 0  # Сумма чисел для текущей последовательности
    k13 = 0  # Количество чисел, кратных 13
    for j in range(i, len(a)):
        s += a[j]  # Собираем искомую последовательность
        if a[j] % 13 == 0:  # Проверяем, кратно ли данное число 13, увеличиваем k13
            k13 += 1
        if s % 97 == 0 and k13 == 17:  # Проверяем, удовлетворяет ли текущая сумма всем условиям
            mx = max(mx, s)
print(mx)

Решение для пункта Б:
f = open("5_27B.txt")
n = int(f.readline())
k = 97
pref = [[10 ** 100] * k for i in range(-17, 76828 + 1)]
# Мы создаём двумерный список для минимальных сумм с разными остатками от деления на k,
# учитывающий количество чисел, кратных 13 (Его нужно посчитать предварительно, в нашем файле - 76828)
# Перебор начинается от -17 во избежание ошибки,
# поскольку на первых итерациях значение выражения (k13 - 17) будет отрицательным
s = mx = k13 = 0  # Общая сумма / Максимальная сумма / Количество чисел, кратных 13
for i in range(n):
    x = int(f.readline())
    s += x  # Прибавляем новое число из файла
    if x % 13 == 0:  # Проверяем, кратно ли данное число 13, увеличиваем k13
        k13 += 1
    p = s % k  # Остаток от деления на k текущей суммы
    t = k13 - 17  # Остаток от деления на 7 количества чисел, кратных 13
    if p == 0 and k13 == 17:  # Проверяем, удовлетворяет ли общая сумма всем условиям
        mx = s  # Если да - записываем её как максимальную
    elif pref[t][p] != 10 ** 100:  # Если нет - проверяем, есть ли подходящий префикс
        mx = max(mx, s - pref[t][p])  # Записываем максимальную сумму, вычитая нужный префикс
    pref[k13][p] = min(pref[k13][p], s)  # После всех проверок записываем текущую общую сумму в качестве префикса
print(mx)  # Выводим ответ

Решение для А пункта:
f = open(’5_27A.txt’)
n = int(f.readline())
a = [int(i) for i in f]
mx = 0
l = 0
for i in range(len(a)):
    s = 0
    k = 0
    for j in range(i,len(a)):
        s += a[j]
        k += 1
        if s % 101 == 0:
            if s > mx or (s == mx and k < l):
                mx = s
                l = k
print(l)
Решение для Б пункта:
f = open(’5_27B.txt’)
n = int(f.readline())
D = 101
mx = 0
l = 0
s = 0
k = [10**20 for i in range(D)]
ml = [0 for i in range(D)]
for i in range(n):
    x = int(f.readline())
    s += x
    if s % D == 0:
        mx = s
        l = i + 1
    s1 = s - k[s % D]
    l1 = (i+1) - ml[s % D]
    if s1 > mx or (s1 == mx and l1 < l):
        l = l1
        mx = s1
    if s < k[s % D]:
        k[s % D] = s
        ml[s % D] = i + 1
print(l)