26 - Обработка данных с помощью сортировки

Источники:

сайт Полякова (https://kpolyakov.spb.ru/)

демонстрационная версия станции КЕГЭ (https://kompege.ru/)

1) (№ 3768) (А. Кабанов) В текстовом файле записан набор натуральных чисел. Гарантируется, что все числа различны. Рассматриваются пары чисел из набора, между которыми в отсортированном массиве помещаются не более 100 чисел из того же набора. Определите количество пар с суммой кратной 10, а также наименьшее среднее арифметическое таких пар.

Входные данные представлены в файле 26-52.txt следующим образом. Первая строка содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 109.

В ответе запишите два целых числа: сначала количество пар, затем наименьшее среднее арифметическое.

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

В примере рассмотрим пары, между которыми помещаются не более 3 чисел из набора. В данном случае есть три подходящие пары: 2 и 8, 9 и 11, 14 и 16. В ответе надо записать числа 3 и 5.

Решение

f=open('26-52.txt','r')

n=int(f.readline())

m=[]

for i in range(n):

m.append(int(f.readline()))

m=sorted(m)

k=0

mi=10**9

for i in range(n-1):

for d in range(1,102):

if i+d<n:

sp=m[i]+m[i+d]

if sp%10==0:

k+=1

mi=min(mi,sp//2)

print(k,mi)

Ответ: 49867 10002885

2) (№ 3767) (А. Кабанов) В текстовом файле записан набор натуральных чисел. Гарантируется, что все числа различны. Рассматриваются пары чисел из набора, между которыми в отсортированном массиве помещаются не менее 100 чисел из того же набора. Определите количество пар с чётной суммой, а также среднее арифметическое чисел пары с наибольшей чётной суммой.

Входные данные представлены в файле 26-51.txt следующим образом. Первая строка содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 109.

В ответе запишите два целых числа: сначала количество пар, затем наибольшее среднее арифметическое.

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

В примере рассмотрим пары, между которыми помещаются не менее 3 чисел из набора. В данном случае есть четыре подходящие пары: 2 и 14, 2 и 16, 3 и 11, 8 и 16. В ответе надо записать числа 4 и 12.

Решение

f=open('26-51.txt','r')

n=int(f.readline())

m=[]

for i in range(n):

m.append(int(f.readline()))

m=sorted(m)

k=0

ma=0

for i in range(n-1):

for d in range(101,n-i):

sp=m[i]+m[i+d]

if sp%2==0:

k+=1

if ma<sp: ma=sp;msr=sp//2

print(k,msr)

Ответ: 6000514 99161667

3) (№ 2643) (Е. Джобс) Робот складывает монеты в ящики. Задача робота заполнить как можно большее количество ящиков монетами в количестве 100 штук. Роботу по конвейеру поступают корзины с монетами. В каждой корзине может быть от 1 до 99 монет. Известно, что робот может высыпать в ящик содержимое не более двух корзин. Необходимо определить, сколько ящиков можно заполнить монетами по 100.

Входные данные представлены в файле 26-j1.txt следующим образом. В первой строке записано число N – количество корзин, в каждой из последующих N строк число K – количество монет в каждой корзине.

В качестве ответа дать одно число – количество ящиков, заполненными 100 монетами.

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

При таких исходных данных можно заполнить только 2 ящика по 100 монет 10 + 90 и 66 + 34. Ответ: 2.

Решение

f=open('26-j1.txt','r')

n=int(f.readline())

m=[0]*100

for i in range(n):

m[int(f.readline())]+=1

k=0

for i in range(1,50): k+=min(m[i],m[100-i])

k+=m[50]//2

print(k)

Ответ: 3845

Решение в Excel

4) (№ 3770) В текстовом файле записан набор натуральных чисел. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наименьшее из средних арифметических таких пар.

Входные данные представлены в файле 26-53.txt следующим образом. Первая строка содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 109.

В ответе запишите два целых числа: сначала количество пар, затем наименьшее среднее арифметическое.

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

В данном случае есть две подходящие пары: 8 и 14 (среднее арифметическое 11) и 14 и 2 (среднее арифметическое 8). В ответе надо записать числа 2 и 8.

Решение (t = 23,19c.)

def pb(l,p,x): #бинарный поиск n в массиве m

while l<p-1:

i=(l+p)//2

if m[i]==x: return 1

if m[i]>x:p=i

if m[i]<x:l=i

return(0)

from time import *

ts=time()

f=open('26-53.txt')

n=int(f.readline())

m=sorted(map(int, f.readlines()))

k=0

maxx=max(m)

minsr=maxx

for i in range(n):

if m[i]%2==0:

for j in range(i+2,n):

if m[j]%2==0:

sr=(m[i]+m[j])//2

if pb(i,j,sr):

k+=1

minsr=min(minsr,sr)

print(k,minsr)

print(k,mi)

Ответ: 15 133397333

5) (№ 2944 Апробация 19 февраля 2022 года, Москва ) Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.

Известно, какой объём занимает файл каждого пользователя.

По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.

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

В первой строке входного файла z_26.txt находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10000) и N - количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое — в отдельной строке.

Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем — максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.

Решение

Вариант 1

f=open('z_26.txt')

s,n=map(int,f.readline().split())

m=[]

for i in range(n):m.append(int(f.readline()))

m.sort()

i=0

while s-m[i]>=0:

s-=m[i]

i+=1

k=i

s+=m[k-1]

while m[i]<=s:i+=1

print(k,m[i-1])

Вариант 2

Решение с помощью электронной таблицы 2944.XLSX

Ответ: 263 86

6) (№ 107 Джобс 07.09.2020) На вход программе поступает набор чисел в диапазоне [10; 10000]. Необходимо узнать сколько чисел в массиве находятся в диапазоне между средним значением и медианой, включая совпадающие с этими показателями значения.

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

В качестве ответа дать одно число – количество найденных чисел.

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

При таких исходных результатом является число 2. Среднее значение равно 50, медиана – 47

Медианой называется такое значение, что ровно половина из оставшихся элементов больше медианы и, соответственно, вторая половина меньше медианы.

