27.05 Макс/мин, кол-во пар, сумма/разность кратна/не кратна

Идея статического решения:

Сумма пары кратна 2 в том случае, когда сумма остатков при делении на 2 пары чисел кратна 2. Идея заключается в том, что мы сначала совершим проход по файлу, в котором посчитаем количество чисел под каждым остатком. Затем, используя знания комбинаторики, нужно записать выражение, которое посчитает итоговое количество пар.

Идея динамического решения:

Идея решения заключается в том, чтобы под каждым остатком при делении на 2 собирать количество число с одинаковым остатком при делении на 2 с той целью, чтобы в итоге мы могли на каждой итерации получать итоговое количество пар на данный момент. Сумма пары кратна 2 в том случае, когда сумма остатков при делении на 2 пары чисел кратна 2. Считывая одно число с определенным остатком при делении на 2 мы должны подобрать в пару ему такое число, чтобы в итоге их пара была кратна 2. Не трудно определить какой остаток нужен для второго числа при делении, зная, остаток первого числа, для этого можно использовать формулу: (D - x % D) % D , где D - это 2, а x - первое число пары.

#переборный алгоритм:
f = open(’1_A.txt’) #открываем файл.
n = int(f.readline()) #считываем первое число - количество чисел в файле.
a = [] #cписок, в котором у нас будут находиться все числа файла.
for i in range(n): #проход по файлу.
    a.append(int(f.readline())) #добавление текущего числа в список.

counter = 0 #итоговый счётчик пар.
for i in range(0,len(a)-1): #перебор для первого числа пары.
    for j in range(i+1,len(a)): #перебор для второго числа пары.
        if (a[i]+a[j]) % 2 == 0: #проверка по условию.
            counter += 1 #увеличиваем итоговый счётчик
print(counter) #вывод ответа.

#Статическое решение
file = open(’2__t1mf.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 2 #число, на которое нацело должна делиться сумма пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 2
count += (k[0] * (k[0]-1)//2) + (k[1] * (k[1]-1)//2)
print(count) #вывод ответа.

#Динамическое решение
file = open(’2__t1mf.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 2 #число, на которое нацело должна делиться сумма пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    need_ost = (div - x % div) % div #определяем необходимый остаток второго числа при делении на 2 для того чтобы сумма пары делилась нацело
    count += k[need_ost] #увеличиваем count на количество чисел с необходимым остатком для первого числа для получения суммы пары кратной 2
    k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 2
print(count) # вывод ответа

Решение 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):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % 9 == 0:
            if (a[i] > 90) or (a[j] > 90):
                ans += 1
print(ans)

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

f = open(’Задание_27_A__gmt5.txt’)
n = int(f.readline())
a = [[0 for j in range(9)] for i in range(2)]
# a[i][j], где i == 0 - > 90, i == 1 - <= 90,
#              j - остатки при делении на 9
ans = 0
for i in range(n):
    x = int(f.readline())
    dop = (9 - x % 9) % 9
    # Если новый элемент больше 90, то к нему в пару
    # можно поставить числа и больше и меньше 90
    if x > 90:
        ans += a[0][dop] + a[1][dop]
        a[0][x % 9] += 1
    # Если новый элемент меньше 90, к нему в пару
    # можно поставить только числа больше 90
    else:
        ans += a[0][dop]
        a[1][x % 9] += 1
print(ans)

Решение 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):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if (a[i] + a[j] + a[k]) % 4 == 0:
                ans = min(ans, a[i] + a[j] + a[k])
print(ans)

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

f = open(’8.txt’)
n = int(f.readline())
a = [int(i) for i in f]
k = 4
# Список из минимальных чисел с определенным остатком от деления
t = [10 ** 10] * k
# Список из пар с минимальными суммами с определенным остатком
v = [[10 ** 10, 10 ** 10] for i in range(k)]
mn = 10 ** 10
for i in range(2, len(a)):
    # Обрабатываем элемент на расстоянии 2 от текущего (через один слева)
    ost1 = a[i - 2] % k
    # Если он меньше прошлого с таким остатком - обновляем список
    t[ost1] = min(t[ost1], a[i - 2])

    # Обрабатываем средний элемент - на расстоянии 1 от текущего (слева)
    ost2 = a[i - 1] % k
    # Для каждого из минимальных первых элементов (для каждого остатка)
    # создаём новые суммы с новым средним элементом и обновляем
    # эти суммы в списке v, если они получились меньше прошлых
    for j in range(k):
        if t[j] < 10 ** 10:
            sm_pair = t[j] + a[i - 1]
            if sm_pair < sum(v[(j + ost2) % k]):
                v[(j + ost2) % k] = [t[j], a[i - 1]]

    # Вычисляем остаток для пары в сумму к нашему числу
    ost3 = (k - (a[i] % k)) % k
    # Если уже нашлось число с таким остатком - считаем и обновляем минимум
    if sum(v[ost3]) < 10 ** 10 * 2:
        sm = a[i] + sum(v[ost3])
        mn = min(mn, sm)

print(mn)

Решение 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):
    for j in range(i + 1, n):
        if a[i] % 100 != a[j] % 100:
            if (a[i] % 6 == 0) or (a[j] % 6 == 0):
                ans = max(ans, a[i] + a[j])
