Макс/мин, кол-во пар, смешаное кратно/не кратно —Каталог задач по ЕГЭ - Информатика БУ

Ошибка.
Попробуйте повторить позже

Задача 1#20795

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

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

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


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

5	2
5
20
20
19
15

Вложения к задаче

27_A.txt

27_B.txt

Показать ответ и решение

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

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

Ошибка.
Попробуйте повторить позже

Задача 2#26422

На вход программы поступает последовательность из $N$ натуральных чисел. Рассматриваются все пары различных элементов последовательности, у которых одинаковые остатки от деления на $L = 29$ и хотя бы одно из чисел делится на $A = 17$ . Необходимо найти и вывести максимальную сумму элементов пары среди таких пар. В ответ запишите $2$ числа через пробел: ответ для файла А и ответ для файла В.

Вложения к задаче

file_A__nzcj.txt

file_B__nzci.txt

Показать ответ и решение

Решение 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] % 29 == a[j] % 29:
            if (a[i] % 17 == 0) or (a[j] % 17 == 0):
                ans = max(ans, a[i] + a[j])
print(ans)

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

file = open(’file_B.txt’, ’rt’, encoding=’utf-8’)

n = int(file.readline())
ans = -1
maxim_krat_17 = [-1] * 29
maxim_nekrat_17 = [-1] * 29

for i in range(n):
    x = int(file.readline())
    ost = x % 29
    if x % 17 == 0:
        ans = max(ans, maxim_nekrat_17[ost] + x, maxim_krat_17[ost] + x)
        maxim_krat_17[ost] = max(maxim_krat_17[ost], x)
    else:
        ans = max(ans, maxim_krat_17[ost] + x)
        maxim_nekrat_17[ost] = max(maxim_nekrat_17[ost], x)
print(ans)

Ответ: 1967 1972

Ошибка.
Попробуйте повторить позже

Задача 3#29242

Дана последовательность из $N$ целых положительных чисел. Необходимо определить максимальное произведение пары элементов этой последовательности, произведение которой кратно $15$ , а сумма кратна $53$ .

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

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

Вложения к задаче

2_A.txt

2_B.txt

Показать ответ и решение

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

