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

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

Задание выполняется с использованием прилагаемых файлов

Дана последовательность $N$ целых положительных чисел. Необходимо определить количество пар элементов этой последовательности, сумма которых делится на $a = 9$ и при этом хотя бы один элемент из пары больше $b = 90$ .

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

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

Пример входного файла:

$4$

$18$

$100$

$120$

$33$

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

$1$

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

Решение 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)

Ответ: 19 4465137