Файлы к заданию: 26-107.txt

Решение

Вариант 1

m=sorted(list(map(int,open('26-107.txt').readlines()))[1:])

d1=sum(m)/len(m)

d2=m[len(m)//2]

if d1>d2:d1,d2=d2,d1

k=0

for i in m:

if d1<=i<=d2: k+=1

print(k)

Вариант 2

Решение с помощью электронной таблицы 107.XLSX

Ответ: 340

7) (№ 225 Джобс 14.09.2020) Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.

Известно, какой объём занимает файл каждого пользователя. Системный администратор старается сохранить файлы как можно большего размера. При этом используя выделенную память максимально эффективно – сохраняя файлы меньшего размера, если файлы большего не могут быть сохранены.

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

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

Запишите в ответе два числа: сначала число сохраненных файлов, затем размер наименьшего сохраненного файла.

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

100 4

При таких исходных данных можно сохранить три файла – 70, 25, 3. Поэтому ответ должен содержать два числа – 3 и 3

Файлы к заданию: 26-225.txt

Решение

Вариант 1

f=open('26-225.txt')

s,n=map(int,f.readline().split())

m=sorted(list(map(int,f.readlines())),reverse=True)

k=0

while sum(m[:k+1])<=s:k+=1

ost=s-sum(m[:k])

while not(ost in m)and ost!=0:ost-=1

if ost!=0: k+=1

print(k, ost)

Вариант 2

Решение с помощью электронной таблицы 225.XLSX

Ответ: 1054 732

8) (№ 476 Джобс 12.10.2020) В проекте «СкупойПлатитДважды» 1 января решено тратить на развитие 60% накоплений всех участников. При этом 20% самых богатых участников вносят 80% от своих накоплений, остальные участники вносят равный процент таким образом, чтобы общая сумма взносов всех участников составила 60%, обозначенные выше.

Запишите в ответе два целых числа: сумма взноса от всех «богатых» участников проекта и сумма взноса участника с самым небольшим размером накоплений.

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

В первой строке входного файла находится число N – количество участников проекта (натуральное число, 20 ≤ N ≤ 1000). В следующих N строках находятся значения – размер накоплений всех пользователей (все числа натуральные, не превышающие 1000), каждое в отдельной строке.

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

При таких исходных данных ответ должен содержать 2 числа – 60 и 4.

Файлы к заданию: 26-476.txt

Решение

Вариант 1

f=open('26-476.txt')

m=sorted(list(map(int,f.readlines()))[1:],reverse=True)

s0=sum(m)

k1=int(len(m)*0.2)

s1=sum(m[:k1])

s2=s0-s1

p2=(s0*0.6-s1*0.8)/(s0-s1)

print(int(s1*0.8),int(min(m)*p2))

Вариант 2

Решение с помощью электронной таблицы 476.XLSX

Ответ: 143518 4

9) (№ 2616) Маркетплейс с оптового склада каждый день отправляет заказанные товары в точки выдачи. Маркетплейс имеет множество видов различных товаров, каждый из которых имеет какой-то вес. Для отправки склад выделяет транспорт таким образом, чтобы отправить все возможные типы товаров и при этом отправить как можно больше каждого из них, но не более, чем определённый вес S. Нужно определить, сколько всего товаров останется на складе и тип товара с самым большим остатком. Если таких товаров несколько, вывести товар с наименьшим кодом.

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

В первой строке входного файла находится два числа через пробел: число N - количество доступных товаров (натуральное число, не превышающее 10000) и число S - вес, не более которого можно отправить каждый тип товара (натуральное число, не превышающее 108). В следующих N строках находятся по два числа через пробел: тип товара (натуральное число, не превышающее 109) и его вес (натуральное число, не превышающее 105).

Известно, что видов товаров не бывает более тысячи.

Запишите в ответе два числа: сколько всего товаров останется на складе и тип товара с самым большим остатком.

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

8 13

150 8

237 3

237 6

150 4

237 5

237 6

150 3

При таких исходных данных имеется всего два вида товаров ("150" и "237")

Товаров вида "150" можно погрузить три штуки (3, 3 и 4), останется 1 штука (8)

Товаров вида "237" можно погрузить две штуки (за 3 и 5), останется 2 штуки (6 и 6)

Поэтому ответ для приведённого примера: 3 237

Файлы к заданию: 26-2616.txt

Решение

Вариант 1

kt,kl=[],[]

f=open('26-2616.txt')

n,p=map(int,f.readline().split())

for i in range(n):

x,y=map(int,f.readline().split())

kt.append(x);kl.append(y)

ktu=sorted(set(kt))

ko=0

maxt=0

for i in ktu:

k=p

mt=[]

for j in range(len(kt)):

if kt[j]==i: mt.append(kl[j])

mt.sort()

j=0

while j<len(mt) and k-mt[j]>=0:

k-=mt[j]

j+=1

kot=0

for o in range(j,len(mt)):

kot+=1

if maxt<kot: kodt=i;maxt=kot

ko+=kot

print(ko,kodt)

Вариант 2

Решение с помощью электронной таблицы 26-2616.XLSX

Ответ: 391 15230058

10) (№ 2652) На кассе самообслуживания в гипермаркете за день покупатели пробивают самые различные товары. С каждого товара касса считывает штрихкод - это девятиразрядное натуральное число, возможно, имеющее какое-то количество ведущих нулей. Штрихкоды различных товаров отличаются. Маркетологу гипермаркета необходимо выяснить, какое количество различных товаров было куплено через кассу и какой товар покупали чаще всего.

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

В первой строке входного файла находится число N - количество пробитых за день штрихкодов (натуральное число, не превышающее 10 000). В следующих N строках находятся значения штрихкодов (все числа натуральные, меньше 109), каждое в отдельной строке.

Запишите в ответе два числа: количество различных проданных товаров и наибольшее количество товаров с совпадающим штрихкодом.

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

4858

112

4858

112

4858

При таких исходных данных имеется 3 различных товара. Наиболее часто встречающийся товар имеет штрихкод 4858. Он встречается 4 раза. Поэтому ответ для приведённого примера: 3 4.

