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

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

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

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

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


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

5	2
5
20
20
19
15

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

f = open(’1_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]) % 20 == 0 and nums[i] * nums[j] % 5 == 0:
            cnt += 1

print(cnt)

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

f = open(’1_B.txt’)
k = 20

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

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

print(cnt)

Ответ: 6 50025294