Задание 26. Информатика. ЕГЭ. Шастин. 6.11.2024
- Просмотры: 77
- Изменено: 24 ноября 2024
(В. Лашин) На престижном турнире по пауэрлифтингу \(M\) тяжелоатлетов соревнуются в силе, поднимая гирю. Спортсмены поочерёдно подходят к стойке и выбирают вес для дальнейшего подъёма. Каждый из них знает свои возможности и, стремясь к победе, выбирает один максимально возможный вес, который способен поднять, из предложенного на мероприятии набора из \(N\) разновесных снарядов.
После проведения турнира для получения статистических данных организаторы вычислили среднее значение весов снарядов, которые были выбраны атлетами, а также вес самого популярного снаряда. Определите, чему равны эти две величины.
Примечание. Гарантируется, что каждый атлет сможет выбрать для себя подходящий вес.
Входные данные:
Первая строка содержит два целых числа: \(N\) — количество доступных снарядов и \(M\) — количество атлетов (\(1 \leqslant N \leqslant 50000, \,\, 1 \leqslant M \leqslant 50000\)). Следующие \(N\) строк содержат по одному целому числу — веса снарядов (от \(1\) до \(100~000\)). Последние \(M\) строк содержат по одному целому числу — максимальные веса, которые могут поднять атлеты (от \(1\) до \(100~000\)).
Выходные данные:
Запишите в ответе два целых числа — сначала целую часть среднего значения весов, которые выбрали атлеты, а затем вес снаряда, который был выбран максимальное количество раз.
Типовой пример организации данных во входном файле:
\(3 \,\, 3\)
\(50\)
\(100\)
\(70\)
\(60\)
\(80\)
\(65\)
При таких исходных данных первый и третий атлеты выберут вес \(50\), так как они не могут поднять \(70\) и \(100\). Второй атлет выберет вес \(70\), так как он не может поднять \(100\). Средний вес: \((50 + 50 + 70) / 3 = 56\). Чаще всего выбирали снаряд с весом \(50\). Ответ: \(56\) \(50\).
Решение:
Python
base = ''
fd = open(base + '26.txt')
N, M = map(int, fd.readline().split())
weights = []
pop = {}
for i in range(N):
weights.append(int(fd.readline().strip()))
weights.sort()
weights.append(weights[-1] * 1000)
for i in range(M):
w = int(fd.readline().strip())
l = 0
r = N
m = (r + l) // 2
while r - l > 1:
if w > weights[m]:
l = m
elif w < weights[m]:
r = m
else:
l = m
break
m = (r + l) // 2
mxw = weights[l]
pop[mxw] = pop.get(mxw, 0) + 1
pop_weight = 0
q = 0
s = 0
for k, v in pop.items():
s += k * v
if v > q:
q = v
pop_weight = k
print(s // M, pop_weight)
Ответ: \(49989 \,\, 65113\)