Файлы к заданию: 26-2652.txt

Решение

Вариант 1

m=list(sorted(map(int,open('26-2652.txt').readlines())))[1:]

maxs=0

for i in set(m):maxs=max(maxs,m.count(i))

print(len(set(m)),maxs)

Вариант 2

Решение с помощью электронной таблицы 26-2652.XLSX

Ответ: 391 15230058

11) (№ 4742) Для анализа нагрузки сервера для каждого запроса в журнал записываются время начала и время завершения его обработки (в миллисекундах от момента начала исследований). Если начальное время равно 0, запрос начал обрабатываться до начала исследований, если конечное время равно 0, то обработка запроса закончилась после окончания исследований. Необходимо определить наименьшее количество запросов, которые сервер обрабатывал одновременно в течение суток, начиная с момента K, и суммарное время, в течение которого обрабатывалось это минимальное количество запросов.

Входные данные представлены в файле 26-66.txt следующим образом. Первая строка входного файла содержит количество записей N и время K. Каждая из следующих N строк содержит два целых числа: время начала и время завершения обработки одного запроса (в миллисекундах).

Запишите в ответе два числа: наименьшее количество запросов, которые сервер обрабатывал одновременно в течение указанных суток, и суммарное время, в течение которого обрабатывалось это минимальное количество запросов.

Пример входного файла (для заданного диапазона от 1000 до 6000):

6 1000

1300 2200

0 3700

1300 5700

0 0

5000 0

1800 3400

В данном случае наименьшее число запросов (2) выполнялось в интервале времени между 1000 и 1300, между 3700 и 5000, а также от 5700 до 6000 (общее время 300 + 1300 + 300 = 1900). Ответ: 2 1900.

Решение

Вариант 1

f=open('26-66.txt')

n,t=map(int,f.readline().split()) # Чтение значений N и T

m=[]

for i in range(n):

a,b=map(int,f.readline().split()) # Чтение значений нач. и конца процесса

m.append([a,1]) # Формирование двумерного списка с добавлением

if b!=0:m.append([b,-1]) # двух записей начала с кодом 1 и конца с кодом -1

m=sorted(m) # Сортировка полученного списка

for i in range(1,len(m)):

m[i][1]+=m[i-1][1] # подсчет количества процессов на интервалах

minp=n

for i in range(len(m)): # Определение мин. количества процессов после вр.T

if m[i][0]>=t: minp=min(minp,m[i][1])

mc=24*60*60*60*1000

m.append([mc,minp+1])

st=0

for i in range(1,len(m)): # Определение суммарного времени раб. с мин. загр.

if m[i][0]>=t and m[i-1][1]==minp:

if m[i-1][0]>=t:st+=m[i][0]-m[i-1][0]

else:st+=m[i][0]-t

print(minp,st)

Вариант 2

Решение с помощью электронной таблицы 26-4742.XLSX

Ответ: 5765 22703

12) (№ 4859 А.Кабанов) Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором наибольшее количеством подряд идущих мест, таких что все они уже распределены (заняты). В ответе запишите два целых числа: номер ряда и наибольшее количество подряд занятых мест.

Входные данные представлены в файле 26-69.txt следующим образом. В первой строке входного файла записано одно число: N – количество занятых мест (натуральное число, не превышающее 10 000). Каждая из следующих N строк содержит пару чисел, разделённых пробелом: ряд и место выкупленного билета (натуральные числа, не превышающие 100000).
Запишите в ответе два числа: сначала номер ряда, затем наибольшее количество подряд занятых мест.
Пример входного файла:

10
5 5
5 6
5 7
16 9
16 3
16 6
20 23
20 28
20 29
20 30

В данном примере максимальное количество подряд идущих занятых мест равно 3 (5 ряд места 5, 6, 7 и 20 ряд места 28, 29,30). Ответ: 20 3.

Решение

Вариант 1

f=open('26-69.txt')

n=int(f.readline())

m=[]

for i in range(n):

m.append(list(map(int,f.readline().split())))

m.sort()

maxm=0

b=[m[0][1]]

for i in range(1,len(m)):

if m[i-1][0]==m[i][0]:

if m[i][1]-m[i-1][1]==1:

b+=[m[i][1]]

if len(b)>=maxm:

maxm=len(b)

maxr=m[i][0]

else:

b=[m[i][1]]

else:

b=[m[i][1]]

print(maxr,maxm)

Вариант 2

Решение с помощью электронной таблицы 26-4859.xlsx

Ответ: 99 14

13) (№ 5037 Досрочный ЕГЭ-2022 ) В лесополосе осуществляется посадка деревьев: саженцы высаживают рядами на одинаковом расстоянии. Спустя некоторое время с помощью аэросъемки выясняют, какие саженцы прижились. Необходимо определить ряд с максимальным номером, в котором есть подряд ровно K неприжившихся саженцев при условии, что справа и слева от них саженцы прижились.
Входные данные представлены в файле 26-79.txt следующим образом. . В первой строке записаны два числа: N – количество занятых мест (натуральное число, не превышающее 10 000) и K – длина цепочки неприжившихся саженцев, которую нужно найти. Каждая из следующих N строк содержит сведения об одном прижившемся саженце – два натуральных числа, не превышающих 100 000: номер ряда и номер саженца в ряду.
В ответе запишите сначала наибольший номер ряда, затем наименьший номер неприжившегося саженца.
Пример входного файла::
6 3

40 30

40 34

50 125

50 129

50 64

50 68

В примере требуется найти 3 подряд идущих неприжившихся саженца. Ответ: 50 65.

Решение

Вариант 1

f=open('26-79.txt')

n,k=map(int,f.readline().split())

m=[]

for i in range(n):

m.append(list(map(int,f.readline().split())))

m.sort()

for i in range(1,len(m)):

if m[i][0]==m[i-1][0] and m[i][1]-m[i-1][1]-1==k:

maxr=m[i][0]

mp=m[i-1][1]+1

print(maxr,mp)

Вариант 2

Решение с помощью электронной таблицы 26-5037.xlsx

Ответ: 2261 5087

