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

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

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

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

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

$5$

$8$

$2$

$10$

$20$

$3$

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

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

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

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

print(cnt)

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

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

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

print(ans)

Ответ: 174 3649957950