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

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

Задача 1#17970

Дано число $N$ и $N$ натуральных чисел. Каждое число находится в диапазоне от $0$ до $10$ $000$ . Напишите программу, которая находит количество пар чисел, произведение элементов которых кратно 8, находящихся на расстоянии не менее 8.

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

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

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

3_A.txt

3_B.txt

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

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

f = open(’3_A.txt’)

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

for i in range(n):
    for j in range(i + 1, n):
        if (a[i] * a[j]) % 8 == 0 and j - i >= 8:
            cnt += 1

print(cnt)

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

f = open(’3_A.txt’)

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

ans = 0

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

# Список количеств чисел, делящихся на определенный делитель числа p
# Например, под индексом 2 хранится кол-во чисел, делящихся на 2
nums = [0] * (p + 1)

for i in range(s, n):
    # Ищем максимальный делитель, на который делится первое число пары
    for j in d:
        if a[i - s] % j == 0:
            # Увеличиваем кол-во чисел делящихся на j
            nums[j] += 1
            break

    # Ищем делители, на которые делится второе число пары
    for j in d:
        if a[i] % j == 0:
            # Увеличиваем ответ на количество образованных пар
            ans += nums[p // j]

print(ans)

Ответ: 34 1562518770

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

Задача 2#20541

На вход подается число $2 < n ≤ 100000$ , а затем последовательность из $n$ натуральных чисел. Напишите программу, которая находит максимальное произведение двух элементов последовательности, стоящих на расстоянии не меньше 4, то есть $|i− j| ≥ 4$ , где $i ⁄= j$ - номера элементов последовательности.

В первой строке файла “ $27 1$ .txt” находится число $n$ , в следующих $n$ строках даны элементы последовательности. Гарантируется, что искомое произведение получить можно.

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

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

27_1.txt

27_A.txt

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

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

f = open(’4_A.txt’)

n = int(f.readline())
a = [int(i) for i in f]
mx = -10 ** 10

for i in range(n):
    for j in range(i + 1, n):
        if j - i >= 4:
            mx = max(mx, a[i] * a[j])

print(mx)

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

f = open(’4_B.txt’)

n = int(f.readline())
a = [int(i) for i in f]
ans = -10 ** 10

s = 4  # Расстояние между элементами

# Максимальное найденное на данный момент число
mx_prev = -10 ** 10

for i in range(s, n):
    mx_prev = max(mx_prev, a[i - s])
    ans = max(ans, a[i] * mx_prev)

print(ans)

Ответ: 997002 7673820

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

Задача 3#20542

На вход подается число $2 < n ≤ 100000$ , а затем последовательность из $n$ натуральных чисел. Напишите программу, которая находит минимальную четную сумму двух элементов последовательности, стоящих на расстоянии не меньше 6, то есть $|i− j| ≥ 6$ , где $i ⁄= j$ - номера элементов последовательности.

В первой строке файла “ $27 2$ .txt” находится число $n$ , в следующих $n$ строках даны элементы последовательности. Гарантируется, что искомую сумму получить можно.

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

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

5_A.txt

5_B.txt

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

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

f = open(’5_A.txt’)

n = int(f.readline())
a = [int(i) for i in f]
ans = 10 ** 10

for i in range(n):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % 2 == 0 and j - i >= 6:
            ans = min(ans, a[i] + a[j])

print(ans)

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

f = open(’5_B.txt’)

n = int(f.readline())
a = [int(i) for i in f]
ans = 10 ** 10

k = 2  # Чему должна быть кратна сумма
s = 6  # Расстояние между элементами

# Список минимальных чисел с определенными остатками от деления на k
# Например, под индексом 1 хранится минимальное число с остатком 1
nums = [10 ** 10] * k

for i in range(s, n):
    # Считаем остаток от деления первого числа пары на k
    ost1 = a[i - s] % k
    # Обновляем минимум по остатку
    nums[ost1] = min(nums[ost1], a[i - s])

    # Считаем остаток, который должен быть у числа,
    # которое можно поставить в пару с текущим
    ost2 = (k - (a[i] % k)) % k
    # Обновляем ответ, если он меньше предыдущего
    ans = min(ans, a[i] + nums[ost2])

print(ans)

Ответ: 6 1072

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

Задача 4#20543

На вход подается число $2 < n ≤ 100000$ , а затем последовательность из $n$ натуральных чисел. Напишите программу, которая находит количество пар элементов последовательности, сумма которых делится на 5, при условии, что элементы стоят на расстоянии не меньше 3, то есть $|i− j| ≥ 3$ , где $i ⁄= j$ - номера элементов последовательности.

В первой строке файла “ $27 3$ .txt” находится число $n$ , в следующих $n$ строках даны элементы последовательности. Найдите количество пар, удовлетворяющих условию.

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

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

6_A.txt

6_B.txt

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

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

f = open(’6_A.txt’)

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

for i in range(n):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % 5 == 0 and j - i >= 3:
            cnt += 1

print(cnt)

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

f = open(’6_B.txt’)

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

k = 5  # Чему должна быть кратна сумма
s = 3  # Расстояние между элементами

# Список количеств чисел с определенными остатками от деления на k
# Например, под индексом 3 хранится кол-во чисел с остатком 3
nums = [0] * k

for i in range(s, n):
    # Считаем остаток от деления первого числа пары на k
    ost1 = a[i - s] % k
    # Увеличиваем кол-во чисел с найденным остатком
    nums[ost1] += 1

    # Считаем остаток, который должен быть у числа,
    # которое можно поставить в пару с текущим
    ost2 = (k - (a[i] % k)) % k
    # Увеличиваем ответ на количество образованных пар
    cnt += nums[ost2]

print(cnt)

Ответ: 99731 999991557

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

Задача 5#20544

На вход подается число $2 < n ≤ 100000$ , а затем последовательность из $n$ натуральных чисел. Напишите программу, которая находит количество пар элементов последовательности, сумма которых нечетна, а произведение четно, при условии, что элементы стоят на расстоянии не меньше 7, то есть $|i− j| ≥ 7$ , где $i ⁄= j$ - номера элементов последовательности.

В первой строке файла “ $27 4$ .txt” находится число $n$ , в следующих $n$ строках даны элементы последовательности. Найдите количество пар, удовлетворяющих условию.

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

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

7_A.txt

7_B.txt

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

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

f = open(’7_A.txt’)

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

for i in range(n):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % 2 != 0 and (a[i] * a[j]) % 2 == 0 and j - i >= 7:
            cnt += 1

print(cnt)

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

f = open(’7_B.txt’)

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

k = 2  # Чему должна быть кратно произведение
s = 7  # Расстояние между элементами

# Список количеств чисел с определенными остатками от деления на k
# Например, под индексом 3 хранится кол-во чисел с остатком 3
nums = [0] * k

for i in range(s, n):
    # Считаем остаток от деления первого числа пары на k
    ost1 = a[i - s] % k
    # Увеличиваем кол-во чисел с найденным остатком
    nums[ost1] += 1

    # Считаем остаток, который должен быть у числа,
    # которое можно поставить в пару с текущим
    # Только у двух чисел разной четности сумма будет
    # нечетной, а произведение четным
    ost2 = int(not a[i] % 2)
    # Увеличиваем ответ на количество образованных пар
    cnt += nums[ost2]

print(cnt)

Ответ: 246988 2499699115

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

Задача 6#20545

На вход подается число $2 < n ≤ 100000$ , а затем последовательность из $n$ натуральных чисел. Напишите программу, которая находит количество пар элементов, произведение которых кратно 6, а сумма кратна 5, при условии, что элементы стоят на расстоянии не меньше 5, то есть $|i− j| ≥ 5$ , где $i ⁄= j$ - номера элементов последовательности.

В первой строке файла “ $27 5$ .txt” находится число $n$ , в следующих $n$ строках даны элементы последовательности. Найдите количество пар элементов, удовлетворяющих условию.

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

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

8_A.txt

8_B.txt

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

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

f = open("8_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] % 6 == 0 and (a[i] + a[j]) % 5 == 0 and j - i >= 5:
            cnt += 1
print(cnt)

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

f = open(’8_B.txt’)

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

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

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

for i in range(s, n):
    # Находим остаток первого числа пары
    ost1 = a[i - s] % k
    # Находим максимальный делитель из d, которому кратно число
    for j in d:
        if a[i - s] % j == 0:
            # Увеличиваем количество чисел с такими характеристиками
            nums[j][ost1] += 1
            break

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

    # Увеличиваем ответ на количество пар с x,
    # произведение с которыми будет кратно p,
    # а сумма будет кратна k
    for j in d:
        if a[i] % j == 0:
            cnt += nums[p // j][ost2]

print(cnt)

Ответ: 419650359

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

Задача 7#20796

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

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

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

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

27_A.txt

27_B.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] > 21 or a[j] > 21) and (a[i] + a[j]) % 74 == 0 and j - i >= 5:
            cnt += 1
print(cnt)

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

f = open(’9_B.txt’)

s = 5  # Расстояние между элементами
k = 74  # Чему должна быть кратна сумма

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

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

for i in range(s, n):
    # Находим остаток первого числа пары
    ost1 = a[i - s] % k
    # Увеличиваем количество чисел с такими характеристиками
    nums[int(a[i - s] > 21)][ost1] += 1

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

    # Увеличиваем ответ на количество пар с x, сумма которых будет кратна k,
    # где первое число точно больше 21
    cnt += nums[1][ost2]
    # Если a[i] больше 21, то его можно поставить также в пару с числами меньше 21
    if a[i] > 21:
        cnt += nums[0][ost2]

print(cnt)

Ответ: 7 60734833253

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

Задача 8#20797

На вход подаётся последовательность из $9 < n ≤ 100000$ натуральных чисел, каждое из которых не больше $1000$ . Напишите программу, вычисляющую количество пар элементов последовательности, сумма которых делится на $7$ , произведение не кратно $15$ , и хотя бы одно число из пары больше $50$ , находящихся на расстоянии не меньше $8$ .

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

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

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


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

10	1
100
85
94
49
92
29
48
27
61
29

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

27_A.txt

27_B.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] > 50 or a[j] > 50) and (a[i] + a[j]) % 7 == 0 and (a[i] * a[j]) % 15 != 0 and j - i >= 8:
            cnt += 1