14) (№ 4935 А.Кабанов) Иван коллекционирует старые марки. Он собирает все марки, которые были выпущены в его стране за определённые годы. Иван знает, что в этот период каждый год выпускалось 8 различных типов марок. Иван решил проверить свою коллекцию и понять, скольких видов марок ему не хватает и для какого самого позднего года ему не хватает наибольшего количества марок до полного набора.
Входные данные представлены в файле 26-77.txt следующим образом. В первой строке входного файла записано число N - количество марок, которые собрал Иван (натуральное число, не превышающее 10 000). В следующих N строках записано по два числа: сначала год выпуска марки, затем – тип марки (натуральное число от 1 до 8).
Запишите в ответе два числа: количество видов марок, которых не хватает Ивану на интервале от 1961 до 1991 года, и самый поздний год, в котором ему не хватает наибольшего количества марок до полного набора.
Пример входного файла:
10

1962 1

1962 2

1962 3

1962 4

1962 6

1962 7

1962 8

1963 4

1964 1

1964 3

При таких входных данных будем считать, что Ивана интересуют только годы с 1962 по 1964.

В 1962 году ему не хватает 1 вида марок; в 1963 году не хватает 7 видов марок; в 1964 году не хватает 6 видов марок. Ответ: 14 1963.

Решение

Вариант 1

f=open('26-77.txt')

n=int(f.readline())

m=[]

for i in range(n):

m.append(list(map(int,f.readline().split())))

m.sort()

b=[[m[0][0],1]]

for i in range(1,n):

if m[i-1][0]==m[i][0]:

if m[i-1][1]!=m[i][1]: b[-1][1]+=1

else:b.append([m[i][0],1])

minm=8

s=0

for i in range(len(b)):

s+=8-b[i][1]

if minm>=b[i][1]:

minm=b[i][1]

ming=b[i][0]

print(s,ming)

Вариант 2

Решение с помощью электронной таблицы 26-4935.xlsx

Ответ: 38 1985

15) (№ 8482 В.Рыбальченко) В городе открылось тайм кафе. В нем есть К столиков. После каждого клиента столик необходимо убрать, на это уходит 5 минут. Уборка начинается в следующую минуту после того, как уходит гость. Новый клиент может сесть в следующую минуту после завершения уборки. Кафе работает с 7:00 и закрывается в 23:00. Все клиенты должны уйти не позже 23:00. За это время в него приходит N клиентов. (Гарантируется, что они придут не раньше 7:00, а планируют уйти не позже 23:00).

Каждого гостя при входе встречает администратор и подбирает для него стол с минимальным номером. Может случиться так, что несколько людей придет одновременно, тогда администратор в первую очередь подбирает столик для того, кто планирует сидеть меньшее время. В случае если все столы заняты, гость готов подождать не более 10 минут, при этом за столом он пробудет обязательно T минут (T – разница между временем прибытия и отбытия), в этом случае выбирается столик, который освободится раньше всего. Если таких несколько, выбирается с меньшим номером.

Определите, сколько клиентов получится обслужить за время работы кафе и номер столика, за который сядет последний клиент.

Входные данные (26_8482.txt)
На первой строке одно число N – количество гостей, пришедших за день. На второй строке одно число K – количество столиков в кафе. Далее N строк, в каждой из которых указано время, когда клиент пришел и время, до которого он планировал пробыть в кафе (время дано в минутах от начала дня).

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

10 20 # садится за первый стол

12 50 # садится за второй стол

25 43 # ждет 1 минут и садится за первый стол

38 70 # уходит, так как ближайший стол освободится через 11 минут

40 51 # ждет 10 минут и садится за первый стол

55 70 # уходит, так как не сможет просидеть планируемое время. (ресторан закроется)

Указанный пример для работы ресторана с 00:00 до 01:10. При таких данных кафе сможет обслужить первого, второго, третьего и пятого клиентов. А последний займет столик номер 1.

прим. Стол №1 был занят в промежутках: 10-25; 26-49; 50-66. Стол №2: 12-55.

Решение

f=open('26_8482.txt')

n=int(f.readline())

k=int(f.readline())

c=[0]*k

m=[]; tk=23*60;kp=0

for i in range(n): m.append(list(map(int, f.readline().split())))

m.sort()

for i in range(n):

fl,mint=0,min(c)

for p in range(k):

if m[i][0]>c[p]:c[p]=m[i][1]+5;fl=1;cp=p;break

if m[i][0]+10>min(c) and fl==0:

p=c.index(mint)

if mint+1+m[i][1]-m[i][0]<=tk: c[p]=mint+1+m[i][1]-m[i][0]+5;fl=1;cp=p

kp+=fl

print(kp,cp+1)

Ответ: 2496 45

16) (№ 10762 PRO100 ЕГЭ) Входной файл содержит расписание показа фильмов во всех кинотеатрах Москвы за весь прошедший месяц. Определите суммарное время, в течение которого показывался хотя бы один фильм.

Входные данные
В первой строке входного файла (26_10726.txt) находится натуральное число N (N ≤ 1000) – общее количество фильмов. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания фильмов в минутах с начала месяца. Каждое из чисел натуральное, не превосходящее 44640.

Выходные данные
Запишите в ответе два числа: суммарное время (в минутах), в течение которого показывался хотя бы один фильм и максимальную длину непрерывного отрезка времени (в минутах), в течение которого показывался хотя бы один фильм.

Типовой пример организации данных во входном файле
4
100 200
200 250
400 500
420 480

При таких исходных данных хотя бы один фильм показывался в промежутки времени [100; 250) и [400; 500). Суммарное время равно (250-100) + (500-400) = 250. Максимальный непрерывный отрезок времени, в течение которого показывался хотя бы один фильм равен 250-100 = 150.

Решение

f=open('26_10726.txt')

n=int(f.readline())

m=[0]*50000

for i in range(n):

a,b=map(int,f.readline().split())

for p in range(a,b):m[p]=1

mm=[m[0]]

for i in range(1,len(m)):mm.append((mm[-1]+m[i])*m[i])

print(sum(m),max(mm))

Ответ: 38032 3014