print(ans)

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

f = open("9.txt")
n = int(f.readline())
# Список максимальных чисел с определенными остатками от деления, которые кратны 6
maxim_d_6 = [0]*100
# Список максимальных чисел с определенными остатками от деления, которые НЕ кратны 6
maxim_d = [0]*100
maxim = 0
for i in range(n):
    x = int(f.readline())
    # Если x кратен 6, к нему в пару можно ставить и кратные и некратные 6 числа
    if x % 6 == 0:
        for j in range(100):
            # Если остатки от деления разные - обновляем максимум
            if j != x % 100:
                maxim = max(x+maxim_d_6[j], x+maxim_d[j], maxim)
        # Обновляем максимальное число с определенным остатком
        maxim_d_6[x % 100] = max(maxim_d_6[x % 100], x)
    # Если x НЕ кратен 6, к нему в пару можно ставить только кратные 6 числа
    else:
        for j in range(100):
            # Если остатки от деления разные - обновляем максимум
            if j != x % 100:
                maxim = max(x+maxim_d_6[j], maxim)
        # Обновляем максимальное число с определенным остатком
        maxim_d[x % 100] = max(maxim_d[x % 100], x)
print(maxim)

Идея статического решения:

Сумма пары кратна 3 в том случае, когда сумма остатков при делении на 3 пары чисел кратна 3. Идея заключается в том, что мы сначала совершим проход по файлу, в котором посчитаем количество чисел под каждым остатком. Затем, используя знания комбинаторики, нужно записать выражение, которое посчитает итоговое количество пар.

Идея динамического решения:

Идея решения заключается в том, чтобы под каждым остатком при делении на 3 собирать количество число с одинаковым остатком при делении на 3 с той целью, чтобы в итоге мы могли на каждой итерации получать итоговое количество пар на данный момент. Сумма пары кратна 3 в том случае, когда сумма остатков при делении на 3 пары чисел кратна 3. Считывая одно число с определенным остатком при делении на 3 мы должны подобрать в пару ему такое число, чтобы в итоге их пара была кратна 3. Не трудно определить какой остаток нужен для второго числа при делении, зная, остаток первого числа, для этого можно использовать формулу: (D - x % D) % D , где D - это 3, а x - первое число пары.

#переборный алгоритм:
f = open(’1_A.txt’) #открываем файл.
n = int(f.readline()) #считываем первое число - количество чисел в файле.
a = [] #cписок, в котором у нас будут находиться все числа файла.
for i in range(n): #проход по файлу.
    a.append(int(f.readline())) #добавление текущего числа в список.

counter = 0 #итоговый счётчик пар.
for i in range(0,len(a)-1): #перебор для первого числа пары.
    for j in range(i+1,len(a)): #перебор для второго числа пары.
        if (a[i]+a[j]) % 3 == 0: #проверка по условию.
            counter += 1 #увеличиваем итоговый счётчик
print(counter) #вывод ответа.