print(cnt)

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

f = open(’10_B.txt’)

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

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

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

for i in range(s, n):
    # Находим остаток первого числа пары
    ost1 = a[i - s] % k

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

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

    # Перебираем все возможные делители и ищем те, при которых произведение
    # не будет кратно 15
    for j in d:
        if (a[i] * j) % 15 != 0:
            # Увеличиваем ответ на количество пар с x, сумма которых будет кратна k,
            # где первое число точно больше 50
                                                                                                     
                                                                                                     
            cnt += nums[1][j][ost2]
            # Если a[i] больше 50, то его можно поставить также в пару с числами меньше 50
            if a[i] > 50:
                cnt += nums[0][j][ost2]

print(cnt)

Ответ: 30 5715135

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

Задача 9#21174

В файле 5.txt имеется набор данных, состоящий из положительных целых чисел. Необходимо определить количество пар элементов ( $ai$ , $aj$ ) этого набора, в которых $i+ 3 ≤ j ≤ N$ и произведение элементов кратно $26$ . В ответе через пробел напишите искомое количество для файла А и для файла Б.

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

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

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

10

2

1

9

13

6

8

9

2

14

26

Для указанных входных данных ответом является число $10$ .

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

5.txt

27B.txt

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

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

f = open(’11_A.txt’)

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

