Задание 27. Программирование. Оптимизация по времени и памяти. ЕГЭ 2023 по информатике
Средний процент выполнения: 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