17) (№ 11605 Л.Шастин) Проспект длиной K метров освещён N фонарями, стоящими вдоль него. Администрация города выяснила, что количество включённых фонарей избыточно для освещения всего проспекта – какие-то из них можно выключить, чтобы сэкономить на тратах электроэнергии, таким образом, что проспект все равно останется освещён полностью. Входной файл содержит данные о метках начала и конца отрезков, освещаемых фонарями. Определите, какое максимальное количество фонарей можно выключить так, чтобы проспект остался освещён полностью, а также общее количество фонарей, которые, если их включить, освещают K-й метр проспекта.

Примечание: начало проспекта определено 1-м метром, конец – K-м метром.

Входные данные
В первой строке входного файла (26_11605.txt) находится два натуральных числа: N (N ≤ 10 000) – количество фонарей, стоящих вдоль проспекта, и K (K ≤ 10 000) – длина проспекта . Следующие N строк содержат пары чисел, обозначающих метку начала и метку конца отрезка проспекта, освещаемого фонарем. Каждое из чисел натуральное, не превосходящее 10 000.
Запишите в ответе два числа: максимальное количество фонарей, которые можно выключить, и количество фонарей, которые, если их включить, освещают K-й метр проспекта.

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

5 50

1 30

28 50

20 40

1 10

15 50

При таких исходных данных можно выключить 3 фонаря: второй, третий и четвёртый. K-й метр может быть освещен 2 фонарями (если они включены): фонарь {28, 50} и фонарь {15, 50}. Ответ: 3 2.

Идея решения

Считать данные и выполнить подсчет количество фонарей освещают точку K
На основе списка m создать список a, выбирая записи с одинаковыми точками начального освещения и максимальной зоной освещенности
Создать модель парка (список b) и перемещаясь по границам освещенности определять в диапазоне текущей освещенности фонарь с максимальным захватом зоны с права от границы диапазона. Обратить внимание на ситуацию, когда одна граница освещенности соприкасается с другой границей (без перекрытия).

Решение

f=open('26_11605.txt')

n,k=map(int,f.readline().split())

m=[]

kfs=0

for i in range(n):

m.append(list(map(int,f.readline().split())))

if m[-1][1]==k:kfs+=1

m.sort()

a=[m[0]]

for i in range(1,n):

if a[-1][0]==m[i][0]:a[-1][1]=m[i][1]

else:a.append(m[i])

b=[0]*(k+1)

for i in range(len(a)): b[a[i][0]]=a[i][1]

kk=b[1]

kf=1

while kk!=k:

maxf=max(b[:kk+2])

kf+=1

kk=maxf

print(n-kf,kfs)

Ответ: 9887 3

18) (№ 9711 Danov2307 А.Богданов) Проводится вычислительный эксперимент для определения необходимого количества самокатов на разных парковках города в начальный момент времени. Всего парковок M, пронумерованных с 1 до М. Входной файл содержит N заявок на аренду самокатов в случайном порядке. В каждой заявке указано время аренды в минутах от начала эксперимента, продолжительность аренды, а также номер парковок старта и финиша. На начало эксперимента на парковках устанавливается минимальное количество самокатов, которых достаточно для удовлетворения всего спроса. Будем считать, что заряда самоката хватает на весь день и самокат может быть арендован со следующей минуты после финиша.

Входные данные (26_9711.txt): в первой строке M и N. Далее N строк, в каждой из которых время старта в минутах, длительность в минутах, номер парковки старта и номер парковки финиша

Определите, в какой момент (в минутах от начала эксперимента) было арендовано максимальное количество самокатов и номер парковки, на которой нужно установить максимальное количество самокатов.

Идея решения

Решение

f=open('26_9711.txt')

M,n=map(int,f.readline().split())

m=[]

for i in range(n):

t,dt,p1,p2=map(int,f.readline().split())

m.append([t,p1,-1]); m.append([t+dt,p2,1])

m.sort()

p=[0]*(M+1)

p[m[0][1]]+=m[0][2]

maxk=maxa=0

at=1

for i in range(1,n):

if m[i][0]!=m[i-1][0]:

if maxa<at: maxt=m[i-1][0]; maxa=at

for j in range(1,M+1):

if maxk>p[j]: maxk=p[j]; maxp=j

p[m[i][1]]+=m[i][2]

at-=m[i][2]

print(maxt,abs(maxp))

Ответ: 400 13

19) (№ 8512 Апробация 17.05) Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.

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

В первой строке входного файла (26_8512.txt) находится натуральное число K, не превышающее 1000, – количество ячеек в камере хранения. Во второй строке – натуральное число N (N ≤ 1000), обозначающее количество пассажиров. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: указанное в заявке время размещения багажа в ячейке и время освобождения ячейки (в минутах от начала суток).

Запишите в ответе два числа: количество пассажиров, которые смогут воспользоваться камерой хранения, и номер последней занятой ячейки.

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

30 60

40 1000

59 60

61 1000

1010 1440

При таких исходных данных положить вещи в камеру хранения смогут первый, второй, четвёртый и пятый пассажиры. Последний пассажир положит вещи в ячейку 1, так как ячейки 1 и 2 будут свободны.

Идея решения

Решение

f=open('26_8512.txt')

k=int(f.readline())

n=int(f.readline())

m=[]

for i in range(n): m.append(list(map(int, f.readline().split())))

m.sort()

a=[0]*k

kp=0

for i in range(n):

if m[i][0]>min(a):

kp+=1

for p in range(k):

if a[p]<m[i][0]: a[p]=m[i][1]; ip=p; break

print(kp,ip+1)

Ответ: 389 133

20) (№ 4687 М.Ишимов) Семья М. собирается купить билеты на самолет, чтобы полететь на отдых. Они выбрали рейс с двухэтажным самолётом. В семье, помимо папы и мамы, имеется двое детей, и билеты нужно купить так, чтобы вся семья летела в одном ряду. Каждый из них боится высоты, поэтому места у окон покупать нельзя. Места у окон считаются самые крайние места в каждом ряду (первое и последнее).