for i in range(n):
    for j in range(i + 1, n):
        if (a[i] * a[j]) % 26 == 0 and j - i >= 3:
            cnt += 1

print(cnt)

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

f = open(’11_B.txt’)

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

ans = 0

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

# Список количеств чисел, делящихся на определенный делитель числа p
# Например, под индексом 2 хранится кол-во чисел, делящихся на 2
nums = [0] * (p + 1)

for i in range(s, n):
    # Ищем максимальный делитель, на который делится первое число пары
    for j in d:
        if a[i - s] % j == 0:
            # Увеличиваем кол-во чисел делящихся на j
            nums[j] += 1
            break

    # Ищем делители, на которые делится второе число пары
    for j in d:
        if a[i] % j == 0:
            # Увеличиваем ответ на количество образованных пар
            ans += nums[p // j]

print(ans)

Ответ: 11 465412050

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

Задача 10#29462

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

На вход подаётся последовательность из $9 < N ≤ 100000$ натуральных чисел, каждое из которых не больше 1000. Напишите программу, вычисляющую количество пар элементов последовательности, сумма которых делится на 4, произведение кратно 14 и ровно одно число из пары больше 60, находящихся на расстоянии не меньше 8.

Программа должна напечатать одно число — вычисленное значение, соответствующую условиям задачи.

Входные файлы:

Файл 27 A

Файл 27 B

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

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

10

78

50

69

90

60

74

50

44

42

Для указанных входных данных искомым значением должно быть 2.

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

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

Задание 27 A.txt

Задание 27 B.txt

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

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

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] > 60) != (a[j] > 60)) and (a[i] + a[j]) % 4 == 0 and (a[i] * a[j]) % 14 == 0 and j - i >= 8:
            cnt += 1
