Задание 26. Алгоритмы сортировки. Обработка целочисленной информации.. ЕГЭ 2026 по информатике
Средний процент выполнения: 6%
Ответом к заданию 26 по информатике может быть развернутый ответ (полная запись решения с обоснованием выполненных действий).
Алгоритм решения задания 26:
- Прочитай условие и определи входные данные и требуемый результат.
- Считай все целые числа и сохрани их в структуре данных (массив/список).
- Определи вид сортировки, который требуется по условию (по возрастанию/убыванию).
- Отсортируй данные выбранным способом.
- После сортировки выполни требуемые действия (поиск, подсчёт, выбор элементов).
- Проверь, что сортировка выполнена корректно.
- Запиши ответ в требуемом формате.
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
В логистическом центре есть N ящиков кубической формы для вложенной упаковки дорогих хрупких товаров. Технология упаковки требует, чтобы каждый следующий ящик был помещён в предыдущий, но разница в длине стороны между внешним и внутренним ящиком должна быть не менее D единиц (иначе товар будет повреждаться).
Один товар упаковывается в самую маленькую коробку, потом она вкладывается в большую и так далее. Определите:
- Максимальное количество ящиков, которое можно использовать для упаковки одного товара.
- При таком максимальном количестве — максимально возможную длину стороны самого маленького ящика в этой цепочке.
Входные данные:
Первые две строки содержат два целых числа:
- N — количество ящиков (1 ≤ N ≤ 10 000)
- D — минимально допустимая разница в длине стороны между соседними ящиками (1 ≤ D ≤ 1000)
В следующих N строках находятся длины сторон ящиков (натуральные числа, не превышающие 10 000), каждое — в отдельной строке.
Выходные данные:
Два целых числа через пробел:
- наибольшее количество ящиков в цепочке
- максимальная длина стороны самого маленького ящика в такой цепочке
Пример входных данных:
5 8 50 22 34 40 16
Пример выходных данных:
3 22
Пояснение к примеру:
Можно собрать цепочку: 16 → 34 → 50 (разницы 18 и 16, что ≥ 8).
Также можно 22 → 34 → 50 (разницы 12 и 16, ≥ 8).
Вторая цепочка тоже из 3 ящиков, но самая маленькая коробка там имеет сторону 22, что больше чем 16.
Ответ: максимальное количество = 3, при этом максимальная минимальная коробка = 22.
Решение
Напишем код на Python:
f = open('26 коробки.txt')
n = int(f.readline())
d = int(f.readline())
boxes = sorted(int(x) for x in f.readlines())
best_len = 0
best_min = 0
for start in range(n):
count = 1
prev = boxes[start]
for i in range(start + 1, n):
if boxes[i] - prev >= d:
count += 1
prev = boxes[i]
# выбираем лучшую цепочку
if count > best_len or (count == best_len and boxes[start] > best_min):
best_len = count
best_min = boxes[start]
print(best_len, best_min)
Ответ: 854 54
Задача 2
РЕШЕНИЕ БЕЗ ОТВЕТА НЕ ПРИНИМАЕТСЯ, В ПРОТИВНОМ СЛУЧАЕ РАБОТА БУДЕТ АННУЛИРОВАНА
Входной файл содержит информацию о домашках учеников Турбо, отправивших свои решения кураторам в течение календарных суток. В домашке указаны время начала и время окончания приёма работы (в минутах от начала суток).
Рабочие места кураторов пронумерованы натуральными числами начиная с 1. Приём одной работы ученика берёт свободный куратор в окне с минимальным номером. Новый ученик может обратиться к освободившемуся куратору начиная со следующей минуты после завершения приёма предыдущего. Если в момент обращения свободных кураторов нет, ученик уходит спать. Определите, сколько учеников смогут получить проверку домашек в течение 24 ч, и каков номер куратора, который начнёт принимать домашку последним. Если таких номеров несколько, укажите наименьший номер.
Входные данные
В первой строке входного файла находится натуральное число K, не превышающее 1000, - количество кураторов. Во второй строке натуральное число N (N ≤ 10 000), обозначающее количество домашек учеников. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: указанные в домашке время начала и время окончания проверки (в минутах от начала суток).
Запишите в ответе два числа: количество учеников, которые смогут получить проверку домашки, и номер куратора, который примет последнюю домашку.
Типовой пример организации данных во входном файле
2 5 30 60 40 100 59 60 61 100 101 144
При таких исходных данных воспользоваться проверкой смогут первый, второй, четвёртый и пятый ученики. Наименьший номер куратора, где последняя домашка будет принята, - 1, так как будут свободны окна 1 и 2.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Решение
Для решения используем Python, отсортируем данные и сделаем простую очередь, добавим счётчик и сохранение последнего куратора, взявшего в работу домашку
Код решения (Python)
f = open("turbo_26.txt")
k = int(f.readline())
n = int(f.readline())
homeworks = []
for i in range(n):
a = list(map(int, f.readline().split()))
homeworks.append(a)
homeworks.sort()
kurators = [0] * (k + 1) # +1 потому что счёт идёт с 1
counter = 0
last = 0
for start, end in homeworks:
for i in range(1, k + 1):
if kurators[i] <= start:
kurators[i] = end + 1
counter += 1
last = i
break
print(counter, last)Ответ: 8712 13
Задача 3
На новогодней фабрике подарков Деда Мороза составляют рейтинговый список новых видов подарков по данным о времени изготовления игрушки в обычном режиме и в ускоренном предпраздничном режиме. У каждого подарка известны оба показателя. Названия подарков скрыты, все подарки пронумерованы начиная с 1.
Алгоритм формирования рейтинга:
- все 2N чисел, обозначающих время изготовления в обычном режиме и в ускоренном режиме для N подарков, располагаются по возрастанию;
- если наименьший показатель соответствует времени изготовления в обычном режиме, подарок занимает первое свободное место от начала рейтинга;
- если наименьший показатель относится ко времени изготовления в ускоренном предпраздничном режиме, подарок занимает первое свободное место от конца рейтинга;
- показатели подарков, ранее включённых в рейтинговый список, игнорируются.
Определите порядковый номер подарка, чей рейтинг будет определён последним, и количество подарков, занявших позиции ниже него.
В ответе запишите два натуральных числа: сначала номер последнего подарка, затем количество подарков, которые займут в рейтинге более низкие места.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 1000) — количество подарков.
Следующие N строк содержат пары натуральных различных чисел, обозначающих соответственно время изготовления подарка в обычном режиме и в ускоренном предпраздничном режиме.
Типовой пример входных данных
5
800 120
150 200
250 300
60 100
180 220
Пример приведён для пяти новогодних подарков.
Решение
Эту задачу можно быстро решить в таблицах, но приведу решение на Python
f = open("26 новый год.txt")
n = int(f.readline())
events = []
for i in range(n):
normal, fast = map(int, f.readline().split())
# 0 — обычный режим, 1 — ускоренный
events.append((normal, i + 1, 0))
events.append((fast, i + 1, 1))
f.close()
# сортируем все 2N показателей
events.sort()
used = set()
left = 1
right = n
last_gift = -1
last_position = -1
for value, gift, mode in events:
if gift in used:
continue
used.add(gift)
if mode == 0: # обычный режим → с начала
position = left
left += 1
else: # ускоренный режим → с конца
position = right
right -= 1
last_gift = gift
last_position = position
# количество подарков ниже последнего
below = n - last_position
print(last_gift, below)
Идея решения заключается в том, что для каждого подарка рассматриваются оба времени изготовления как отдельные события, после чего все 2N значений сортируются по возрастанию; далее рейтинг заполняется по очереди: если минимальное из оставшихся значений относится к обычному режиму, соответствующий подарок помещается на первую свободную позицию слева, если к ускоренному режиму — на первую свободную позицию справа, при этом после размещения подарка его второй показатель больше не учитывается; фиксируя подарок, размещённый последним, и его позицию, легко определить, сколько подарков окажется ниже него в рейтинге.
Ответ: 667 517
Задача 4
Предприятие производит детали A и B, на их производство выделена конкретная сумма денег. Вам предоставлен полный перечень, какие детали можно изготовить. Каждую деталь из перечня моно сделать только 1 раз. При изготовлении необходимо руководствоваться следующими правилами:
- Нужно изготовить максимальное количество деталей.
- При одинаковом максимальном количестве деталей, нужно постараться изготовить больше деталей B при наименьшей стоимости.
Определите, сколько всего будет изготовлено деталей B и какая сумма останется неиспользованной. В ответе запишите эти два числа через пробел, сначала количество изготовленных деталей, потом пробел, потом оставшуюся сумму.
В первой строке файла указано количество деталей, которые можно изготовить и общая сумма денег, которую можно потратить
В остальных строчках указана стоимость детали и её вид
Решение
Для решения этого номера напишем код:
f = open('26.txt', 'r')
n, s = map(int, f.readline().strip().split(' '))
detail = {'A': [], 'B': []}
for line in f:
v, k = line.strip().split()
detail[k].append(int(v))
detail['B'].sort()
detail['A'].sort()
sum_all = 0
cur = ''
last = 0
new = {'A': [], 'B': []}
while sum(new['B']) + sum(new['A']) <= s:
if detail['B'][0] <= detail['A'][0]:
new['B'].append(detail['B'].pop(0))
cur = 'B'
else:
new['A'].append(detail['A'].pop(0))
cur = 'A'
detail[cur].insert(0, last)
new[cur].pop()
while sum(new['B']) + detail['B'][0] + sum(new['A']) - new['A'][-1] <= s:
new['B'].append(detail['B'].pop(0))
new['A'].pop()
print(len(new['B']), s - sum(new['B']) - sum(new['A']))
Задача 5
На складе посылки складывают параллельными рядами, которые пронумерованы идущими подряд натуральными числами. Посылки в каждом ряду пронумерованы натуральными числами начиная с единицы.
Все посылки расставляют специальные роботы, которые все данные хранят в общей базе. Известно, в каких рядах и на каких местах посылки забрали в доставку. Найдите ряд с наибольшим номером, в котором есть ровно 7 идущих подряд свободных мест для новых посылок таких, что непосредственно слева и справа от них в том же ряду посылка лежит. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: наибольший номер ряда и наименьший номер места для размещения посылки из числа найденных в этом ряду подходящих последовательностей из 7 свободных мест.
В ответе укажите два числа без пробелов. Например, если вы получили 46 и 72, то ответ будет 4672
Решение
f = open('26.txt', 'r')
n = int(f.readline().strip())
forest = [[int(t) for t in x.split()] for x in f]
forest.sort()
max_row = float('-inf')
min_pos = float('inf')
for i in range(n - 1):
if forest[i][0] == forest[i + 1][0]:
if forest[i + 1][1] - forest[i][1] == 8:
if max_row < forest[i][0]:
max_row = forest[i][0]
min_pos = forest[i][1] + 1
print(max_row, min_pos)
Задача 6
На склад завезли обручи разного диаметра. Рабочие решили собрать как можно больше обручей в одной месте, для этого они стали помещать один обруч внутрь другого. Один обруч можно поместить в другую, если его диаметр хотя бы на 3 единицы меньше диаметра стороны другого обруча. Определите наибольшее количество обручей, которые можно уложить в одном месте, и максимально возможный диаметр самого маленького обруча, который можно положить последним.
Входные данные представлены в файле следующим образом. В первой строке входного файла записано число N – количество обручей на складе (натуральное число, не превышающее 10 000). В каждой из следующих N строк находится число, равное диаметру обруча (натуральное число, не превышающее 10 000).
Запишите в ответе два целых числа через пробел: сначала наибольшее количество обручей, которые можно поместить в одном месте, затем максимально возможный диаметр самого маленького обруча, который положили последним.
Пример входного файла: 5 43 40 32 40 30
Пример входного файла приведён для пяти обручей и случая, когда минимальная допустимая разница между диаметрами составляет 3 единицы. При таких исходных данных условию задачи удовлетворяют наборы обручей с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество обручей равно 3, а длина стороны самого маленького обруча 32.
Решение
f = open('26.txt', 'r')
n = int(f.readline())
rounds = [int(x) for x in f]
rounds.sort(reverse=True)
curr = rounds[0]
count = 1
for i in range(n):
if curr - 3 >= rounds[i]:
curr = rounds[i]
count += 1
print(count, curr)
Задача 7
В городе расположены постаматы из K ячеек. Ячейки постамата пронумерованы, начиная с 1. Курьеры складывают товар в ячейки постамата. Товар кладётся в свободную ячейку с минимальным номером. Известно время размещения товара в ячейку и время освобождения ячейки (в минутах от начала суток). Товар достаётся из ячейки в течение минуты. Начиная со следующей минуты, в ячейку можно положить другой товар. Если все ячейки заняты, то товар убирается в другой постамат.
Определите количество товаров, которое можно загрузить в первый постамат за 24 часа и номер последней использованной ячейки, в которую положили товар.
Входные данные
В первой строке входных данных задается количество ячеек в постамате - K и количество товаров, которые хотят убрать в постамат - M.
В каждой из последующих М строк содержится два числа - количество минут с начала суток, предположительное время занятия ячейки и количество минут - предположительное время, когда товар заберёт покупатель.
В ответе укажите 2 числа слитно (без пробелов и других разделителей)
Решение
f = open('26_1.txt', 'r')
n, k = map(int, f.readline().split())
packages = [[int(l) for l in x.split()] for x in f]
packages.sort()
print(packages)
cell = [0] * n
print(cell)
number = 0
count = 0
for p in packages:
for i in range(n):
if cell[i] < p[0]:
count += 1
cell[i] = p[1]
number = i + 1
break
print(cell)
print(count, number)
Задача 8
В магазине решили провести акцию «каждый третий товар бесплатно». Дядя Миша решил хорошенько сэкономить и разделил товары на группы по три товара, собираясь заплатить за каждую группу отдельным чеком. Дядя Миша разместил товары таким образом, что каждый третий товар был самым дорогим. Но к великому разочарованию Дяди Миши выяснилось, что при на кассе не учитывается расположение товара на ленте и итоговая цена товаров в чеке формируется таким образом, что стоимость покупки максимальная.
Входные данные
В первой строке входного файла находится число N — количество товаров, которые планирует приобрести покупатель (натуральное число, не превышающее 10 000). В следующих N строках находятся цены товаров, которые выбрал покупатель (все числа натуральные, не превышающие 10 000, каждое — в отдельной строке).
Цены товаров указаны в произвольном порядке.
Найдите минимальную цену, которую планировал заплатить покупатель изначально, если бы бесплатным был 3-й товар в любой покупке, состоящей из З предметов. А затем цену, которую он заплатил. Покупатель делит товары на группы наиболее выгодным для себя способом.
Запишите в ответе разность между суммой, которую заплатил, и суммой, которую планировал заплатить покупатель.
Типовой пример организации во входном файле:
4 80 30 50 40
При таких исходных данных, если каждый третий товар бесплатно, предполагаемая и действительная суммы равны 120 и 170. В ответе нужно указать 50 (170 - 120)
Решение
Решение на языке Python
f = open('26_new.txt')
n = int(f.readline())
a = []
for i in range(n):
a.append(int(f.readline()))
a.sort(reverse = True)
sum_min = sum(a[n // 3:])
a.sort()
sum_max = sum(a[n // 3:])
print(sum_max-sum_min)
Ответ: 21957374
Задача 9
В городе расположены постаматы из K ячеек. Ячейки постамата пронумерованы, начиная с 1. Курьеры складывают товар в ячейки постамата. Товар кладётся в свободную ячейку с минимальным номером. Известно время размещения товара в ячейку и время освобождения ячейки (в минутах от начала суток). Товар достаётся из ячейки в течение минуты. Начиная со следующей минуты, в ячейку можно положить другой товар. Если все ячейки текущего постамата заняты, то товар убирается в следующий постамат и так, пока весь товар не будет загружен.
Определите количество товаров, которое можно загрузить в третий постамат за 24 часа и минимальное количество постаматов, которые нужно использовать.
Входные данные
В первой строке входных данных задается количество ячеек в постамате - K и количество товаров, которые хотят убрать в постамат - M.
В каждой из последующих М строк содержится два числа - количество минут с начала суток, предположительное время занятия ячейки и количество минут - предположительное время, когда товар заберёт покупатель.
В ответе укажите 2 числа.
Решение
f = open('26_1.txt', 'r')
n, k = map(int, f.readline().split())
packages = [[int(l) for l in x.split()] for x in f]
packages.sort()
cell = [[0] * n for i in range(k // n)]
number = 0
count = 0
max_post = 0
for p in packages:
start = True
for post in range(k // n):
for i in range(n):
if cell[post][i] < p[0]:
if post == 2:
count += 1
cell[post][i] = p[1]
number = i + 1
start = False
max_post = max(max_post, post + 1)
break
if not start:
break
print(count, max_post)
Ответ: 320 19
Задача 10
В городе расположены постаматы из K ячеек. Ячейки постамата пронумерованы, начиная с 1. Курьеры складывают товар в ячейки постамата. Товар кладётся в свободную ячейку с минимальным номером. Известно время размещения товара в ячейку и время освобождения ячейки (в минутах от начала суток). Товар достаётся из ячейки в течение минуты. Начиная со следующей минуты, в ячейку можно положить другой товар. Если все ячейки текущего постамата заняты, то товар убирается в следующий постамат и так, пока весь товар не будет загружен.
Определите количество товаров, которое можно загрузить в первый постамат за 24 часа и минимальное количество постаматов, которые нужно использовать.
Входные данные
В первой строке входных данных задается количество ячеек в постамате - K и количество товаров, которые хотят убрать в постамат - M.
В каждой из последующих М строк содержится два числа - количество минут с начала суток, предположительное время занятия ячейки и количество минут - предположительное время, когда товар заберёт покупатель.
В ответе укажите 2 числа слитно (без пробелов и других разделителей)
Решение
f = open('26_1.txt', 'r')
n, k = map(int, f.readline().split())
packages = [[int(l) for l in x.split()] for x in f]
packages.sort()
cell = [[0] * n for i in range(k // n)]
number = 0
count = 0
max_post = 0
for p in packages:
start = True
for post in range(k // n):
for i in range(n):
if cell[post][i] < p[0]:
if post == 0:
count += 1
cell[post][i] = p[1]
number = i + 1
start = False
max_post = max(max_post, post + 1)
break
if not start:
break
print(count, max_post)
Задача 11
Для тестирования нового агропромышленного дрона на поле были установлены специальные метки на разном расстоянии (расстояние измеряется в целых метрах). При этом метки размещались на координатной сетке и имели координаты x и y. Началом отсчёта считалась крайняя левая точка на поле. Все метки были занесены в файл в формате x и y.
Дрон летает по линии, за основу дрон берёт координату по х. Когда дрон пролетит все метки в текущей координате х, он переходит в координату х+1. Выяснилось, что если метки по координате у установлены на расстоянии в 50 и более метров, то дрон их не считывает и автоматически переходит на следующую координату по х.
Напишите программу, которая позволит найти количество координат по х, где есть метки по у на расстоянии в 50 и более метров. В ответе укажите количество таких координат по x и максимальное количество пропущенных меток в одном ряду по х, удовлетворяющих условию.
Входные данные.
В первой строке входного файла находится одно число:
N – количество меток (натуральное число, не превышающее 10 000). В следующих N строках находятся пары чисел: х и y с установленными метками (числа не превышают 100 000).
Выходные данные.
Два целых неотрицательных числа:
Количество координат по х, удовлетворяющих условию, и максимальное количество пропущенных меток одного ряда, удовлетворяющих условию.
Примечание: эту задачу можно решить через Excel, но формула будет достаточно сложной.
Решение
Этот номер решить в Excel несколько сложнее, но тоже вполне реально. Рассмотрим решение на Python.
f = open('26.txt', 'r')
n = int(f.readline().strip())
ticket = [[int(x) for x in line.strip().split()] for line in f if line.strip() != '']
ticket.sort()
corr = []
current_row = -1
for row in range(len(ticket) - 1):
if ticket[row][0] == ticket[row + 1][0] and ticket[row][1] <= ticket[row + 1][1] - 50:
corr.append(ticket[row][0])
current_row = ticket[row][0]
elif current_row == ticket[row][0]:
corr.append(ticket[row][0])
max_s = 0
for x in corr:
max_s = max(max_s, corr.count(x))
print(len(set(corr)), max_s)
Обратите внимание, что в одном ряду, как только будет найдена метка на расстоянии 50 и более, нужно учитывать все оставшиеся метки до конца ряда, чтобы найти максимальное количество. Можно реализовать и другой алгоритм для решения этой задачи, без сохранения номера ряда, но с подсчётом количества таких меток.
f = open('26_dron.txt', 'r')
n = int(f.readline().strip())
ticket = [[int(x) for x in line.strip().split()] for line in f if line.strip() != '']
ticket.sort()
corr = []
current_row = -1
k = 0
max_s = 0
for row in range(len(ticket) - 1):
if current_row == ticket[row][0]:
k += 1
elif ticket[row][0] == ticket[row + 1][0] and ticket[row][1] <= ticket[row + 1][1] - 50:
max_s = max(max_s, k)
corr.append(ticket[row][0])
current_row = ticket[row][0]
k = 1
print(len(set(corr)), max_s)
Ответ: 2492 7
Задача 12
ДЛЯ 2022
Для развития сельского хозяйства разрабатываются специальные агропромышленные дроны и роботы. После тестирования агропромышленного дрона, решили протестировать робота, который позволяет высаживать яблони, в дальнейшем и другие деревья. Яблони были высажены параллельными рядами, которые пронумерованы идущими подряд натуральными числами, начиная с 1.
После окончания работы робота, через несколько недель решили запустить дрона (исправленного после тестирования), чтобы он определил в каких рядах и на каких местах яблони не прижились. Дрон зафиксировал все деревья, которые прижились, и сохранил данные в файл. Найдите ряд с наибольшим номером, в котором есть максимальное количество идущих подряд свободных мест для посадки новых яблонь, так, чтобы слева и справа от них в этом же ряду яблони прижились. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два целых числа: номер ряда и максимальное количество подряд идущих свободных места для посадки яблонь.
Входные данные
В первой строке входного файла находится число N – количество прижившихся яблонь (натуральное число, не превышающее 20 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер места в этом ряду, на котором растёт яблоня.
Выходные данные
Два целых неотрицательных числа: наибольший номер ряда и максимальное количество мест, подходящий для посадки новых яблонь.
Типовой пример организации входных данных
7 40 3 40 7 60 33 50 125 50 129 50 68 50 72
Для приведённого примера, при условии, что необходимо 3 свободных места, ответом является пара чисел: 50; 69.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Решение
Для решения этого номера можно написать программу или решить номер в электронных таблицах
Приведём пример решения на языке программирования Python
f = open('26.txt', 'r')
n = int(f.readline().strip())
places = [[int(x) for x in line.split()] for line in f if line.strip() != '']
places.sort()
max_free = 0
max_row = 0
for i in range(n - 1):
if places[i][0] == places[i + 1][0] and places[i + 1][1] - places[i][1] - 1 >= max_free:
max_free = places[i + 1][1] - places[i][1] - 1
max_row = places[i][0]
print(max_row, max_free)
ответ: 99702 98902
Задача 13
Для тестирования нового агропромышленного дрона на поле были установлены специальные метки на разном расстоянии (расстояние измеряется в целых метрах). При этом метки размещались на координатной сетке и имели координаты x и y. Началом отсчёта считалась крайняя левая точка на поле. Все метки были занесены в файл в формате x и y.
Дрон летает по линии, за основу дрон берёт координату по х. Когда дрон пролетит все метки в текущей координате х, он переходит в координату х+1. Выяснилось, что если метки по координате у установлены на расстоянии в 50 и более метров, то дрон их не считывает и автоматически переходит на следующую координату по х.
Напишите программу, которая позволит найти количество координат по х, где есть метки по у на расстоянии в 50 и более метров. В ответе укажите количество таких координат по x и максимальное количество промежутков внутри одного ряда по х, удовлетворяющих условию.
Входные данные.
В первой строке входного файла находится одно число:
N – количество меток (натуральное число, не превышающее 10 000). В следующих N строках находятся пары чисел: х и y с установленными метками (числа не превышают 100 000).
Выходные данные.
Два целых неотрицательных числа:
Количество координат по х, удовлетворяющих условию, и максимальное количество промежутков внутри одного ряда, удовлетворяющих условию.
Решение
Этот номер решить в Excel несколько сложнее, но тоже вполне реально. Рассмотрим решение на Python.
f = open('26.txt', 'r')
n = int(f.readline().strip())
ticket = [[int(x) for x in line.strip().split()] for line in f if line.strip() != '']
ticket.sort()
corr = []
for row in range(len(ticket) - 1):
if ticket[row][0] == ticket[row + 1][0] and ticket[row][1] < ticket[row + 1][1] - 50:
corr.append(ticket[row][0])
max_s = 0
for x in corr:
max_s = max(max_s, corr.count(x))
print(len(set(corr)), max_s)
Обратите внимание, что в одном ряду может быть несколько меток на расстоянии 50 и более. Поэтому просто вывести количество найденных элементов недостаточно. Можно придумать и другую реализацию алгоритма, без использования set (множества).
Ответ: 2491 5
Задача 14
РЕШЕНИЕ БЕЗ ОТВЕТА НЕ ПРИНИМАЕТСЯ, В ПРОТИВНОМ СЛУЧАЕ РАБОТА БУДЕТ АННУЛИРОВАНА
Во время соревнований по футболу болельщики одной из команд решили купить все места на стадионе, чтобы болельщикам другой команде не было места, где можно было сесть. Билеты покупали через 1 или 2 пустых места, но для родственников покупали билеты рядом, чтобы выполнить требования связанные с ограничениями из-за распространения COVID-19. В файле были сохранены все купленные места, в формате "ряд место".
Выяснилось, что места купили неправильно и некоторые места были куплены на расстоянии 3 и более пустых мест.
Напишите программу, которая позволит найти все пустые места такие, что слева и справа от этого места пусто, а через одно пустое место слева и справа, места заняты. В ответе укажите максимальный ряд и минимальное место в этом ряду, удовлетворяющее условию.
Входные данные.
В первой строке входного файла находится одно число:
N – количество занятых мест (натуральное число, не превышающее 10 000). В следующих N строках находятся пары чисел: ряд и место выкупленного билета (числа не превышают 100 000).
Выходные данные.
Два целых неотрицательных числа:
Максимальный номер ряда, где нашлись обозначенные в задаче места и минимальный номер места.
Решение
Данную задачу можно решить через электронные таблицы, используя сортировку и условие, но тут будет описано решение через Python.
f = open('26.txt', 'r')
n = int(f.readline().strip())
ticket = [[int(x) for x in line.strip().split()] for line in f if line.strip() != '']
ticket.sort()
for row in range(len(ticket) - 1):
if ticket[row][0] == ticket[row + 1][0] and ticket[row][1] == ticket[row + 1][1] - 4:
print(ticket[row])
Обратите внимание, что мы будем искать подходящее место вручную, это можно автоматизировать, но затраченное время на самом экзамене не окупится.
Важное замечание:Исходя из условия, мы ищем пустое место, которое находится ровно посередине от двух занятых мест.
Ответ: 9468 319
Задача 15
Грузчик Лёха закидывает мешки со строительным мусором в Газель. Мусора целая стройка, а Газель маленькая. Лёха хочет узнать, какое наибольшее количество мешков с мусором можно впихнуть в Газель, а также наибольший вес мешка, который можно погрузить в Газель при условии, что запихнули наибольшее количество мешков.
Входные данные
В первой строке входного файла находятся два числа: X - грузоподъёмность Газели в килограммах (натуральное число, не превышает 3000) и N - количество мешков с мусором (натуральное число, не превышает 1000). В следующих N строках находятся значения вес каждого мешка в килограммах (натуральные числа, не превышают 100), каждое в отдельной строке.
В качестве ответа прикрепите код решённой задачи, а также укажите два числа: наибольшее количество мешков и вес наибольшего мешка в Газели.
Пример входного файла:
100 4
70
50
20
40
Пример выходных данных:
2 70
Решение
Пример решения на языке 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:
X, N = map(int, st.split())
else:
a.append(int(st))
i += 1
bubble_sort(a)
s = 0
i = -1
while s <= X:
i += 1
s += a[i]
s -= a[i]
s -= a[i-1]
kol = i
while i < N and s+a[i] <= X:
i += 1
print(kol, a[i-1])
f.close()
Ответ, который выведет верная программа: 212 32
Задача 16
В магазине электроники "Эскалейдо" проводится рекламная акция. Каждый второй товар - бесплатно. Естественно, в руководстве магазина сидят умные люди, которые не хотят отдавать бесплатно Sony PS5 при покупке жвачки на кассе, поэтому хотят написать умный алгоритм, который поможет располагать пары "платный товар-бесплатный товар" таким образом, чтобы прибыль магазина была наибольшей. Задача: написать алгоритм, который определяет максимальную выручку магазина для каждого чека.
Входные данные: в первой строке вводится число N (натуральное, не превышает 1000) - количество товаров в чеке, в каждой из следующих N строк записано одно число (Натуральное, не превышает $10^6$) - стоимость купленного товара.
Выходные данные: одно число - максимальная выручка магазина с данного списка товаров.
Пример входных данных:
4
300
5000
600
900
Пример выходных данных:
5900
В качестве ответа на это задание прикрепите код программы, а также напишите ответ, который выдала программа для прикреплённого файла.
Решение
В итоговую стоимость пойдёт половина самых дорогих товаров. Поэтому нам необходимо отсортировать список по убыванию и посчитать сумму первой половины товаров (и ещё +1 товар для нечётного количества товаров). Пример решения на 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:
a.append(int(st))
i += 1
bubble_sort(a)
s = 0
for i in range(N//2+N%2):
s += a[i]
print(s)
f.close()
Для прикреплённого файла программа выведет: 13428503
Задача 17
В Высшей Школе Экологии на факультете Экологии K бюджетных мест. N абитуриентов подали документы на этот факультет. Определить проходной балл на факультете. Проходной балл - количество баллов у последнего прошедшего абитуриента.
Входные данные: в первой строке вводятся два числа. Число N (натуральное, не превышает 1000) - количество абитурентов, подавших документы. Число K (натуральное, не превышает N) - количество бюджетных мест. В каждой из следующих N строк записано одно число (Натуральное, не превышает 310) - баллы абитурента за экзамены.
Выходные данные: одно число - проходной балл на факультете.
Пример входных данных:
5 3
300
290
170
240
275
Пример выходных данных:
275
В качестве ответа на это задание прикрепите код программы, а также напишите ответ, который выдала программа для прикреплённого файла.
Решение
Отсортируем список по убыванию, а затем выведем значение элемента массива, который находится на K-ом месте. Пример решения на 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, K = map(int, st.split())
else:
a.append(int(st))
i += 1
bubble_sort(a)
print(a[K-1])
f.close()
Для прикреплённого файла программа выведет: 119
Задача 18
По результатам прошедшей олимпиады Google Code Jam участников награждают дипломами I, II и III степени. Если несколько участников набрали одинаковое количество баллов, они получают дипломы одинаковой степени. Призёром олимпиады считается участник, получивший диплом не хуже III степени. Определите количество призёров по результатам олимпиады.
Входные данные: в первой строке вводится число N (натуральное, не превышает 10000) - количество участников олимпиады, в каждой из следующих N строк записано одно число (Натуральное, не превышает 1000000) - количество баллов, набранных участником.
Выходные данные: одно число - количество призёров олимпиады.
Пример входных данных:
5
95
50
60
95
90
Пример выходных данных:
4
В качестве ответа на это задание прикрепите код программы, а также напишите ответ, который выдала программа для прикреплённого файла.
Решение
Отсортируем список по убыванию и будем считать количество участников, набравших три самых больших результата. Нюанс: для такого количества элементов массива стандартные алгоритмы сортировки работают ощутимо медленно. Здесь приходится либо смириться, либо использовать алгоритмы быстрой сортировки.
Решение на 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:
a.append(int(st))
i += 1
bubble_sort(a)
first_res = a[0]
winners = 0
i = 0
while a[i] == first_res:
winners += 1
i += 1
second_res = a[i]
while a[i] == second_res:
winners += 1
i += 1
third_res = a[i]
while a[i] == third_res:
winners += 1
i += 1
print(winners)
f.close()
Решение на C++:
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int compMax(int a, int b){ return a < b;}
int compMin(int a, int b){ return a > b;}
int main() {
ifstream file("file.txt");
int size;
file >> size;
int* arr = new int[size];
for (int i = 0; i < size; ++i)
file >> arr[i];
sort(arr, arr + size, compMin);
int count, winPlace = 1;
for (count = 0; winPlace <= 3; ++count)
if (arr[count] != arr[count + 1])
winPlace++;
cout << count;
return 0;
}
Ответ: 4
Задача 19
Работница прачечной Скайлер засовывает вещи в стиральную машину. Заказов очень много, все вещи за одну стирку не постираешь. Скайлер хочет постирать наибольшее количество вещей за один раз, а также узнать наибольший вес вещи, которую можно погрузить в стиральную машину при условии, что разместили наибольшее количество вещей.
Входные данные
В первой строке входного файла находятся два числа: X - грузоподъёмность стиральной машины в граммах (натуральное число, не превышает 3000) и N - количество вещей (натуральное число, не превышает 1000). В следующих N строках находятся значения вес каждой вещи в граммах (натуральные числа, не превышают 100), каждое в отдельной строке.
В качестве ответа прикрепите код решённой задачи, а также укажите два числа: наибольшее количество вещей и вес самой тяжёлой вещи.
Пример входного файла:
100 4
70
50
20
40
Пример выходных данных:
2 70
Решение
Пример решения на языке 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:
X, N = map(int, st.split())
else:
< style="margin-left: 60px;"p> a.append(int(st))i += 1
bubble_sort(a)
s = 0
i = -1
while s <= X:
i += 1
s += a[i]
s -= a[i]
s -= a[i-1]
kol = i
while i < N and s+a[i] <= X:
i += 1
print(kol, a[i-1])
f.close()
Ответ, который выведет верная программа: 223 28
Задача 20
Фанаты музыкальной группы Rammstein организуют поездку на концерт. Фанатов очень много, для их перевозки нужны автобусы. У организатора есть количество людей, а также информация о вместимости всех автобусов, свободных на данные дни. Определите наименьшее количество автобусов, необходимых для размещения всех фанатов, а также минимальное количество пустующих мест в автобусе для наименьшего количества автобусов.
Входные данные
В первой строке входного файла находятся два числа: X - количество фанатов (натуральное число, не превышает 3000) и N - количество автобусов (натуральное число, не превышает 1000). В следующих N строках находятся значения количества мест в каждом автобусе (натуральные числа, не превышают 100), каждое в отдельной строке.
В качестве ответа прикрепите код решённой задачи, а также укажите два числа: наименьшее количество автобусов и наименьшее количество пустующих мест.
Пример входного файла:
100 4
70
50
20
40
Пример выходных данных:
2 10
Решение
Пример решения на языке 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:
X, N = map(int, st.split())
else:
a.append(int(st))
i += 1
bubble_sort(a)
s = 0
i = -1
while s <= X:
i += 1
s += a[i]
kol = i+1
s -= a[i]
if s == X:
print(kol -1, 0)
else:
while i < N and s+a[i] >= X:
i += 1
print(kol, s+a[i-1]-X)
f.close()
Решение на C++:
#include <iostream>
#include <algorithm>
#include <fstream>
int comp(int a, int b){ return a > b;}
using namespace std;
int main() {
ifstream file("file.txt");
int fans, n;
file >> fans >> n;
int* arr = new int[n];
for (int i = 0; i < n; ++i) file >> arr[i];
sort(arr, arr + n, comp);
// Инициализируем счётчики количества автобусов
// и суммарное количество посадочных мест
int count = 0, sum = 0;
// увеличиваем количество посадочных мест
// на вместимость очередного автобуса
// пока суммарное количество не привысит
// количество фанатов
while(sum < fans) {
sum += arr[count];
count++;
}
// вычитаем вместимость последнего автобуса
// count был увеличен +1 после увеличения sum
// поэтому count - 1
sum -= arr[count - 1];
// начинаем поиск наименьшего кол-ва пустующих мест
// с конца списка (c наименьших по вместимости)
// ищем автобус, который вместил бы
// оставихся фанатов (fans - sum)
// прожолжаем поиск, пока вместимость очередного автобуса
// меньше, чем оставшееся количество фанатов
int index = n - 1; // индекс последнего автобуса
while (arr[index] < fans - sum)
index--;
cout << count << " " << sum + arr[index] - fans;
return 0;
}
Ответ, который выведет верная программа: 29 0
Рекомендуемые курсы подготовки
- Узнаешь как кодируется изображение
- Поймешь как решать 7 номер ЕГЭ
- Разберешься с паролями
- Потренируешь 11 и 4 номер ЕГЭ
на бесплатном курсе Турбо ЕГЭ