Известно, какие места уже заняты. Найдите ряд с наибольшим номером, в котором можно забронировать подходящие места для всей семьи. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. В ответе запишите два числа: максимальный номер ряда и общее количество таких рядов, в которых можно забронировать подряд идущие свободные места без мест у окон.

Входные данные представлены в файле следующим образом. В первой строке входного файла находится два числа: N – количество занятых мест (натуральное число, не превышающее 20 000) и K – количество мест в каждом ряду самолета (натуральное число, не превышающее 10). Каждая из следующих N строк содержит три натуральных числа, не превышающих 100 000: номер этажа, номер ряда и номер занятого места в этом ряду.

Запишите в ответе два числа: максимальный номер подходящего ряда, в котором куплено хотя бы одно место, и общее количество таких рядов, в которых можно забронировать четыре подряд идущие свободные места без мест у окон.

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

7 6

1 50 2

2 23 1

1 50 6

1 1 1

2 30 5

2 23 6

1 1 6

При таких исходных данных есть два подходящих ряда: 1-й ряд на 1-м этаже и 23-й ряд на 2-м этаже. Ответ: 23 2.

Файлы к заданию:26_4687.txt

Идея решения

Решение

f=open('26_4687.txt')

n,k=map(int,f.readline().split())

m=[]

km=maxr=0

for i in range(n):

m.append(list(map(int,f.readline().split())))

m.sort()

r=['*']*(k+1); z=m[0][0]; rt=m[0][1]; r[m[0][2]]='X'

for i in range(1,n):

if rt==m[i][1]: r[m[i][2]]='X'

else:

if '****' in ''.join(r[2:-1]):maxr=max(maxr,rt);km+=1

rt=m[i][1]; z=m[i][0]; r=['*']*(k+1); r[m[i][2]]='X'

if '0000' in ''.join(r[2:-1]):maxr=max(maxr,rt);km+=1

print(maxr,km)

Ответ: 9988 2408

21) (№ 7012 Л.Шастин) В магазине имеется N товаров. Известны цена каждого из товаров и его текущий статус (продан или не продан). Товары разделены на две категории - дорогие и дешёвые. Дорогими считаются товары, цена на которые превышает средний чек M. Остальные, соответственно, являются дешёвыми (цена на них не превышает M). Необходимо найти сумму выручки магазина за продажу самого популярного товара среди дорогих и самого популярного товара среди дешёвых (если известно, что популярность товара тем выше, чем больше раз он был продан), а также сколько товаров этих двух видов остались в наличии.

Входные данные представлены в файле 26-136.txt следующим образом. В первой строке входного файла находится два натуральных числа, не превышающих 10000: N – количество товаров и M – средний чек. В следующих N строках записано по два числа: цена товара (она же вид товара) и статус товара (0 – не продан; 1 – продан).

Запишите в ответе два целых неотрицательных числа: сумму выручки магазина за продажу самого популярного товара среди дорогих и самого популярного товара среди дешёвых, а также количество товаров этих двух видов, оставшихся в наличии.

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

5 60

43 1

90 1

43 0

43 1

90 0

Для данного примера цена самого популярного дорогого товара – 90 (продан 1 раз), а самого популярного из дешёвых – 43 (продан дважды). Их сумма = 90 + 43·2 = 176. Продано товаров = 3, всего их в наличии было 5. Осталось = 5 - 3 = 2. Ответ: 176 2.

Идея решения

Решение

f=open('26-136.txt')

n,t=map(int,f.readline().split())

m1,m2=[],[]

for i in range(n):

x,y=map(int,f.readline().split())

m1.append(x);m2.append(y)

k=max(m1)

b0,b1=[0]*(k+1),[0]*(k+1)

for i in range(n):

it=m1[i]

if m2[i]==1:b1[it]+=1

else:b0[it]+=1

max0=b1.index(max(b1[:t+1]))

max1=b1.index(max(b1[t+1:]))

print(max0*b1[max0]+max1*b1[max1], b0[max0]+b0[max1])

Ответ: 2320 51

22) (№6191 Р.Сорокин) В период, когда действовали ограничения, направленные на предотвращение распространения новой инфекции, при продаже мест в кинотеатрах оставляли по одному свободному месту между зрителями. Места, расположенные рядом, можно было купить только одновременно, т.е. одна семья (или компания друзей) могла сидеть вместе при одновременной покупке билетов.
Известно, что кинозал имеет N рядов по M мест в каждом. Места и ряды нумеруются по порядку, начиная с единицы. Известно, что K мест уже выкуплены (заняты). По приведенным данным о уже занятых местах требуется определить
а) какое наибольшее количество мест сможет продать кинотеатр при условии соблюдения ограничений;
б) в каком ряду количество мест, которое сможет продать кинотеатр, будет наибольшим. Если таких рядов несколько, требуется указать наименьший номер ряда.
Входные данные представлены в файле 26-106.txt следующим образом. В первой строке файла через пробел записаны три натуральных числа: N – количество рядов в кинотеатре (1 ≤ N ≤ 10 000), M – количество мест в ряду (1 ≤ M ≤ 10 000), K – количество занятых мест (1 ≤ K ≤ 10 000). Далее в файле записаны K строк, по два числа в каждой. Первое число в паре означает номер ряда, второе – номер занятого места в этом ряду.
Пример входного файла::

3 10 4
1 3
1 4
1 7
2 5

Наибольшее количество мест удастся продать, если билеты будут покупать большие компании людей, тогда их можно будет посадить рядом.

Для наглядности на рисунке серым цветом обозначены уже занятые места, желтым цветом — места, билеты на которые удастся продать в наиболее благоприятном случае. Максимальное количество проданных билетов для приведенного примера будет равно 20. Номер ряда, где удастся продать максимальное количество билетов – 3. Ответ: 20 3.

Идея решения

Решение

f=open('26-106.txt')

n,m,k=map(int,f.readline().split())

r=set()

b=[];maxr=0;maxm=0

for i in range(k):

ir,im=map(int,f.readline().split())

r.add(ir)

b.append([ir,im])

kol=(n-len(r))*m

for i in range(1,n+1):

if i not in r:maxr=i;maxm=m;break

b.sort()

rt=0

t=[0]*(m+1)