f = open("3.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]) % 15 == 0) and ((a[i] + a[j]) % 53 == 0):
            ans = max(ans, a[i] * a[j])
print(ans)

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

file = open(’3.txt’, ’rt’)
n = int(file.readline())
max_kr_15 = [0] * 53
max_kr_5 = [0] * 53
max_kr_3 = [0] * 53
max_nekr = [0] * 53

ans = 0

for i in range(n):
    x = int(file.readline())
    ost = x % 53
    dop = (53 - ost) % 53
    if x % 15 == 0:
        maxim = max(max_kr_15[dop], max_kr_5[dop],
                max_kr_3[dop], max_nekr[dop])
        ans = max(ans, x * maxim)
        max_kr_15[ost] = max(max_kr_15[ost], x)
    elif x % 5 == 0:
        maxim = max(max_kr_15[dop], max_kr_3[dop])
        ans = max(ans, x * maxim)
        max_kr_5[ost] = max(max_kr_5[ost], x)
    elif x % 3 == 0:
        maxim = max(max_kr_15[dop], max_kr_5[dop])
        ans = max(ans, x * maxim)
        max_kr_3[ost] = max(max_kr_3[ost], x)
    else:
        ans = max(ans, x * max_kr_15[dop])
        max_nekr[ost] = max(max_nekr[ost], x)
print(ans)

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

f = open(’2_B.txt’)

k = 53
p = 15
# Делители числа p
d = [15, 5, 3, 1]

n = int(f.readline())

# Создаём список, где индексы элемента nums[x][y] обозначают следующее:
# x - индекс делителя числа p, на которое делится элемент
# y - остаток от деления элемента на k
# Элементами же списка являются максимальные числа,
# делящиеся на определенный делитель числа p
# и имеющие определенный остаток от деления на k
nums = [[-10 ** 10] * k for _ in range(p + 1)]
mx = -10 ** 10

for i in range(n):
    x = int(f.readline())

    # Вычисляем остаток от деления на k числа-пары для x
    ost = (k - (x % k)) % k

    # Ищем наибольший делитель, на который делится x
    for j in d:
        if x % j == 0:
            # Обновляем максимум, умножая x на самое большое число,
            # при умножении x на которое их произведение будет кратно p
            mx = max(mx, x * nums[p // j][ost])
            break

    # Заполняем список максимальных чисел nums
    for j in d:
        if x % j == 0:
            # Если x больше предыдущего числа кратному dl с таким же
            # остатком от деления на k - обновляем число в списке
            nums[j][x % k] = max(nums[j][x % k], x)
                                                                                                     
                                                                                                     

print(mx)

Ответ: 2805 961380

Ошибка.
Попробуйте повторить позже

Задача 4#29431

На вход подаётся последовательность из $7 < n < 100000+ 1$ натуральных чисел, каждое из которых не больше $1000$ . Напишите программу, вычисляющую количество пар элементов последовательности, сумма которых делится на $5$ или $7$ , произведение кратно $6$ и хотя бы одно число из пары больше $40$ , находящихся на расстоянии не меньше $5$ .

Формат входных данных

В первой строке дано количество чисел $n$ , в каждой из последующих $n$ строк записано одно натуральное число, не превышающее $1000$ .

Формат выходных данных

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

Пример:

10

56

84

26

81

28

93

60

29

72

36

Ответом для примера будет: $2$

Вложения к задаче

3_A.txt

3_B.txt

Показать ответ и решение

Решение 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 + 5, n):
        if ((a[i] + a[j]) % 5 == 0) or ((a[i] + a[j]) % 7 == 0):
            if (a[i] * a[j]) % 6 == 0:
                if (a[i] > 40) or (a[j] > 40):
                    ans += 1
print(ans)

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

f = open(’3_B.txt’)

s = 5  # Расстояние между элементами
p = 6  # Чему должно быть кратно произведение
d = [6, 3, 2, 1]  # Делители числа p

n = int(f.readline())
x = [int(i) for i in f]

# Списки с количествами чисел, удовлетворяющих определенным условием
# Индексы числа nums_{k}[x][y][z] обозначают следующее:
# x - больше ли число чем 40 (0 - нет, 1 - да)
# y - делитель из списка d, которому кратно число
# z - остаток от деления числа на k
nums_5 = [[[0] * 5 for _ in range((p + 1))] for _ in range(2)]
nums_7 = [[[0] * 7 for _ in range((p + 1))] for _ in range(2)]
nums_35 = [[[0] * 35 for _ in range((p + 1))] for _ in range(2)]
cnt = 0

for i in range(s, n):
    # Элемент, находящийся на расстоянии s от текущего
    t = x[i - s]
    # Заполняем списки, увеличивая количества чисел по условиям
    for j in d:
        if t % j == 0:
            nums_5[int(t > 40)][j][t % 5] += 1
            nums_7[int(t > 40)][j][t % 7] += 1
            nums_35[int(t > 40)][j][t % 35] += 1

    # Вычисляем остатки от деления на {k}, которыми должны обладать пары для текущего числа
    ost_5 = (5 - (x[i] % 5)) % 5
    ost_7 = (7 - (x[i] % 7)) % 7
    ost_35 = (35 - (x[i] % 35)) % 35

    # Если текущее число больше 40, его можно ставить в пару с числами и больше и меньше 40
    if x[i] > 40:
        # Ищем наибольший делитель, на который делится текущее число
        for j in d:
            if x[i] % j == 0:
                # Вычисляем необходимый парный делитель для числа-пары
                dl = p // j
                # Количество чисел, которые делится на 5 или на 7, равносильно
                                                                                                     
                                                                                                     
                # сумме количества чисел, делящихся на 5, и количества чисел, делящихся на 7,
                # из которых вычли количество чисел, делящихся на 35
                for r in range(2):
                    cnt += nums_5[r][dl][ost_5] + nums_7[r][dl][ost_7] - nums_35[r][dl][ost_35]
                break
    # Если текущее число не больше 40, его можно ставить только в пары к числам больше 40
    else:
        for j in d:
            dl = p // j
            if x[i] % j == 0:
                cnt += nums_5[1][dl][ost_5] + nums_7[1][dl][ost_7] - nums_35[1][dl][ost_35]
                break

print(cnt)

Ответ: 9 6560792

Ошибка.
Попробуйте повторить позже

Задача 5#30009

Имеется набор данных из N натуральных чисел. Требуется найти наибольшую сумму пары, конкатенация которых будет являться палиндромом. Если такой суммы нет — напечатайте 0.

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

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

5

3

5

3

10

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

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

Вложения к задаче

27A.txt

27B.txt

Показать ответ и решение

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

f = open(’4_A.txt’)

n = int(f.readline())
x = [int(i) for i in f]
mx = 0

for i in range(n):
    for j in range(i + 1, n):
        s1 = str(x[i]) + str(x[j])
        s2 = str(x[j]) + str(x[i])
        if s1 == s1[::-1] or s2 == s2[::-1]:
            mx = max(mx, s1 + s2)

print(mx)

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

pali = []
for i in range(6):
    pali.append([str(i) for i in range(10**i, 10**(i+1)+1) if str(i) == str(i)[::-1]])
n = int(input())
mask = [0]*10000
for i in range(n):
    mask[int(input())] += 1
ans = 0
for k in range(10000):
    if mask[k] >= 1:
        s = str(k)
        for i in range(len(s)):
            s1 = s[i:len(s)][::-1]
            if s != s1:
                if mask[int(s1)] >= 1:
                    if s + s1 == (s + s1)[::-1]:
                        if int(s) + int(s1) > ans:
                            ans = int(s)+int(s1)
            else:
                if mask[int(s1)] >= 2:
                    if s + s1 == (s + s1)[::-1]:
                        ans = int(s)+int(s1)

        s1 = s[::-1]
        s2 = ’’
        for i in range(8-len(s + s1)):
            for j in range(len(pali[i])):
                s2 = pali[i][j] + s1
                if len(s2) > 4:
                    break
                if mask[int(s2)] >= 1:
                    if s + s2 == (s + s2)[::-1]:
                                                                                                     
                                                                                                     
                        if int(s)+int(s2) > ans:
                            ans = int(s)+int(s2)
print(ans)

Ответ: 0 15774

Ошибка.
Попробуйте повторить позже

Задача 6#30010

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

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

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

4

11

22

39

99

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

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

Вложения к задаче

27A.txt

27B.txt

Показать ответ и решение

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

f = open(’4_A.txt’)

n = int(f.readline())
x = [int(i) for i in f]
cnt = 0

for i in range(n):
    for j in range(i + 1, n):
        s1 = str(x[i])
        s2 = str(x[j])
        if s1 == s1[::-1] and s2 == s2[::-1]:
            cnt += 1

print(cnt)

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

n = int(input())
count_of_palis = 0  # Количество палиндромов
ans = 0
for i in range(n):
    x = int(input())
    if str(x) == str(x)[::-1]:
     # Если число - палиндром, оно образует пары со всеми ранее встреченными палиндромами
        ans += count_of_palis
        # Увеличиваем количество палиндромов
        count_of_palis += 1
print(ans)

Ответ: 1 5151

Ошибка.
Попробуйте повторить позже

Задача 7#36769

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

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

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

5

3

315

0

159

1

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

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

Вложения к задаче

fileA.txt

fileB.txt

Показать ответ и решение

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

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

print(cnt)

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

f = open(’6_B.txt’)
k = 53

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

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

print(cnt)

Ответ: 71 11796077645

Ошибка.
Попробуйте повторить позже

Задача 8#40793

В текстовом файле записан набор натуральных чисел, не превышающих $108$ . Гарантируется, что все числа различны. Из набора нужно выбрать три числа, так чтобы чисел, больших $1000$ было не более $2$ . Сколько троек, подходящих под условие задачи можно найти?

Первая строка входного файла содержит натуральное число $N$ — общее количество чисел в файле. Каждая из следующих $N$ строк содержит одно число.

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

$4$

$5$

$8$

$14$

$11$

Для данного примера в ответе нужно записать $4$ (подходят все тройки, т.к. ни в одной из них нет больше $2$ -х чисел, больших $1000$ ).

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

Вложения к задаче

27-A.txt

27-B.txt

Показать ответ и решение

Решение 1. Неэффективное

f = open("27-A.txt")
n = int(f.readline())
a = []
for i in range(n):
    a.append(int(f.readline()))
k = 0
for i in range(n):
    for j in range(i + 1, n):
        for l in range(j + 1, n):
            if (a[i] > 1000) + (a[j] > 1000) + (a[l] > 1000) <= 2:
                k += 1
print(k)

Решение 2. Эффективное. Динамика

f = open("27-B.txt")
n = int(f.readline())
pairs = [0] * 3
# pairs[i] - кол-во пар на свалке, где в паре i чисел > 1000
numbers = [0] * 2
# numbers[0] - кол-во чисел на свалке, которые <= 1000
# numbers[1] - кол-во чисел на свалке, которые > 1000
ans = 0
for i in range(n):
    x = int(f.readline())

    if x <= 1000:
        ans += pairs[0] + pairs[1] + pairs[2]
    else:
        ans += pairs[0] + pairs[1]

    t = x > 1000  # True(1),когда x > 1000, False(0) иначе

    for j in range(2):
        pairs[j + t] += numbers[j]

    numbers[t] += 1
print(ans)

Решение 3. Эффективное. Статика

f = open("27-B.txt")
n = int(f.readline())
more = 0
for i in range(n):
    x = int(f.readline())
    more += (x > 1000)
less = n - more
print(more * (more - 1) * less // 2 + more * less * (less - 1) // 2 + less * (less - 1) * (less - 2) // 6)
f.close()

Ответ: 9880 4999950000

Ошибка.
Попробуйте повторить позже

Задача 9#40794

В текстовом файле записан набор натуральных чисел, не превышающих $108$ . Гарантируется, что все числа различны. Из набора нужно выбрать три числа, так чтобы произведение чисел было кратно $27$ , а их сумма кратна $10$ . Сколько троек, подходящих под условие задачи можно найти?

Первая строка входного файла содержит натуральное число $N$ — общее количество чисел в файле. Каждая из следующих $N$ строк содержит одно число.

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

$4$

$3$

$8$

$12$

$15$

Для данного примера в ответе нужно записать $1$ (подходит тройка ( $3,12,15$ ). Произведение элементов тройки кратно $27$ , а их сумма кратна $10$ ).

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

Вложения к задаче

27-A.txt

27-B.txt

Показать ответ и решение

Решение 1. Неэффективное

f = open("27-A.txt")
n = int(f.readline())
a = []
for i in range(n):
    a.append(int(f.readline()))
k = 0
for i in range(n):
    for j in range(i + 1, n):
        for l in range(j + 1, n):
            if (((a[i] * a[j] *a[l]) % 27 == 0)
              and ((a[i] + a[j] + a[l]) % 10 == 0)):
                k += 1
print(k)

Решение 2. Эффективное. Динамика

f = open(’7_B.txt’)
n = int(f.readline())
a = [int(i) for i in f]

k = 10  # Чему должна быть кратна сумма
p = 27  # Чему должно быть кратно произведение
d = [27, 9, 3, 1]  # Делители числа p в порядке убывания

# Список с количествами чисел, удовлетворяющих определенным условием
# Индексы числа nums[x][y] обозначают следующее:
# x - максимальный делитель из списка d, которому кратно число
# y - остаток от деления числа на k
nums = [[0] * k for _ in range(p + 1)]

# Список с количествами пар чисел, удовлетворяющих определенным условием
# Индексы числа pairs[x][y] обозначают следующее:
# x - максимальный делитель из списка d, которому кратно произведение пары
# y - остаток от деления суммы чисел пары на k
pairs = [[0] * k for _ in range(p + 1)]

cnt = 0

for i in range(2, len(a)):
    ost1 = a[i - 2] % k # Остаток от деления на k первого числа тройки

    # Находим максимальный делитель из d, которому кратно число
    for dl in d:
        if a[i - 2] % dl == 0:
            # Увеличиваем количество чисел с такими характеристиками
            nums[dl][ost1] += 1
            break

    # Составляем со вторым числом пары с числами из всех возможных категорий делителей
    for dl_num in d:
        # Ищем максимальный делитель из d, которому кратно произведение пары
        for dl_pair in d:
            if (dl_num * a[i - 1]) % dl_pair == 0:
                # Увеличиваем количество пар для всех возможных остатков
                                                                                                     
                                                                                                     
                for j in range(k):
                    pairs[dl_pair][(j + a[i - 1]) % k] += nums[dl_num][j]
                break

    # Остаток, которым должна обладать сумма пары при делении на 10
    ost3 = (k - (a[i] % k)) % k

    # Составляем тройки со всеми подходящими под условие парами
    for dl_tr in d:
        if a[i] % dl_tr == 0:
            cnt += pairs[p // dl_tr][ost3]

print(cnt)

Ответ: 130 3452168965913

Ошибка.
Попробуйте повторить позже

Задача 10#40795

В текстовом файле записан набор натуральных чисел, не превышающих $108$ . Гарантируется, что все числа различны. Из набора нужно выбрать три числа, так чтобы произведение чисел было кратно $12$ , их сумма кратна $24$ и также ровно $2$ числа из тройки должны быть больше $128$ . Сколько троек, подходящих под условие задачи можно найти?

Первая строка входного файла содержит натуральное число $N$ — общее количество чисел в файле. Каждая из следующих $N$ строк содержит одно число.

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

$4$

$240$

$480$

$12$

$24$

Для данного примера в ответе нужно записать $1$ (подходит тройка ( $240,480,24$ ). Произведение элементов тройки кратно $12$ , их сумма кратна $24$ , и ровно $2$ числа больше $128$ ).

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

Вложения к задаче

27-A.txt

27-B.txt

Показать ответ и решение

Решение 1. Неэффективное

f = open("27-A.txt")
n = int(f.readline())
a = []
for i in range(n):
    a.append(int(f.readline()))
k = 0
for i in range(n):
    for j in range(i + 1, n):
        for l in range(j + 1, n):
            if (((a[i] * a[j] *a[l]) % 12 == 0)
              and ((a[i] + a[j] + a[l]) % 24 == 0)
              and ((a[i] > 128) + (a[j] > 128) + (a[l] > 128)) == 2):
                k += 1
print(k)

Решение 2. Эффективное. Динамика

f = open(’8_B.txt’)
n = int(f.readline())
a = [int(i) for i in f]

k = 24  # Чему должна быть кратна сумма
p = 12  # Чему должно быть кратно произведение
d = [12, 6, 4, 3, 2, 1]  # Делители числа p в порядке убывания

# Список с количествами чисел, удовлетворяющих определенным условием
# Индексы числа nums[x][y][z] обозначают следующее:
# x - больше ли число чем 128 (1 - да, 0 - нет)
# y - максимальный делитель из списка d, которому кратно число
# z - остаток от деления числа на k
nums = [[[0] * k for _ in range(p + 1)] for _ in range(2)]

# Список с количествами пар чисел, удовлетворяющих определенным условием
# Индексы числа pairs[x][y][z] обозначают следующее:
# x - количество чисел в паре больше 128
# y - максимальный делитель из списка d, которому кратно произведение пары
# z - остаток от деления суммы чисел пары на k
pairs = [[[0] * k for _ in range(p + 1)] for _ in range(3)]

cnt = 0

for i in range(2, len(a)):
    ost1 = a[i - 2] % k  # Остаток от деления на k первого числа тройки

    # Находим максимальный делитель из d, которому кратно число
    for dl in d:
        if a[i - 2] % dl == 0:
            # Увеличиваем количество чисел с такими характеристиками
            nums[int(a[i - 2] > 128)][dl][ost1] += 1
            break

    # Составляем со вторым числом пары с числами из всех возможных категорий делителей
    for dl_num in d:
        # Ищем максимальный делитель из d, которому кратно произведение пары
        for dl_pair in d:
                                                                                                     
                                                                                                     
            if (dl_num * a[i - 1]) % dl_pair == 0:
                # Увеличиваем количество пар для всех возможных остатков
                for j in range(k):
                    for h in range(2):
                        pairs[h + int(a[i - 1] > 128)][dl_pair][(j + a[i - 1]) % k] += nums[h][dl_num][j]
                break

    # Остаток, которым должна обладать сумма пары при делении на 10
    ost3 = (k - (a[i] % k)) % k

    # Составляем тройки со всеми подходящими под условие парами
    for dl_tr in d:
        if a[i] % dl_tr == 0:
            cnt += pairs[2 - int(a[i] > 128)][p // dl_tr][ost3]

print(cnt)

Ответ: 27 69909974

Ошибка.
Попробуйте повторить позже

Задача 11#45082

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

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

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

$5$

$90$

$2$

$10$

$40$

$3$

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

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

Вложения к задаче

27A.txt

27B.txt

Показать ответ и решение

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

f = open("9_A.txt")
n = int(f.readline())
a = []
for i in range(n):
    a.append(int(f.readline()))
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % 10 != 0 and (a[i] * a[j]) % 8 != 0:
            cnt += 1
print(cnt)

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

f = open(’9_B.txt’)

k = 10  # Чему НЕ должна быть кратна сумма
p = 8  # Чему НЕ должно быть кратно произведение
d = [8, 4, 2, 1]  # Делители числа p в порядке убывания

n = int(f.readline())

# Список с количествами чисел, удовлетворяющих определенным условием
# Индексы числа nums[x][y] обозначают следующее:
# x - максимальный делитель из списка d, которому кратно число
# y - остаток от деления числа на k
nums = [[0] * k for _ in range(p + 1)]
cnt = 0

for i in range(n):
    x = int(f.readline())

    # Вычисляем остаток от деления на k числа-пары для x
    ost = (k - (x % k)) % k

    # Увеличиваем ответ на количество пар с x,
    # произведение с которыми будет не кратно p, а сумма не кратна k
    for j in d:
        if (x * j) % p != 0:
            for h in range(k):
                if h != ost:
                    cnt += nums[j][h]

    # Находим максимальный делитель из d, которому кратно число
    for j in d:
        if x % j == 0:
            # Увеличиваем количество чисел с такими характеристиками
            nums[j][x % k] += 1
            break

print(cnt)

Ответ: 146 2596382100

Ошибка.
Попробуйте повторить позже

Задача 12#56887

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

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

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

Вложения к задаче

27A.txt

27B.txt

Показать ответ и решение

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

f = open("10_A.txt")
n = int(f.readline())
a = []
for i in range(n):
    a.append(int(f.readline()))
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[i] != a[j] and a[i] ** 0.5 == int(a[i] ** 0.5) and a[j] ** 0.5 == int(a[j] ** 0.5):
            cnt += 1
print(cnt)

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

f = open(’10_B.txt’)

n = int(f.readline())

# Список количеств чисел, где индекс равен корню из числа
# Например, под индексом 7 хранится количество чисел 49
nums = [0] * 101
count = 0  # Общее количество чисел-квадратов

ans = 0

for i in range(n):
    x = int(f.readline())
    # Проверяем, является ли текущее число полным квадратом
    if x ** 0.5 == int(x ** 0.5):
        # Так как числа должны быть разными, x составляет пары со всеми
        # встреченными до этого полными квадратами, кроме равных себе чисел
        ans += count - nums[int(x ** 0.5)]

        # Увеличиваем количество встреченных чисел x
        nums[int(x ** 0.5)] += 1
        # Увеличиваем общее количество квадратов
        count += 1

print(ans)

Ответ: 3 1231738

Ошибка.
Попробуйте повторить позже

Задача 13#56888

Дано число $N$ , затем $N$ натуральных чисел. Найдите количество пар элементов, где оба элемента будут являться различными числами, при этом хотя бы одно число является полным квадратом.

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

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

Вложения к задаче

27A.txt

27B.txt

Показать ответ и решение

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

f = open("11_A.txt")
n = int(f.readline())
a = []
for i in range(n):
    a.append(int(f.readline()))
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[i] != a[j] and (a[i] ** 0.5 == int(a[i] ** 0.5) or a[j] ** 0.5 == int(a[j] ** 0.5)):
            cnt += 1
print(cnt)

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

f = open(’11_B.txt’)

n = int(f.readline())

# Список количеств чисел, где индекс равен корню из числа
# Например, под индексом 7 хранится количество чисел 49
nums = [0] * 101
count = 0  # Общее количество квадратов

ans = 0

for i in range(n):
    x = int(f.readline())
    # Проверяем, является ли текущее число полным квадратом
    if x ** 0.5 == int(x ** 0.5):
        # Так как числа должны быть разными, x составляет пары со всеми
        # встреченными до этого числами, исключая самого себя
        ans += i - nums[int(x ** 0.5)]

        # Увеличиваем количество встреченных чисел x
        nums[int(x ** 0.5)] += 1
        # Увеличиваем общее количество квадратов
        count += 1
    else:
        # Если x не полный квадрат, он составляет пары со всеми квадратами
        ans += count

print(ans)

Ответ: 54 78484522

Ошибка.
Попробуйте повторить позже

Задача 14#56889

Дано число $N$ затем $N$ натуральных чисел. Найдите количество пар чисел, где произведение чисел будет кратно $8$ , но некратно $16$ , а сумма будет иметь остаток $4$ при делении на $10$ .

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

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

Вложения к задаче

27A.txt

27B.txt

Показать ответ и решение

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

f = open("12_A.txt")
n = int(f.readline())
a = []
for i in range(n):
    a.append(int(f.readline()))
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[i] * a[j] % 8 == 0 and a[i] * a[j] % 16 != 0 and (a[i] + a[j]) % 10 == 4:
            cnt += 1
print(cnt)

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

f = open(’12_B.txt’)

k = 10  # Остаток от деления на что должен быть равен 4
p = 8  # Чему должно быть кратно произведение
d = [8, 4, 2, 1]  # Делители числа p в порядке убывания

n = int(f.readline())

# Список с количествами чисел, удовлетворяющих определенным условием
# Индексы числа nums[x][y] обозначают следующее:
# x - максимальный делитель из списка d, которому кратно число
# y - остаток от деления числа на k
nums = [[0] * k for _ in range(p + 1)]
cnt = 0

for i in range(n):
    x = int(f.readline())

    # Вычисляем остаток от деления на k числа-пары для x
    ost = ((k + 4) - (x % k)) % k

    # Увеличиваем ответ на количество пар с x,
    # произведение с которыми будет кратно p, не кратно 16,
    # а сумма даст остаток 4 при делении на 10
    for j in d:
        if x % j == 0 and (x * (p // j)) % 16 != 0:
            cnt += nums[p // j][ost]

    # Находим максимальный делитель из d, которому кратно число
    for j in d:
        if x % j == 0:
            # Увеличиваем количество чисел с такими характеристиками
            nums[j][x % k] += 1
            break

print(cnt)

Ответ: 1 15769843

Ошибка.
Попробуйте повторить позже

Задача 15#63433

Имеется набор данных, состоящий из положительных целых чисел. Необходимо определить количество пар элементов $(ai,aj)$ этого набора, в которых $1 ≤ i < j ≤ N$ и сумма элементов нечётна, а произведение делится на 13.

Входные данные: Даны два входных файла (файл $A$ и файл $B$ ), каждый из которых содержит в первой строке количество чисел $N (1 ≤ N ≤ 100000).$ Каждая из следующих $N$ строк содержит натуральное число, не превышающее 1000.

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

5

4

13

27

39

7

Для указанных входных данных количество подходящих пар должно быть равно 2. В приведённом наборе имеются две пары (4, 13) и (4, 39), сумма элементов которых нечётна, и произведение кратно 13.

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

Вложения к задаче

27-4a.txt

27-4b.txt

Показать ответ и решение

Для А

s = open(’27-4a.txt’, ’r’).readlines()[1:]
arr = []
for i in range(len(s)):
    arr.append(int(s[i]))
n = len(arr)
cnt = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if (arr[i]*arr[j]) % 13 == 0 and (arr[i]+arr[j]) % 2 != 0:
            cnt += 1
print(cnt)

Для Б

f = open(’13_B.txt’)

k = 2  # Остаток от деления на что должен быть 1
p = 13  # Чему должно быть кратно произведение

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

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

print(cnt)

Ответ: 19 132286186

Ошибка.
Попробуйте повторить позже

Задача 16#63434

Дано число N, затем N натуральных чисел. Требуется найти максимальное четное произведение двух чисел кратное 27.

Входные данные: Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар $N (1 ≤ N ≤ 10000)$ . Каждая из следующих N строк содержит натуральное число, не превышающее 1000.

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

Вложения к задаче

27-5a.txt

27-5b.txt

Показать ответ и решение

Для А

s = open(’27-5a.txt’, ’r’).readlines()[1:]
arr = []
for i in range(len(s)):
    arr.append(int(s[i]))
print(arr)
n = len(arr)
mx = -1
for i in range(n - 1):
    for j in range(i + 1, n):
        if (arr[i]*arr[j]) % 27 == 0 and (arr[i]*arr[j]) % 2 == 0:
            mx = max(mx, arr[i]*arr[j])
print(mx)

Для Б

f = open(’14_B.txt’)

# Если произведение должно быть четным и кратным 27,
# значит оно должно быть кратно 27 * 2 = 54
p = 54
d = [54, 27, 18, 9, 6, 3, 2, 1]  # Делители числа p

n = int(f.readline())

# Создаём список, где индекс элемента nums[x] обозначает следующее:
# x - делитель числа p, на которое делится элемент
# Элементами же списка являются максимальные числа,
# делящиеся на определенный делитель числа p
nums = [-10 ** 10] * (p + 1)
mx = -10 ** 10

for i in range(n):
    x = int(f.readline())

    # Ищем наибольший делитель, на который делится x
    for j in d:
        if x % j == 0:
            # Обновляем максимум, умножая x на самое большое число,
            # при умножении x на которое их произведение будет кратно p
            mx = max(mx, x * nums[p // j])

    # Заполняем список максимальных чисел nums
    for j in d:
        if x % j == 0:
            # Если x больше предыдущего числа кратному dl
            nums[j] = max(nums[j], x)
            break

print(mx)

Варианты правильных ответов:

694710 999000

Ошибка.
Попробуйте повторить позже

Задача 17#63855

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

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

Вложения к задаче

27A_9.txt

27B_9.txt

Показать ответ и решение

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

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

print(cnt)

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

f = open(’15_B.txt’)

k = 2  # Остаток от деления на что должен быть 1
p = 7  # Чему должно быть кратно произведение

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

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

print(cnt)

Ответ: 601 6916429

27.07 Макс/мин, кол-во пар, смешаное кратно/не кратно