Задача к ЕГЭ по информатике на тему «Макс/мин, кол-во пар, сумма/разность кратна/не кратна» №2

Просмотров 7 Комментарии 0

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

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

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

$5$

$90$

$2$

$10$

$40$

$3$

Выходные данные для приведённого выше примера: $8$

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

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

f = open(’18_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]) % 50 != 0:
            cnt += 1

print(cnt)

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

f = open(’27B.txt’)
n = int(f.readline())
ans = 0
# Количества чисел с определенными остаткми от деления на 50
kr = [0]*50

for i in range(n):
    x = int(f.readline())
    # Если x в сумме с остатком не будет делиться на 50,
    # значит со всеми числами с таким остатком он образует пары,
    # чья сумма не делится на 50
    for j in range(50):
        if (x + j) % 50 != 0:
            ans += kr[j]
    # Увеличиваем количество чисел с этим остатком
    kr[x % 50] += 1

print(ans)

Ответ: 187 3974131350