for i in range(k):

if rt!=b[i][0]:

kol+=sum(t[1:])

if sum(t[1:])>maxm:maxm=sum(t[1:]);maxr=rt

t=[1]*(m+1);rt=b[i][0]

t1=b[i][1]

t[t1]=0

if t1<m:t[t1+1]=0

if t1>1:t[t1-1]=0

kol+=sum(t[1:])

print(kol,maxr)

Ответ: 997006 6

23) (№4519) На закупку товаров типов A, B, C, D и E выделена определённая сумма денег. Эти товары есть в продаже по различной цене. Необходимо на выделенную сумму закупить как можно больше товаров пяти типов (по общему количеству). Если можно разными способами купить максимальное количество пяти типов товаров, то нужно выбрать способ, при котором будет закуплено как можно больше товаров типа B. Если при этих условиях есть несколько способов закупки, нужно потратить как можно меньше денег.
Определите, сколько будет закуплено товаров типа B и сколько денег останется.
Входные данные представлены в файле 26-64.txt следующим образом. Первая строка входного файла содержит два целых числа: N – общее количество товаров и M – сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена товара в рублях) и символ (латинская буква), определяющий тип товара. Все данные в строках входного файла отделены одним пробелом.
Запишите в ответе два числа: сначала количество закупленных товаров типа B, затем оставшуюся неиспользованной сумму денег.
Пример входного файла:

6 110
40 E
50 A
50 B
30 C
20 B
10 A

В данном случае можно купить не более четырёх товаров, из них не более двух товаров типа B. Минимальная цена такой покупки 110 рублей (покупаем товары 10 A, 20 B, 30 C, 50 B). Останется 0 рублей. Ответ: 2 0.

Идея решения

Решение

f=open('26-64.txt')

n,m=map(int,f.readline().split())

a=[]

for i in range(n):

x,y=f.readline().split(); a.append([int(x),y])

a.sort(); k,mt=0,m

while mt-a[k][0]>=0:mt-=a[k][0];k+=1

kb=0;c=[];b=[]

for i in range(k+1):

if a[i][1]=='B':kb+=1

for i in range(k+1):

if a[i][1]!='B':c.append(a[i][0])

for i in range(k+1,n):

if a[i][1]=='B':b.append(a[i][0])

c=c[::-1];i=0

while mt+c[i]-b[i]>=0 and i<len(c):

kb+=1;mt=mt+c[i]-b[i];i+=1

print(kb,mt)

Ответ: 41 74

24) (№6320 Л.Евич) В тренажёрном зале N тренажёров, работающих c 10:00 до 22:00. Все тренажёры пронумерованы от 1 до N. Каждый из M посетителей зала может воспользоваться любым тренажёром. Посетитель всегда выбирает свободный тренажёр с наименьшим номером; если свободных тренажёров нет, он уходит. Если в одно и то же время пришли несколько посетителей, то они занимают тренажёры в том порядке, в котором расположены данные в файле. Для каждого посетителя известно время начала и время окончания его тренировки. Время тренировки на тренажёре другого посетителя может начаться со следующей минуты после окончания времени тренировки предыдущего посетителя.
Определите количество посетителей тренажерного зала, которые могли воспользоваться тренажёрами за время работы зала и номер тренажёра, на котором начал свою тренировку последний посетитель.
Входные данные представлены в файле 26-115.txt следующим образом. В первой строке входных данных задается два числа: N - количество тренажёров и M – количество посетителей зала. В каждой из последующих M строк содержится информация по каждому посетителю: время начала и время окончания тренировки на тренажёре (в минутах от начала суток).
Запишите в ответе два числа: количество посетителей тренажерного зала, которые могли воспользоваться тренажёрами за время работы зала и номер тренажёра, на котором проводил свою тренировку последний посетитель.
Пример входного файла:

2 5
601 690
620 642
640 645
650 670
680 700

При этих исходных данных 1-й тренажёр с самого начала занимает первый посетитель. Посетители со временем прихода 620, 650 и 680 работают один за другим на 2-м тренажёре. Посетитель со временем прихода 640 уходит, потому что в этот момент свободных тренажёров нет. Всего обслужено 4 посетителя, последний начал работу на тренажёре 2. Ответ: 4 2.

Идея решения

Решение

f=open('26-115.txt')

p,n=map(int,f.readline().split())

m=[]

for i in range(n):

m.append(list(map(int,f.readline().split())))

for j in range(n):

for i in range(n-j-1):

if m[i][0]>m[i+1][0]:

m[i],m[i+1]=m[i+1],m[i]

tr=[0]*p

k=0

for i in range(n):

if m[i][0]>min(tr) and m[i][1]<=1320:

for z in range(p):

if m[i][0]>tr[z]:

tr[z]=m[i][1]

k+=1

ppz=z+1

break

print(k,ppz)

Ответ: 1269 41

