desktop/inf.jpg mobile/inf.jpg

Задание 27. Программирование. Оптимизация по времени и памяти. ЕГЭ 2023 по информатике

За это задание ты можешь получить 2 балла. На решение дается около 55 минут. Уровень сложности: высокий.
Средний процент выполнения: 14.3%
Ответом к заданию 27 по информатике может быть развернутый ответ (полная запись решения с обоснованием выполненных действий).
Разбор сложных заданий в тг-канале

Задачи для практики

Задача 1

ДЛЯ 2022

На кольцевой дороге с двусторонним движением установлены магазины для продажи яблок. Все магазины находятся на расстоянии 1 километра друг от друга. Специальные роботы доставщики развозят яблоки со склада по этим магазинам. Длина кольцевой дороги равна N километров. Нулевой километр и N-й километр автодороги находятся в одной точке. Известно количество килограмм яблок, которое необходимо ежедневно доставлять в каждый из магазинов. Для каждого пункта яблоки возит отдельный робот доставщик. Стоимость доставки яблок вычисляется как произведение количества яблок (в килограммах) на расстояние от склада до магазина. Склад открыли в одном из магазинов таким образом, чтобы общая стоимость доставки яблок во все магазины была минимальной.

Определите минимальные расходы на доставку яблок в магазины.

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

Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество магазинов на кольцевой дороге. В каждой из следующих N строк находится число – количество килограмм яблок, необходимых для доставки в магазин (все числа натуральные, количество килограмм не превышает 1000). Числа указаны в порядке расположения магазинов на дороге, начиная с первого километра.

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

Типовой пример организации данных во входном файле

6
8
20
5
13
7
19

При таких исходных данных, если магазины установлены на каждом километре дороги, необходимо открыть склад в пункте 6. В этом случае сумма затрат на доставку составит:

1 · 7 + 0 · 19 + 1 · 8 + 2 · 20 + 3 · 5 + 2 · 13.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Решение

Для решения этого номера составим программу на языке Python