#Статическое решение
file = open(’4__t7qm.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 3 #число, на которое нацело должна делиться сумма пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 3
for i in range(len(k)//2 + 1): #делаем проход до половины всевозможных остатков при делении на 3
    if i == 0: #если остаток 0
        count += k[0] * (k[0] - 1) // 2 #то мы можем составить пару из двух чисел кратных 3
    else: # в ином случае
        count += k[i] * k[len(k)-i] #составляем пару из двух разных остатков при делении на 3
print(count) #вывод ответа.

#Динамическое решение
file = open(’4__t7qm.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 3 #число, на которое нацело должна делиться сумма пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    need_ost = (div - x % div) % div #определяем необходимый остаток второго числа при делении на 3 для того чтобы сумма пары делилась нацело
    count += k[need_ost] #увеличиваем count на количество чисел с необходимым остатком для первого числа для получения суммы пары кратной 3
    k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 3
print(count) # вывод ответа

Решение 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):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % 2 == 0:
            if (a[i] % 13 == 0) or (a[j] % 13 == 0):
                ans = max(ans, a[i] + a[j])

print(ans)

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

f = open(’10.txt’)

n = int(f.readline())
# Список, где первый индекс - кратность 13 (0 - не кратно, 1 - кратно),
# а второй индекс - остаток от деления на 2
nums = [[-10 ** 10] * 2 for i in range(2)]
mx = -10 ** 10

for i in range(n):
    x = int(f.readline())
    ost = (2 - (x % 2)) % 2
    # Если x кратен 13, к нему в пару можно ставить числа
    # и кратные и не кратные 13
    if x % 13 == 0:
        mx = max(mx, x + nums[0][ost], x + nums[1][ost])
        nums[1][x % 2] = max(x, nums[1][x % 2])
    # Если же x не кратен 13, к нему в пару можно ставить
    # только числа, кратные 13
    else:
        mx = max(mx, x + nums[1][ost])
        nums[0][x % 2] = max(x, nums[0][x % 2])

print(mx)

Решение 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):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % 42 == 0:
            if (a[i] > 512) or (a[j] > 512):
                ans += 1
print(ans)

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

file = open(’file_B.txt’)

n = int(file.readline())
ans = 0
# Список чисел с определенными остатками от деления, которые больше 512
k_over_512 = [0] * 42
# Список чисел с определенными остатками от деления, которые меньше 512
k_less_512 = [0] * 42

for i in range(n):
    x = int(file.readline())
    ost = x % 42
    dop = (42 - ost) % 42
    # Если x больше 512, к нему в пару можно ставить числа как больше,
    # так и меньше 512
    if x > 512:
        ans += k_over_512[dop] + k_less_512[dop]
        k_over_512[ost] += 1
    # Если x меньше 512, к нему в пару можно ставить только числа больше 512
    else:
        ans += k_over_512[dop]
        k_less_512[ost] += 1
print(ans)

Идея эффективного решения:

Идея решения заключается в том, чтобы под каждым остатком при делении на 165 собрать максимальное число с той целью, чтобы в итоге мы могли получить максимальную сумму кратную 165. Сумма пары кратна 165 в том случае, когда сумма остатков при делении на 165 пары чисел кратна 165. Считывая одно число с определенным остатком при делении на 165 мы должны подобрать в пару ему такое число, чтобы в итоге их пара была кратна 165. Не трудно определить какой остаток нужен для второго числа при делении, зная, остаток первого числа, для этого можно использовать формулу: (D - x % D) % D , где D - это 165, а x - первое число пары.

#переборный алгоритм:
f = open(’1_A.txt’) #открываем файл.
n = int(f.readline()) #считываем первое число - количество чисел в файле.
a = [] #cписок, в котором у нас будут находиться все числа файла.
for i in range(n): #проход по файлу.
    a.append(int(f.readline())) #добавление текущего числа в список.

maxi = 0 #максимальная сумма пары.
for i in range(0,len(a)-1): #перебор для первого числа пары.
    for j in range(i+1,len(a)): #перебор для второго числа пары.
        if (a[i]+a[j]) % 165 == 0: #проверка по условию.
            maxi = max(maxi, a[i]+a[j]) # записываем максимальную сумму пары.
print(maxi) #вывод ответа.

#эффективный алгоритм:
file = open(’1_B__48rmd.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 165 #число, на которое нацело должна делиться сумма пары.
mx = [0] * div #список, в котором под каждым индексом (под каждым остатком) записано максимальное число данного остатка.
mx_sum = 0 #максимальная сумма пары
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    need_ost = (div - x % div) % div #определяем необходимый остаток второго числа при делении на 165 для того чтобы сумма пары делилась нацело
    mx_sum = max(mx_sum,x+mx[need_ost]) #записываем максимальную сумму пары
    mx[x % div] = max(mx[x % div],x) #записываем максимальное число под индексом равным его остатку при делении на 165, сравниваем между текущим число и тем, что было в этой ячейке ранее
print(mx_sum) #вывод ответа

Идея эффективного решения:

Идея решения заключается в том, чтобы под каждым остатком при делении на 13 собрать минимальное число с той целью, чтобы в итоге мы могли получить минимальную сумму кратную 13. Сумма пары кратна 13 в том случае, когда сумма остатков при делении на 13 пары чисел кратна 13. Считывая одно число с определенным остатком при делении на 13 мы должны подобрать в пару ему такое число, чтобы в итоге их пара была кратна 13. Не трудно определить какой остаток нужен для второго числа при делении, зная, остаток первого числа, для этого можно использовать формулу: (D - x % D) % D , где D - это 13, а x - первое число пары.

#переборный алгоритм:
f = open(’1_A.txt’) #открываем файл.
n = int(f.readline()) #считываем первое число - количество чисел в файле.
a = [] #cписок, в котором у нас будут находиться все числа файла.
for i in range(n): #проход по файлу.
    a.append(int(f.readline())) #добавление текущего числа в список.

mini = 10**10 #минимальная сумма пары.
for i in range(0,len(a)-1): #перебор для первого числа пары.
    for j in range(i+1,len(a)): #перебор для второго числа пары.
        if (a[i]+a[j]) % 13 == 0: #проверка по условию.
            mini = min(mini, a[i]+a[j]) # записываем минимальную сумму пары.
print(mini) #вывод ответа.

#эффективный алгоритм:
file = open(’1_B__48rmd.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 13 #число, на которое нацело должна делиться сумма пары.
mn = [10**10] * div #список, в котором под каждым индексом (под каждым остатком) будет записано минимальное число данного остатка.
mn_sum = 10**10 #минимальная сумма пары
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    need_ost = (div - x % div) % div #определяем необходимый остаток второго числа при делении на 13 для того чтобы сумма пары делилась нацело
    mn_sum = min(mn_sum,x+mn[need_ost]) #записываем минимальную сумму пары
    mn[x % div] = min(mn[x % div],x) #записываем минимальное число под индексом равным его остатку при делении на 13, сравниваем между текущим число и тем, что было в этой ячейке ранее
print(mn_sum) #вывод ответа

Идея статического решения:

Сумма пары кратна 11 в том случае, когда сумма остатков при делении на 11 пары чисел кратна 11. Идея заключается в том, что мы сначала совершим проход по файлу, в котором посчитаем количество чисел под каждым остатком. Затем, используя знания комбинаторики, нужно записать выражение, которое посчитает итоговое количество пар.

Идея динамического решения:

Идея решения заключается в том, чтобы под каждым остатком при делении на 11 собирать количество число с одинаковым остатком при делении на 11 с той целью, чтобы в итоге мы могли на каждой итерации получать итоговое количество пар на данный момент. Сумма пары кратна 11 в том случае, когда сумма остатков при делении на 11 пары чисел кратна 11. Считывая одно число с определенным остатком при делении на 11 мы должны подобрать в пару ему такое число, чтобы в итоге их пара была кратна 11. Не трудно определить какой остаток нужен для второго числа при делении, зная, остаток первого числа, для этого можно использовать формулу: (D - x % D) % D , где D - это 11, а x - первое число пары.

#переборный алгоритм:
f = open(’1_A.txt’) #открываем файл.
n = int(f.readline()) #считываем первое число - количество чисел в файле.
a = [] #cписок, в котором у нас будут находиться все числа файла.
for i in range(n): #проход по файлу.
    a.append(int(f.readline())) #добавление текущего числа в список.

counter = 0 #итоговый счётчик пар.
for i in range(0,len(a)-1): #перебор для первого числа пары.
    for j in range(i+1,len(a)): #перебор для второго числа пары.
        if (a[i]+a[j]) % 11 == 0: #проверка по условию.
            counter += 1 #увеличиваем итоговый счётчик
print(counter) #вывод ответа.

#Статическое решение
file = open(’4_B__2l6y2.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 11 #число, на которое нацело должна делиться сумма пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 11
for i in range(len(k)//2 + 1): #делаем проход до половины всевозможных остатков при делении на 11
    if i == 0: #если остаток 0
        count += k[0] * (k[0] - 1) // 2 #то мы можем составить пару из двух чисел кратных 11
    else: # в ином случае
        count += k[i] * k[len(k)-i] #составляем пару из двух разных остатков при делении на 11
print(count) #вывод ответа.

#Динамическое решение
file = open(’4_B__2l6y2.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 11 #число, на которое нацело должна делиться сумма пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    need_ost = (div - x % div) % div #определяем необходимый остаток второго числа при делении на 11 для того чтобы сумма пары делилась нацело
    count += k[need_ost] #увеличиваем count на количество чисел с необходимым остатком для первого числа для получения суммы пары кратной 11
    k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 11
print(count) # вывод ответа

Идея эффективного решения:

Идея решения заключается в том, чтобы под каждым остатком при делении на 98 собрать максимальное число для того чтобы в итоге получить максимальную сумму пары. Сумма пары кратна 98 в том случае, когда сумма остатков при делении на 88 пары чисел кратна 98. Проходясь по файлу, мы будем искать для текущего числа подбирать такое число, с которым в сумме с ним будет кратна 98. Число, которое мы считываем на текущей итераций всегда будет вторым в паре (j индекс). Числа, которые уже записаны в списке - всегда будут первыми в паре(i индекс). Не трудно определить какой остаток нужен для второго числа при делении, зная, остаток первого числа, для этого можно использовать формулу: (D - x % D) % D , где D - это 98, а x - первое число пары.

f = open(’27A__tcf4.txt’) #открытие файла
n = int(f.readline()) #считываем первое число - количество чисел в файле
arr = list(map(int, f.read().split())) #записываем все числа файла в список
mx = -1 # максимальная сумма пары
pair = [0,0] # элементы пары
for i in range(n-1): # перебор для первого числа пары
    for j in range(i+1, n): # перебор для второго числа пары
        if arr[i] > arr[j] and arr[i] + arr[j] >= mx and (arr[i] + arr[j]) % 98 == 0: # проверка по условию
            mx = arr[i] + arr[j] # обновляем максимальную сумму
            pair = [arr[i],arr[j]] #обновляем элементы пары
print(pair) # вывод ответа

#Эффективный алгоритм
file = open(’27B__tcf5.txt’) #открытие файла
n = int(file.readline()) #считываем первое число - количество чисел в файле
div = 98 # наш делитель
mx = [0]*div # список, в котором будет храниться максимальное число под каждым остатком при делении на 98
mx_sum = [0,0,0] # максимальная сумма пары
for i in range(n): # проход по всему файлу
    x = int(file.readline()) # считываем текущее число
    need_ost = (div - x % div) % div # определяем необходимый остаток для второго числа чтобы в итоге получилась пара кратная 98
    if x < mx[need_ost] and x + mx[need_ost] >= mx_sum[0]: # если первое число в паре больше второго и при этом сумма пары больше или равна максимальной
         mx_sum = [x + mx[need_ost],mx[need_ost],x]# то обновляем максимальную сумму, а также сохраняем числа пары
    mx[x % div] = max(mx[x % div],x) # обновляем максимальное число под определенным остатком, сравнивая текущее число с тем, что было записано в ячейке ранее.
print(mx_sum[1],mx_sum[2]) # вывод чисел пары

Переборное решение:

f = open(’11_A.txt’)

n = int(f.readline())

nums = [int(i) for i in f]

cnt = 0

for i in range(n):
    for j in range(i + 1, n):
        if (nums[i] + nums[j]) % 91 == 0:
            if nums[i] > 33 or nums[j] > 33:
                cnt += 1

print(cnt)

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

n = int(input())
# Количества чисел с определенными остатками, которые больше 33
b_33 = [0]*91
# Количества чисел с определенными остатками, которые меньше 33
m_33 = [0]*91
ans = 0

for i in range(n):
    x = int(input())
    # Если x больше 33, к нему в пару можно ставить числа
    # и больше и меньше 33
    if x > 33:
        ans += b_33[(91 - x%91) % 91] + m_33[(91 - x%91) % 91]
        b_33[x%91] += 1
    # Иначе же к нему в пару можно ставить только числа больше 33
    else:
        ans += b_33[(91 - x%91) % 91]
        m_33[x%91] += 1
print(ans)

Идея динамического решения:

Разность пары кратна 29 в том случае, когда разность остатков при делении на 29 пары чисел кратна 29. Это выполняется только в одном случае, когда остатки при делении на 29 двух чисел равны. Идея решения заключается в том, чтобы под каждым остатком при делении на 29 собирать минимальное число с той целью, чтобы в итоге мы могли получить минимальную сумму кратную 29.

#Переборный алгоритм
f = open("27A.txt") #открываем файл.
n = int(f.readline()) #считываем первое число - количество чисел в файле.
a = [int(f.readline()) for x in range(n)] #список, в котором хранятся все числа файла
ans = 100000000 #минимальная сумма пары
for i in range(n): #проход для первого числа пары
    for j in range(i + 1, n): #проход для второго числа пары
        if abs(a[i] - a[j]) % 29 == 0: #проверка по условию
            ans = min(ans, a[i] + a[j]) #обновление минимальной суммы
print(ans) #вывод ответа

#Эффективное решение
file = open(’27B__tcct.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 29 #число, на которое нацело должна делиться сумма пары.
mn = [10**10] * div #список, в котором под каждым индексом (под каждым остатком) записано минимальное число данного остатка.
mn_sum = 10**10 #минимальная сумма пары
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    mn_sum = min(mn_sum,x + mn[x % div]) #записываем минимальную сумму пары
    mn[x % div] = min(mn[x % div],x) #записываем минимальное число под индексом равным его остатку при делении на 29, сравниваем между текущим число и тем, что было в этой ячейке ранее
print(mn_sum) #вывод ответа

f = open("osn3.txt")
n = int(f.readline())
a = [int(i) for i in f]
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if abs(a[i] - a[j]) % 8 == 6:
            ans += 1
print(ans)

Идея статического решения:

Сумма пары кратна 11 в том случае, когда сумма остатков при делении на 11 пары чисел кратна 11. Идея заключается в том, что мы сначала совершим проход по файлу, в котором посчитаем количество чисел под каждым остатком. Затем, используя знания комбинаторики, нужно записать выражение, которое посчитает итоговое количество пар.

Идея динамического решения:

Идея решения заключается в том, чтобы под каждым остатком при делении на 11 собирать количество число с одинаковым остатком при делении на 11 с той целью, чтобы в итоге мы могли на каждой итерации получать итоговое количество пар на данный момент. Сумма пары кратна 11 в том случае, когда сумма остатков при делении на 11 пары чисел кратна 11. Считывая одно число с определенным остатком при делении на 11 мы должны подобрать в пару ему такое число, чтобы в итоге их пара была кратна 11. Не трудно определить какой остаток нужен для второго числа при делении, зная, остаток первого числа, для этого можно использовать формулу: (D - x % D) % D , где D - это 11, а x - первое число пары.

#переборный алгоритм:
f = open(’1_A.txt’) #открываем файл.
n = int(f.readline()) #считываем первое число - количество чисел в файле.
a = [] #cписок, в котором у нас будут находиться все числа файла.
for i in range(n): #проход по файлу.
    a.append(int(f.readline())) #добавление текущего числа в список.

counter = 0 #итоговый счётчик пар.
for i in range(0,len(a)-1): #перебор для первого числа пары.
    for j in range(i+1,len(a)): #перебор для второго числа пары.
        if (a[i]+a[j]) % 11 == 0: #проверка по условию.
            counter += 1 #увеличиваем итоговый счётчик
print(counter) #вывод ответа.

#Статическое решение
file = open(’4_B__2l6y2.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 11 #число, на которое нацело должна делиться сумма пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 11
for i in range(len(k)//2 + 1): #делаем проход до половины всевозможных остатков при делении на 11
    if i == 0: #если остаток 0
        count += k[0] * (k[0] - 1) // 2 #то мы можем составить пару из двух чисел кратных 11
    else: # в ином случае
        count += k[i] * k[len(k)-i] #составляем пару из двух разных остатков при делении на 11
print(count) #вывод ответа.

#Динамическое решение
file = open(’4_B__2l6y2.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 11 #число, на которое нацело должна делиться сумма пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    need_ost = (div - x % div) % div #определяем необходимый остаток второго числа при делении на 11 для того чтобы сумма пары делилась нацело
    count += k[need_ost] #увеличиваем count на количество чисел с необходимым остатком для первого числа для получения суммы пары кратной 11
    k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 11
print(count) # вывод ответа

Переборное решение:

f = open(’11_A.txt’)

n = int(f.readline())

nums = [int(i) for i in f]

cnt = 0

for i in range(n):
    for j in range(i + 1, n):
        if (nums[i] + nums[j]) % 91 == 0:
            if nums[i] > 33 or nums[j] > 33:
                cnt += 1

print(cnt)

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

n = int(input())
# Количества чисел с определенными остатками, которые больше 33
b_33 = [0]*91
# Количества чисел с определенными остатками, которые меньше 33
m_33 = [0]*91
ans = 0

for i in range(n):
    x = int(input())
    # Если x больше 33, к нему в пару можно ставить числа
    # и больше и меньше 33
    if x > 33:
        ans += b_33[(91 - x%91) % 91] + m_33[(91 - x%91) % 91]
        b_33[x%91] += 1
    # Иначе же к нему в пару можно ставить только числа больше 33
    else:
        ans += b_33[(91 - x%91) % 91]
        m_33[x%91] += 1
print(ans)

Переборное решение:

f = open(’11_A.txt’)

n = int(f.readline())

nums = [int(i) for i in f]

cnt = 0

for i in range(n):
    for j in range(i + 1, n):
        if (nums[i] + nums[j]) % 91 == 0:
            if nums[i] > 33 or nums[j] > 33:
                cnt += 1

print(cnt)

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

n = int(input())
# Количества чисел с определенными остатками, которые больше 33
b_33 = [0]*91
# Количества чисел с определенными остатками, которые меньше 33
m_33 = [0]*91
ans = 0

for i in range(n):
    x = int(input())
    # Если x больше 33, к нему в пару можно ставить числа
    # и больше и меньше 33
    if x > 33:
        ans += b_33[(91 - x%91) % 91] + m_33[(91 - x%91) % 91]
        b_33[x%91] += 1
    # Иначе же к нему в пару можно ставить только числа больше 33
    else:
        ans += b_33[(91 - x%91) % 91]
        m_33[x%91] += 1
print(ans)

Переборное решение:

f = open(’13_A.txt’)

n = int(f.readline())

nums = [int(i) for i in f]

cnt = 0

for i in range(n):
    for j in range(i + 1, n):
        if (nums[i] + nums[j]) % 5 == 0 or (nums[i] + nums[j]) % 7 == 0:
            cnt += 1

print(cnt)

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

f = open(’27.txt’)
n = int(f.readline())
# Количества чисел с определенными остатками на 5, 7, 35
a = [0] * 5
b = [0] * 7
c = [0] * 35
ans = 0
for i in range(n):
    x = int(f.readline())
    # Количество пар, кратных 5 или 7 равно сумме количества пар,
    # кратных 5 и количества пар, кратных 7, из которой вычли количество пар,
# кратных 35
    ans += a[(5 - x % 5) % 5] + b[(7 - x % 7) % 7] - c[(35 - x % 35) % 35]
    a[x % 5] += 1
    b[x % 7] += 1
    c[x % 35] += 1
print(ans)

Идея статического решения:

Сумма пары кратна 90 в том случае, когда сумма остатков при делении на 90 пары чисел кратна 90. Идея заключается в том, что мы сначала совершим проход по файлу, в котором посчитаем количество чисел под каждым остатком. Затем, используя знания комбинаторики, нужно записать выражение, которое посчитает итоговое количество пар.

Идея динамического решения:

Идея решения заключается в том, чтобы под каждым остатком при делении на 90 собирать количество число с одинаковым остатком при делении на 90 с той целью, чтобы в итоге мы могли на каждой итерации получать итоговое количество пар на данный момент. Сумма пары кратна 90 в том случае, когда сумма остатков при делении на 90 пары чисел кратна 90. Считывая одно число с определенным остатком при делении на 90 мы должны подобрать в пару ему такое число, чтобы в итоге их пара была кратна 90. Не трудно определить какой остаток нужен для второго числа при делении, зная, остаток первого числа, для этого можно использовать формулу: (D - x % D) % D , где D - это 90, а x - первое число пары.

#переборный алгоритм:
f = open(’1_A.txt’) #открываем файл.
n = int(f.readline()) #считываем первое число - количество чисел в файле.
a = [] #cписок, в котором у нас будут находиться все числа файла.
for i in range(n): #проход по файлу.
    a.append(int(f.readline())) #добавление текущего числа в список.

counter = 0 #итоговый счётчик пар.
for i in range(0,len(a)-1): #перебор для первого числа пары.
    for j in range(i+1,len(a)): #перебор для второго числа пары.
        if (a[i]+a[j]) % 90 == 0: #проверка по условию.
            counter += 1 #увеличиваем итоговый счётчик
print(counter) #вывод ответа.

#Статическое решение
file = open(’fileB__v0qe.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 90 #число, на которое нацело должна делиться сумма пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 90
for i in range(len(k)//2 + 1): #делаем проход до половины всевозможных остатков при делении на 90
    if i == 0 or (i == div//2 and div % 2 == 0): #если остаток 0 или равен половине делимого, при условии, что делимое четное число
        count += k[i] * (k[i] - 1) // 2 #то мы можем составить пару из двух чисел кратных 90
    else: # в ином случае
        count += k[i] * k[len(k)-i] #составляем пару из двух разных остатков при делении на 90
print(count) #вывод ответа.

#Динамическое решение
file = open(’fileB__v0qe.txt’) #открываем файл.
n = int(file.readline()) #считываем первое число - количество чисел в файле.
div = 90 #число, на которое нацело должна делиться сумма пары.
k = [0] * div #список, в котором под каждым индексом (под каждым остатком) будет записано количество чисел с таким остатком.
count = 0 #итоговое количество пар
for i in range(n): #проход по всему файлу
    x = int(file.readline()) #считываем текущее число
    need_ost = (div - x % div) % div #определяем необходимый остаток второго числа при делении на 90 для того чтобы сумма пары делилась нацело
    count += k[need_ost] #увеличиваем count на количество чисел с необходимым остатком для первого числа для получения суммы пары кратной 90
    k[x % div] += 1 #увеличиваем на 1 ячейку в списке k равную остатку текущего числа при делении на 90
print(count) # вывод ответа

Переборное решение:

f = open(’14_A.txt’)

n = int(f.readline())

nums = [int(i) for i in f]

cnt = 0

for i in range(n):
    for j in range(i + 1, n):
        if (nums[i] + nums[j]) % 9 == 0:
            # Критерии превышения 9000 у чисел отличаются,
            # значит одно из них больше 9000, а другое нет
            if (nums[i] > 9000) != (nums[j] > 9000):
                cnt += 1

print(cnt)

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

f = open("fileA.txt")
n = int(f.readline())
a = [int(x) for x in f.readlines()]
ost = [[0] * 2 for _ in range(9)]
# ost[i][0] - элемент <= 9000
# ost[i][1] - элемент > 9000
ans = 0
for i in range(n):
# Если элемент больше 9000, к нему в пару можно ставить только числа меньше 9000
    if a[i] > 9000:
        ans += ost[(9 - a[i] % 9) % 9][0]
        ost[a[i] % 9][1] += 1
    # Иначе к нему в пару можно ставить только числа больше 9000
    else:
        ans += ost[(9 - a[i] % 9) % 9][1]
        ost[a[i] % 9][0] += 1
print(ans)
f.close()