print(cnt)

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

f = open(’12_B.txt’)

s = 8  # Расстояние между элементами
k = 4  # Чему должна быть кратна сумма
p = 14  # Чему должно быть кратно произведение
d = [14, 7, 2, 1]

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

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

for i in range(s, n):
    # Находим остаток первого числа пары
    ost1 = a[i - s] % k

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

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

    # Перебираем все возможные делители и ищем те, при которых произведение будет кратно 15
    for j in d:
        if a[i] % j == 0:
            # Увеличиваем ответ на количество пар с x, сумма которых будет кратна k,

            # Если a[i] больше 50, то его можно поставить в пару с числами меньше 60
                                                                                                     
                                                                                                     
            if a[i] > 60:
                cnt += nums[0][p // j][ost2]
            # Иначе только с числами больше 60
            else:
                cnt += nums[1][p // j][ost2]

print(cnt)

Ответ: 1 169322

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

Задача 11#29985

На вход программы поступает последовательность из $N$ натуральных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов, находящихся на расстоянии не меньше чем $4$ (разница в индексах элементов пары должна быть $4$ или более, порядок элементов в паре неважен). Необходимо найти максимальное произведение пар кратное $5$ .

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

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

5

7

4

3

7

Для таких входных данных значением искомое суммы будет число 35

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

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

27A.txt

27B.txt

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

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

f = open(’13_A.txt’)

n = int(f.readline())
a = [int(i) for i in f]
ans = -10 ** 10

for i in range(n):
    for j in range(i + 1, n):
        if (a[i] * a[j]) % 5 == 0 and j - i >= 4:
            ans = max(ans, a[i] * a[j])

print(ans)

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

f = open(’13_B.txt’)

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

ans = 0

s = 4  # Расстояние между элементами
p = 5  # Чему должно быть кратно произведение

# Список максимальных чисел, где индекс обозначает кратность 5
# 1 - кратно, 0 - не кратно
nums = [0] * (p + 1)

for i in range(s, n):
    # Обновляем список, если первое число из пары больше предыдущего такого
    nums[int(a[i - s] % 5 == 0)] = max(nums[int(a[i - s] % 5 == 0)], a[i - s])

    # Обновляем ответ, если он больше предыдущего
    # Мы можем поставить текущее число к любому кратному 5
    ans = max(ans, a[i] * nums[1])
    if a[i] % 5 == 0:
        # А также к любому не кратному, если само текущее число кратно 5
        ans = max(ans, a[i] * nums[0])

print(ans)

Ответ: 2321000 99820045

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

Задача 12#29986

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

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

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

8

6

10

15

33

35

7

13

39

Для таких входных данных значением искомое суммы будет число 45

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

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

27A.txt

27B.txt

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

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

f = open(’14_A.txt’)

n = int(f.readline())
a = [int(i) for i in f]
ans = -10 ** 10

for i in range(n):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % 9 == 0 and j - i >= 7:
            ans = max(ans, a[i] + a[j])

print(ans)

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

f = open(’14_B.txt’)

n = int(f.readline())
a = [int(i) for i in f]
ans = -10 ** 10

k = 9  # Чему должна быть кратна сумма
s = 7  # Расстояние между элементами

# Список максимальных чисел с определенными остатками от деления на k
# Например, под индексом 3 хранится кол-во чисел с остатком 3
nums = [-10 ** 10] * k

for i in range(s, n):
    # Считаем остаток от деления первого числа пары на k
    ost1 = a[i - s] % k
    # Обновляем минимум по остатку
    nums[ost1] = max(nums[ost1], a[i - s])

    # Считаем остаток, который должен быть у числа,
    # которое можно поставить в пару с текущим
    ost2 = (k - (a[i] % k)) % k
    # Обновляем ответ, если он больше предыдущего
    ans = max(ans, a[i] + nums[ost2])

print(ans)

Ответ: 3321 19989

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

Задача 13#29987

На вход программы поступает последовательность из N натуральных чисел, все числа в последовательности различны. Необходимо найти количество всех пар различных элементов, находящихся на расстоянии не менее 3, чтобы их произведение было нечетным, а сумма кратна 61. Если таких пар нет — в ответе укажите 0.

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

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

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

27A.txt

27B.txt

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

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

f = open(’15_A.txt’)

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

for i in range(n):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % 61 == 0 and (a[i] * a[j]) % 2 != 0 and j - i >= 3:
            cnt += 1

print(cnt)

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

f = open(’15_B.txt’)

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

k = 61  # Чему должна быть кратна сумма
s = 3  # Расстояние между элементами

# Список количеств чисел с определенными остатками от деления на k
# Например, под индексом 3 хранится кол-во чисел с остатком 3
nums = [0] * k

for i in range(s, n):
    # Чтобы произведение было нечетным, оба числа должны быть нечетными
    # поэтому работаем только с нечетными числами

    if a[i - s] % 2 != 0:
        # Считаем остаток от деления первого числа пары на k
        ost1 = a[i - s] % k
        # Увеличиваем кол-во чисел с найденным остатком
        nums[ost1] += 1

    if a[i] % 2 != 0:
        # Считаем остаток, который должен быть у числа,
        # которое можно поставить в пару с текущим
        ost2 = (k - (a[i] % k)) % k
        # Увеличиваем ответ на количество образованных пар
        cnt += nums[ost2]

print(cnt)

Ответ: 0 51225

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

Задача 14#29989

На вход программы поступает последовательность из N натуральных чисел. Необходимо найти такую пару различных элементов последовательности, находящихся на расстоянии не менее 4, чтобы их произведение было максимально и кратно 3, сумма кратна 8 и хотя бы один элемент пары был больше 30.

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

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

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

27A.txt

27B.txt

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

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

f = open("16_A.txt")
n = int(f.readline())
a = [int(i) for i in f]
ans = -10 ** 10
for i in range(n):
    for j in range(i + 1, n):
        if a[i] * a[j] % 3 == 0 and (a[i] + a[j]) % 8 == 0:
            if (a[i] > 30 or a[j] > 30) and j - i >= 4:
                ans = max(ans, a[i] * a[j])
print(ans)

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

f = open(’27.txt’)
kr_3 = [[0] * 8, [0] * 8] # первая ячейка --- > или <= 30, вторая ячейка --- остатки от деления на 8
nekr_3 = [[0] * 8, [0] * 8]
n = int(f.readline())
line = []
for i in range(3):
    line.append(int(f.readline()))
ans = 0
for i in range(n - 3):
    x = int(f.readline())
    dop = (8 - x % 8) % 8
    # числа больше 30 можно использовать всегда, поэтому используем if только для тех, что <= 30
    ans = max(ans, kr_3[0][dop] * x, nekr_3[0][dop] * x * (x % 3 == 0))
    if x > 30:
        ans = max(ans, kr_3[1][dop] * x, nekr_3[1][dop] * x * (x % 3 == 0))
    t = line[i % 3]
    if t % 3 == 0:
        kr_3[t <= 30][t % 8] = max(t, kr_3[t <= 30][t % 8])
    else:
        nekr_3[t <= 30][t % 8] = max(t, nekr_3[t <= 30][t % 8])
    line[i % 3] = x
print(ans)

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

f = open(’16_B.txt’)

s = 4  # Расстояние между элементами
k = 8  # Чему должна быть кратна сумма
p = 3  # Чему должно быть кратно произведение

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

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

for i in range(s, n):
    # Находим остаток первого числа пары
    ost1 = a[i - s] % k
    # Обновляем число в списке с такими же характеристиками
    nums[int(a[i - s] > 30)][int(a[i - s] % 3 == 0)][ost1] = max(
        nums[int(a[i - s] > 30)][int(a[i - s] % 3 == 0)][ost1],
        a[i - s]
    )

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

    ans = max(ans, a[i] * nums[1][1][ost2])
    if a[i] % 3 == 0:
        ans = max(ans, a[i] * nums[1][0][ost2])
        if a[i] > 30:
            ans = max(ans, a[i] * nums[0][0][ost2])
    if a[i] > 30:
        ans = max(ans, a[i] * nums[0][1][ost2])

print(ans)

Ответ: 101103 99920016

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

Задача 15#29990

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

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

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

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

27A.txt

27B.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 + 3, n):
        if (a[i] * a[j]) % 8 == 0:
            if (a[i] < 100) or (a[j] < 100):
                ans = max(ans, a[i] + a[j])
print(ans)

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

f = open(’17_B.txt’)

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

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

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

for i in range(s, n):
    # Получаем индекс для первого критерия
    ind = int(a[i - s] < 100)
    # Ищем максимальный делитель, которому кратно число
    for j in d:
        if a[i - s] % j == 0:
            # Обновляем максимальное число с такими характеристиками
            nums[ind][j] = max(nums[ind][j], a[i - s])
            break

    # Перебираем все возможные делители и ищем те, при которых произведение будет кратно 8
    for j in d:
        if a[i] % j == 0:
            # Обновляем ответ, если новая сумма больше прошлой
            ans = max(ans, a[i] + nums[1][p // j])

            # Если a[i] меньше 100, то его можно поставить в пару с числами больше 100
            if a[i] < 100:
                ans = max(ans, a[i] + nums[0][p // j])

print(ans)

Ответ: 1050 10093

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

Задача 16#29991

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

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

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

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

27A.txt

27B.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 + 6, n):
        if (
            ((a[i] + a[j]) % 8 == 0)
            and ((a[i] * a[j]) % 4 == 0)
            and ((a[i] * a[j]) in a)
        ):
            ans += 1
print(ans)

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

f = open("27B.txt")
n = int(f.readline())
ans = 0

# Список с количествами чисел, удовлетворяющих определенным условием
# Индексы числа nums[x][y][z] обозначают следующее:
# x - максимальный делитель 4, которому кратно число
# y - остаток от деления числа на 8
# z - индекс числа в этом списке
k = [[], [], [], [], []]
for i in range(5):
    for j in range(8):
        k[i].append([])

a = [int(f.readline()) for i in range(n)]
# Превращаем a во множество, чтобы быстрее проверять наличие произведений
s = set(a)
line = [a[i] for i in range(5)]
for i in range(5, n):
    x = a[i]
    # Вычисляем остаток, который должен быть у пары
    d = (8 - x % 8) % 8
    # Ищем делители, при умножении на которые произведение будет кратно 4
    for j in range(1, 5):
        if 4 % j == 0 and x * j % 4 == 0:
            # Проходимся по всем элементам с такими характеристиками
            for elem in k[j][d]:
                # Если такое произведение есть в последовательности - считаем его
                if (elem * x) in s:
                    ans += 1
    # Новый элемент на нужном расстоянии
    t = line[i % 5]
    # Определяем максимальный делитель, на который делится элемент
    z = max(j for j in range(1, 5) if 4 % j == 0 and t % j == 0)
    # Сохраняем этот элемент
    k[z][t % 8].append(t)
    # Добавляем его в очередь
    line[i % 5] = x
                                                                                                     
                                                                                                     
print(ans)

Ответ: 0 198

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

Задача 17#30011

Дано натуральное число N, затем N натуральных чисел. Требуется найти количество пар чисел, чья сумма будет кратна 10. Парой считаются два элемента, расстояние между которыми равно 3 и более (т.е. разница между их индексами >= 3).

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

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

$7$

$10$

$20$

$30$

$40$

$50$

$60$

$70$

Подходящими парами будут являться: (10, 40), (10, 50), (10, 60), (10, 70), (20, 50), (20, 60), (20, 70), (30, 60), (30, 70), (40, 70) и ответом будет являться 10.

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

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

27A.txt

27B.txt

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

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

f = open(’1_A.txt’)

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

for i in range(n):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % 10 == 0 and j - i >= 3:
            cnt += 1

print(cnt)

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

f = open(’1_B.txt’)

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

k = 10  # Чему должна быть кратна сумма
s = 3  # Расстояние между элементами

# Список количеств чисел с определенными остатками от деления на k
# Например, под индексом 3 хранится кол-во чисел с остатком 3
nums = [0] * k

for i in range(s, n):
    # Считаем остаток от деления первого числа пары на k
    ost1 = a[i - s] % k
    # Увеличиваем кол-во чисел с найденным остатком
    nums[ost1] += 1

    # Считаем остаток, который должен быть у числа,
    # которое можно поставить в пару с текущим
    ost2 = (k - (a[i] % k)) % k
    # Увеличиваем ответ на количество образованных пар
    cnt += nums[ost2]

print(cnt)

Ответ: 13 249001

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

Задача 18#38460

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

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

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

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

27A.txt

27B.txt

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

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

f = open("19_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] < 35 or a[j] < 35) and (a[i] + a[j]) % 13 == 0 and j - i >= 3:
            cnt += 1
print(cnt)

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

f = open(’19_B.txt’)

s = 3  # Расстояние между элементами
k = 13  # Чему должна быть кратна сумма

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

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

for i in range(s, n):
    # Находим остаток первого числа пары
    ost1 = a[i - s] % k
    # Увеличиваем количество чисел с такими характеристиками
    nums[int(a[i - s] < 35)][ost1] += 1

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

    # Увеличиваем ответ на количество пар с x, сумма которых будет кратна k,
    # где первое число точно меньше 35
    cnt += nums[1][ost2]
    # Если a[i] меньше 35, то его можно поставить также в пару с числами больше 35
    if a[i] < 35:
        cnt += nums[0][ost2]

print(cnt)

Ответ: 1 6542

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

Задача 19#42772

На вход подается число $N$ , а затем последовательность из $N$ натуральных чисел. Напишите программу, которая находит минимальную четную сумму двух элементов последовательности, стоящих на расстоянии не меньше $3$ , то есть $|i− j| ≥ 3$ , где $i ⁄= j$ - номера элементов последовательности.

В первой строке файла находится число $N$ , в следующих $N$ строках даны элементы последовательности, целые положительные числа. Гарантируется, что искомую сумму получить можно.

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

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

20_A.txt

20_B.txt

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

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

f = open(’20_A.txt’)

n = int(f.readline())
a = [int(i) for i in f]
ans = 10 ** 10

for i in range(n):
    for j in range(i + 1, n):
        if (a[i] + a[j]) % 2 == 0 and j - i >= 3:
            ans = min(ans, a[i] + a[j])

print(ans)

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

f = open(’20_B.txt’)

n = int(f.readline())
a = [int(i) for i in f]
ans = 10 ** 10

k = 2  # Чему должна быть кратна сумма
s = 3  # Расстояние между элементами

# Список минимальных чисел с определенными остатками от деления на k
# Например, под индексом 1 хранится минимальное число с остатком 1
nums = [10 ** 10] * k

for i in range(s, n):
    # Считаем остаток от деления первого числа пары на k
    ost1 = a[i - s] % k
    # Обновляем минимум по остатку
    nums[ost1] = min(nums[ost1], a[i - s])

    # Считаем остаток, который должен быть у числа,
    # которое можно поставить в пару с текущим
    ost2 = (k - (a[i] % k)) % k
    # Обновляем ответ, если он меньше предыдущего
    ans = min(ans, a[i] + nums[ost2])

print(ans)

Ответ: 20 936

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

Задача 20#42775

На вход подается число $N$ , а затем последовательность из $N$ натуральных чисел. Напишите программу, которая находит количество пар элементов, произведение которых кратно $12$ , а сумма кратна $15$ , при условии, что элементы стоят на расстоянии не меньше $5$ , то есть $|i− j| ≥ 5$ , где $i ⁄= j$ - номера элементов последовательности.

В первой строке файла находится число $N$ , в следующих $N$ строках даны элементы последовательности, целые положительные числа.

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

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

21_A.txt

21_B.txt

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

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

f = open("21_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] % 12 == 0 and (a[i] + a[j]) % 15 == 0 and j - i >= 5:
            cnt += 1
print(cnt)

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

f = open(’21_B.txt’)

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

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

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

for i in range(s, n):
    # Находим остаток первого числа пары
    ost1 = a[i - s] % k
    # Находим максимальный делитель из d, которому кратно число
    for j in d:
        if a[i - s] % j == 0:
            # Увеличиваем количество чисел с такими характеристиками
            nums[j][ost1] += 1
            break

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

    # Увеличиваем ответ на количество пар с x,
    # произведение с которыми будет кратно p,
    # а сумма будет кратна k
    for j in d:
        if a[i] % j == 0:
            cnt += nums[p // j][ost2]

print(cnt)

Ответ: 2 55276926

27.08 Макс/мин, кол-во пар, сумма/разность/произведение кратно/не кратно на расстоянии