f = open('27_B.txt', 'r')
n = int(f.readline().strip())
x = [int(line) for line in f]
right = 0
left = x[0]
sum_all = 0
for i in range(1, n // 2):
    sum_all += i * x[i] + i * x[-i]
    right += x[i]
    left += x[-i]
sum_all += (n // 2) * x[n // 2]
right += x[n // 2]

min_sum = sum_all
for i in range(1, n):
    sum_all = sum_all - right + left
    right = right + x[(n // 2 + i) % n] - x[i]
    left = left + x[i] - x[(n // 2 + i) % n]
    min_sum = min(min_sum, sum_all)

print(min_sum)

ОТВЕТ: А - 157076, В - 16371318320559

Ответ:
Показать решение
Полный курс

Задача 2

Имеется набор данных, состоящий из положительных целых чисел, все числа не превышают 10000. Количество чисел известно, но может быть очень велико. Необходимо найти количество пар чисел, сумма которых кратна 26. Под парой подразумеваются два числа, расположенных на разных местах в наборе, порядок в паре неважен. Программа должна напечатать одно число - количество пар чисел, соответствующих условиям задачи.Если такое произведение получить невозможно, вывести -1.

Описание входных и выходных данных

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

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

4
61
9
95
3

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

2

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

Предупреждение: для обработки файла b не следует использовать переборный алгоритм, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Решение

Сумма будет кратна 26, если остатки от деления на 26 слагаемых в сумме дают 26 или 0. Воспользуемся критериальным способом решения этой задачи: будем находить количество чисел с различными остатками при делении на 26, а затем сопоставим эти группы для получения итогового ответа. Количество пар чисел, в которых оба числа кратны 10, рассчитываем по формуле $N*(N-1)/2!$, как и для чисел, кратных 26 (их количество будет храниться в элементе с индексом 10 и 0 соответственно)

Решение на Python:

file = open("file.txt", "r")
size = int(file.readline())
arr = [0] * 26
count13 = 0
for i in range(size):
val = int(file.readline())
arr[val % 26] += 1
countSum = int((arr[0] * (arr[0] - 1)) / 2 + (arr[13] * (arr[13] - 1)) / 2)
for i in range(1, 13):
countSum += arr[i] * arr[26 - i]
if countSum == 0:
print("-1")
else:
print(countSum)
file.close()

Решение на C++:
#include <iostream>
#include <fstream>
using namespace std;
int comp(int a, int b){return a < b;}
int main() {
ifstream file("file.txt");
int size; file >> size;
int arr[26]; for (int i = 0; i < 26; ++i) arr[i] = 0;
for (int i = 0; i < size; ++i) {
int val; file >> val;
arr[val % 26]++;
}
int count = (arr[0] * (arr[0] - 1))/2 + (arr[13] * (arr[13] - 1))/2;
for (int i = 1; i < 13; ++i)
count += arr[i] * arr[26 - i];
if (count == 0) cout << "-1";
else cout << count;
return 0;
}

Ответы: для файла А = 105, для файла Б = 173548026

Ответ:
Показать решение
Полный курс

Задача 3

Имеется набор данных, состоящий из положительных целых чисел, все числа не превышают 10000. Количество чисел известно, но может быть очень велико. Необходимо найти количество пар, в которых произведение чисел кратно 14, а числа находятся на расстоянии не больше 10 (разность в индексах ≤ 10). Под парой подразумеваются два числа, расположенных на разных местах в наборе, порядок в паре неважен. Программа должна напечатать одно число - количество пар, соответствующее условиям задачи.

В качестве ответа прикрепите код решения, а также два числа - ответ для файла А и ответ для файла B.

Предупреждение: для обработки файла b не следует использовать переборный алгоритм, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Решение

Пример решения на Python:

f = open('fileB4.txt')
N = int(f.readline())
mas = []
kol = 0
for i in range(N):
    x = int(f.readline())
    for y in mas:
        if x * y % 14 == 0:
            kol += 1
    if len(mas) >= 10:
        mas.pop(0)
    mas.append(x)
print(kol)
f.close()

Для прикреплённого файла A программа выведет: 173

Для прикреплённого файла B программа выведет: 198081

Ответ:
Показать решение
Полный курс

Задача 4

Имеется набор данных, состоящий из положительных целых чисел, все числа не превышают 10000. Количество чисел известно, но может быть очень велико. Необходимо найти наибольшее произведение пары чисел, кратное 26, числа в которой находятся на расстоянии не больше 26 (разность в индексах ≤ 26). Под парой подразумеваются два числа, расположенных на разных местах в наборе, порядок в паре неважен. Программа должна напечатать одно число - максимально возможное произведение, соответствующее условиям задачи. Если такое произведение получить невозможно, вывести -1.

В качестве ответа прикрепите код решения, а также два числа - ответ для файла А и ответ для файла B.

Предупреждение: для обработки файла b не следует использовать переборный алгоритм, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Решение

Пример решения на Python:

f = open('fileB7.txt')
N = int(f.readline())
mas = []
max_pr = -1
for i in range(N):
    x = int(f.readline())
    for y in mas:
        if x * y % 26 == 0:
            if x * y > max_pr:
                max_pr = x * y
    if len(mas) >= 26:
        mas.pop(0)
    mas.append(x)
print(max_pr)
f.close()

Для прикреплённого файла A программа выведет: 94449498

Для прикреплённого файла B программа выведет: 99580416

Ответ:
Показать решение
Полный курс

Задача 5

Имеется набор данных, состоящий из положительных целых чисел, все числа не превышают 10000. Количество чисел известно, но может быть очень велико. Необходимо найти количество пар, в которых произведение чисел кратно 85, а числа находятся на расстоянии не меньше 6 (разность в индексах ≥ 6). Под парой подразумеваются два числа, расположенных на разных местах в наборе, порядок в паре неважен. Программа должна напечатать одно число - количество пар, соответствующее условиям задачи.

Описание входных и выходных данных

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

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

4

14

2

8

3

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

1

В качестве ответа прикрепите код решения, а также два числа - ответ для файла А и ответ для файла B.

Предупреждение: для обработки файла b не следует использовать переборный алгоритм, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Решение

Пример решения на Python:

def bubble_sort(a):

for i in range(len(a)):

for j in range(len(a) - 1 - i):

if a[j] < a[j+1]:

a[j], a[j+1] = a[j+1], a[j]

f = open("file.txt")

i = 0

a = []

for st in f:

if i == 0:

N = int(st)

else:

n1, n2, n3 = map(int, st.split())

a.append(max(n1,n2,n3))

i += 1

bubble_sort(a)

print(a[9])

f.close()

Для прикреплённого файла программа выведет: 9952

Ответ:
Показать решение
Полный курс

Задача 6

Имеется набор данных, состоящий из положительных целых чисел, все числа не превышают 10000. Количество чисел известно, но может быть очень велико. Необходимо найти наибольшее произведение пары чисел, кратное 27, числа в которой находятся на расстоянии не меньше 7 (разность в индексах ≥ 7). Под парой подразумеваются два числа, расположенных на разных местах в наборе, порядок в паре неважен. Программа должна напечатать одно число - максимально возможное произведение, соответствующее условиям задачи.Если такое произведение получить невозможно, вывести -1.

Описание входных и выходных данных

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

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

5

13

15

6

2

4

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

52

В качестве ответа прикрепите код решения, а также два числа - ответ для файла А и ответ для файла B.

Предупреждение: для обработки файла b не следует использовать переборный алгоритм, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Решение

Пример решения на Python:

def bubble_sort(a):

for i in range(len(a)):

for j in range(len(a) - 1 - i):

if a[j] < a[j+1]:

a[j], a[j+1] = a[j+1], a[j]

f = open("file.txt")

i = 0

a = []

for st in f:

if i == 0:

N = int(st)

else:

n1, n2, n3 = map(int, st.split())

a.append(max(n1,n2,n3))

i += 1

bubble_sort(a)

print(a[9])

f.close()

Для прикреплённого файла программа выведет: 9952

Ответ:
Показать решение
Полный курс

Задача 7

Имеется набор данных, состоящий из положительных целых чисел, все числа не превышают 10000. Количество чисел известно, но может быть очень велико. Необходимо найти количество пар, в которых произведение чисел кратно 46. Под парой подразумеваются два числа, расположенных на разных местах в наборе, порядок в паре неважен. Программа должна напечатать одно число - количество пар, соответствующее условиям задачи.

Описание входных и выходных данных

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

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

4

92

2

8

3

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

3

В качестве ответа прикрепите код решения, а также два числа - ответ для файла А и ответ для файла B.

Предупреждение: для обработки файла b не следует использовать переборный алгоритм, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Решение

Пример решения на Python на 1 балл:

f = open("fileA7.txt")

N = int(f.readline())

a = []

for i in range(N):

x = int(f.readline())

a.append(x)

f.close()

kol_par = 0

for i in range(N):

for j in range(i+1, N):

if a[i]*a[j] % 46 == 0:

kol_par += 1

print(kol_par)

Пример решения на Python на 2 балла:

f = open("fileB7.txt")

N = int(f.readline())

kol46 = kol23 = kol2 = kol0 = 0

for i in range(N):

x = int(f.readline())

if x % 46 == 0:

kol46 += 1

elif x % 23 == 0:

kol23 += 1

elif x % 2 == 0:

kol2 += 1

else:

kol0 += 1

f.close()

kol_par = kol46*(kol46-1)//2 + kol46*(N-kol46) + kol23*kol2

print(kol_par)

Для прикреплённого файла A программа выведет: 197

Для прикреплённого файла B программа выведет: 286112969

Ответ:
Показать решение
Полный курс

Задача 8

Имеется набор данных, состоящий из положительных целых чисел, все числа не превышают 10000. Количество чисел известно, но может быть очень велико. Необходимо найти количество пар, в которых произведение чисел кратно 26. Под парой подразумеваются два числа, расположенных на разных местах в наборе, порядок в паре неважен. Программа должна напечатать одно число - количество пар, соответствующее условиям задачи.

Описание входных и выходных данных

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

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

4

14

2

8

3

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

3

В качестве ответа прикрепите код решения, а также два числа - ответ для файла А и ответ для файла B.

Предупреждение: для обработки файла b не следует использовать переборный алгоритм, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Решение

Пример решения на Python:

def bubble_sort(a):

for i in range(len(a)):

for j in range(len(a) - 1 - i):

if a[j] < a[j+1]:

a[j], a[j+1] = a[j+1], a[j]

f = open("file.txt")

i = 0

a = []

for st in f:

if i == 0:

N = int(st)

else:

n1, n2, n3 = map(int, st.split())

a.append(max(n1,n2,n3))

i += 1

bubble_sort(a)

print(a[9])

f.close()

Для прикреплённого файла программа выведет: 9952

Ответ:
Показать решение
Полный курс

Задача 9

Имеется набор данных, состоящий из положительных целых чисел, все числа не превышают 10000. Количество чисел известно, но может быть очень велико. Необходимо найти наибольшее произведение пары чисел, кратное 52. Под парой подразумеваются два числа, расположенных на разных местах в наборе, порядок в паре неважен. Программа должна напечатать одно число - максимально возможное произведение, соответствующее условиям задачи.Если такое произведение получить невозможно, вывести -1.

Описание входных и выходных данных

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

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

4

13

4

2

15

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

52

В качестве ответа прикрепите код решения, а также два числа - ответ для файла А и ответ для файла B.

Предупреждение: для обработки файла b не следует использовать переборный алгоритм, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Решение

Пример решения на Python:

def bubble_sort(a):

for i in range(len(a)):

for j in range(len(a) - 1 - i):

if a[j] < a[j+1]:

a[j], a[j+1] = a[j+1], a[j]

f = open("file.txt")

i = 0

a = []

for st in f:

if i == 0:

N = int(st)

else:

n1, n2, n3 = map(int, st.split())

a.append(max(n1,n2,n3))

i += 1

bubble_sort(a)

print(a[9])

f.close()

Для прикреплённого файла программа выведет: 9952

Ответ:
Показать решение
Полный курс

Задача 10

Имеется набор данных, состоящий из положительных целых чисел, все числа не превышают 10000. Количество чисел известно, но может быть очень велико. Необходимо найти наименьшее произведение пары чисел, кратное 26, числа в которой находятся на расстоянии не меньше 4 (разность в индексах ≥ 4). Под парой подразумеваются два числа, расположенных на разных местах в наборе, порядок в паре неважен. Программа должна напечатать одно число - минимально возможное произведение, соответствующее условиям задачи.Если такое произведение получить невозможно, вывести -1.

Описание входных и выходных данных

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

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

5

13

15

6

2

4

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

52

В качестве ответа прикрепите код решения, а также два числа - ответ для файла А и ответ для файла B.

Предупреждение: для обработки файла b не следует использовать переборный алгоритм, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Решение

Пример решения на Python на 1 балл:

f = open("file.txt")

N = int(f.readline())

a = []

for i in range(N):

a.append(int(f.readline()))

f.close()

min_pr = 10001 * 10001

for i in range(N):

for j in range(i+1, N):

pr = a[i]*a[j]

if pr % 26 == 0 and pr < min_pr and j-i >= 4:

min_pr = pr

if min_pr == 10001 * 10001:

print(-1)

else:

print(min_pr)

Пример решения на Python на 2 балла:

f = open("file.txt")

N = int(f.readline())

min26 = min13 = min2 = min0 = 10001

min_pr = 10001 * 10001

queue = []

for i in range(3):

queue.append(int(f.readline()))

for i in range(3, N):

x = int(f.readline())

if x % 26 == 0:

if x * min26 < min_pr and min26 != 10001:

min_pr = x * min26

if x * min13 < min_pr and min13 != 10001:

min_pr = x * min13

if x * min2 < min_pr and min2 != 10001:

min_pr = x * min2

if x * min0 < min_pr and min0 != 10001:

min_pr = x * min0

elif x % 13 == 0:

if x * min26 < min_pr and min26 != 10001:

min_pr = x * min26

if x * min2 < min_pr and min2 != 10001:

min_pr = x * min2

elif x % 2 == 0:

if x * min26 < min_pr and min26 != 10001:

min_pr = x * min26

if x * min13 < min_pr and min13 != 10001:

min_pr = x * min13

else:

if x * min26 < min_pr and min26 != 10001:

min_pr = x * min26

if queue[0] % 26 == 0:

if queue[0] < min26:

min26 = queue[0]

elif queue[0] % 13 == 0:

if queue[0] < min13:

min13 = queue[0]

elif queue[0] % 2 == 0:

if queue[0] < min2:

min2 = queue[0]

else:

if queue[0] < min0:

min0 = queue[0]

queue[0] = queue[1]

queue[1] = queue[2]

queue[2] = x

if min_pr == 10001 * 10001:

print(-1)

else:

print(min_pr)

f.close()

Вывод для файла А: 53404

Вывод для файла B: 78

Ответ:
Показать решение
Полный курс

Задача 11

Имеется набор данных, состоящий из положительных целых чисел, все числа не превышают 10000. Количество чисел известно, но может быть очень велико. Необходимо найти количество пар чисел, произведение которых кратно 14. Под парой подразумеваются два числа, расположенных на разных местах в наборе, порядок в паре неважен. Программа должна напечатать одно число - количество пар чисел, соответствующих условиям задачи.Если такое произведение получить невозможно, вывести -1.

Описание входных и выходных данных

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

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

4
14
2
21
3

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

4

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

Предупреждение: для обработки файла b не следует использовать переборный алгоритм, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Решение

Число 14 раскладывается на множители 7 и 2. Проивзедение будет кратно 14, если один из множителей кратен 14 или числа в паре содержат простые множители 14. Воспользуемся критериальным способом решения этой задачи и разобъём входные значения на 4 группы и найдём количество значений в каждой из групп:
А. Число делится на 2 и 7;
В. Число делится на 2, не делится на 7;
С. Число не делится на 2, делится на 7;
D. Число не делится на 2, не делится на 7;

Решение на Python:

file = open("file.txt", "r")
size = int(file.readline())
countA, countB, countC, countD = (0, 0, 0, 0)
for i in range(size):
val = int(file.readline())
if val % 2 == 0 and val % 7 == 0:
countA += 1
elif val % 2 == 0 and val % 7 != 0:
countB += 1
elif val % 2 != 0 and val % 7 == 0:
countC += 1
elif val % 2 != 0 and val % 7 != 0:
countD += 1
print(int(countA * (countA - 1) / 2 + countA * countB +
countA * countC + countA * countD + countB * countC))
file.close()

Решение на C++:

#include <iostream>
#include <fstream>
using namespace std;
int main() {
ifstream file("file.txt");
int size; file >> size;
int countA = 0, countB = 0, countC = 0, countD = 0;
for (int i = 0; i < size; ++i) {
int val; file >> val;
if (val % 2 == 0 && val % 7 == 0)
countA += 1;
else if (val % 2 == 0 && val % 7 != 0)
countB += 1;
else if (val % 2 != 0 && val % 7 == 0)
countC += 1;
else if (val % 2 != 0 && val % 7 != 0)
countD += 1;
}
int count = countA * (countA - 1) / 2 + countA * countB +
countA * countC + countA * countD + countB * countC;
if (count == 0) cout << "-1";
else cout << count;
return 0;
}

Ответы: для файла А = 947, для файла Б = 990014844

Ответ:
Показать решение
Полный курс
Показать еще

Готовим к ЕГЭ на 85+ баллов и побеждаем лень

Каждый месяц 12 онлайн-занятий в дружелюбной атмосфере + 16 домашних работ с жесткими сроками.
Не готовишься — вылетаешь.

Подробнее о курсе