25) (№5310 М.Шагитов) Для экрана размером 10000 х 10000 пикселей используется цветовая модель RGB. Графический адаптер считывает пиксели экрана и записывает в файл данные всех пикселей, кроме тех, для которых установлен белый цвет. Для каждого пикселя записывается номер строки, номер позиции в строке и цвет в виде шестнадцатеричного кода (например, #FFFFFF – белый цвет). Найдите все пиксели с кодом #00FF00, слева и справа от которых записаны по три подряд идущих пикселя с кодом #0000FF. Определите общее количество подходящих пикселей, а также номер строки, в которой есть наибольшее количество таких пикселей. Гарантируется, что на экране есть хотя бы один подходящий пиксель.
Входные данные представлены в файле 26-87.txt следующим образом. В первой строке входного файла записано натуральное число N – общее количество записей (1 ≤ N ≤ 100 000). В каждой из следующих N строк находятся два натуральных числа, не превышающих 10000, и шестнадцатеричный код, разделённые пробелом: номер строки, номер позиции в строке уникального пикселя и цвет пикселя.
Запишите в ответе два числа: общее количество подходящих пикселей на экране и наибольший номер строки, с максимальным количеством подходящих пикселей.
Пример входного файла:

11
1 1 #00FF00
1 3 #00FF00
2 1 #0000FF
2 2 #0000FF
2 3 #0000FF
2 4 #00FF00
2 5 #0000FF
2 6 #0000FF
2 7 #0000FF
3 3 #00FF00
3 5 #00FF00

В данном случае есть один подходящий пиксель (строка 2, позиция 4) с кодом цвета #00FF00, окруженный с двух сторон тройками пикселей с кодом #0000FF. Ответ: 1 2.

Идея решения

Решение

Вариант 1 (t = 66.5 c.)

f=open('26-87.txt')

n=int(f.readline())

mm=[[' ']*10000 for i in range(10000)]

for i in range(n):

a,b,c=f.readline().split()

mm[int(a)-1][int(b)-1]=c

fk=['#0000FF']*3+['#00FF00']+['#0000FF']*3

maxk=sk=0

for i in range(10000):

k=0

for j in range(10000-6):

if fk==mm[i][j:j+7]:k+=1

sk+=k

if maxk<=k: maxk=k;ns=i+1

print(sk,ns)

Вариант 2 (t = 15.999 c.)

f=open('26-87.txt')

n=int(f.readline())

m=[]

for i in range(n):

a,b,c=f.readline().split()

m.append([int(a),int(b),c])

m=sorted(m)

fk=['#0000FF']*3+['#00FF00']+['#0000FF']*3

mk=['']*10000

ns=-1

ks=maxk=k=0

for i in range(n):

a,b,c=m[i]

if ns==a: mk[b]=c

else:

for p in range(10000-6):

if fk==mk[p:p+7]:

k+=1

ks+=k

if maxk<=k: maxk=k;mps=ns

ns=a;mk[b]=c;k=0;mk=['']*10000

for p in range(10000-6):

if fk==mk[p:p+7]:

k+=1

ks+=k

if maxk<=k: maxk=k;mps=ns

print(ks,mps)

Ответ: 1487 9980

26) (№7577 ЕГЭ-2024) В магазине продаётся N товаров нескольких артикулов. Товары одного артикула имеют одинаковую цену. Учёт товаров ведётся поштучно, для каждой единицы товара известен её текущий статус (продана или нет). Товары разделены на две категории: дорогие и дешёвые. Дорогими считаются товары, цена на которые превышает среднюю цену (среднее арифметическое) всех товаров в базе данных магазина без учёта их текущего статуса, остальные товары считаются дешёвыми. Лидером продаж называется товар с таким артикулом, наибольшее количество единиц которого продано. Лидер продаж выбирается среди дорогих товаров, а если продано одинаковое количество дорогих товаров с разными артикулами, лидером выбирается товар с наибольшей ценой. Если и таких товаров несколько, лидер продаж – тот из них, которого осталось меньше всего. Найдите суммарную выручку магазина от реализации товара – лидера продаж, а также оставшееся количество товара этого артикула.

Входные данные представлены в файле 26-152.txt следующим образом. В первой строке входного файла находится натуральное число N, не превышающее 10 000 – количество товаров в базе данных магазина. В каждой из следующих N строк находится три числа, разделённых пробелами: артикул товара (натуральное число, не превышающее 100 000), его цена (натуральное число, не превышающее 10 000) и статус (0, если товар уже продан, и 1, если ещё не продан).

Запишите в ответе два целых числа: сумму выручки от реализации товара – лидера продаж, а также количество товара этого артикула, оставшееся в наличии.

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

10 100 1

3 10 0

10 100 0

2 10 1

10 100 0

3 10 1

11 100 0

1 200 0

При таких исходных данных дорогими являются товары с ценой 100 и 200 рублей. Больше всего (2 шт.) было продано товара артикула 10 на сумму 200, в продаже осталась одна единица такого товара. Ответ: 200 1.

Идея решения

Решение (t = 0.25 c.)

f=open('26-152.txt')

n=int(f.readline())

m=[[0,0,0] for i in range(100001)]

st=0

for i in range(n):

a,b,c=map(int,f.readline().split())

st+=b

m[a][1]=b

m[a][2]+=1

m[a][0]+=abs(c-1)

st=st/n

m1=[]

for i in range(len(m)):

if m[i][1]>st:m1.append(m[i])

m=sorted(m,key = lambda sub:(-sub[0],-sub[1],sub[2]))

print(m[0][1]*m[0][0],m[0][2]-m[0][0])

Ответ: 43656 36

27) (№4439 А.Богданов) В некотором государстве правительство выделяет K специальностей для обучения студентов. На эти места претендуют N абитуриентов. Для каждой специальности задано количество мест. Для каждого абитуриента известны его баллы и одна выбранная им специальность. Зачисление осуществляется в одну волну. На направление зачисляются абитуриенты с максимальными баллами. Требуется определить общее количество зачисленных абитуриентов и минимальный балл студента, зачисленного на специальность с максимальным конкурсом.

Входные данные представлены в файле 26-60.txt следующим образом. В первой строке через пробел два целых числа K и N. В следующих K строках записано по одному числу – количеством мест по каждой специальности. Следующие N строк содержат пары чисел: баллы студента (до 300 включительно) и код выбранной специальности (начиная с 0).

В ответе запишите два целых числа: общее количество зачисленных абитуриентов и минимальный балл студента, зачисленного на специальность с максимальным конкурсом.

Идея решения

Решение (t = 0.25 c.)

f=open('26-60.txt')

k,n=map(int,f.readline().split())

ms=[]

for i in range(k):

ms.append(int(f.readline()))

ma=[]

for i in range(n):

a,b=map(int,f.readline().split())

ma.append([b,a])

ma=sorted(ma, key = lambda sub:(sub[0],-sub[1]))

mk=[0]*k

ks=0

mz=[[] for i in range(k)]

for i in range(n):

a,b=ma[i]

mk[a]+=1

if len(mz[a])<ms[a]:mz[a].append(b);ks+=1

maxk=0

for i in range(k):

kon=mk[i]/ms[i]

if kon>=maxk:maxk=kon;maxi=i

print(ks,mz[maxi][-1])

Ответ: 55255 266

Page updated

Google Sites

Report abuse