26.05 Поиск мест на поле (билеты, саженцы, матрицы)
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы за ними все кресла с такими же номерами были свободны, а ряд находился как можно ближе к сцене. Сцена расположена перед первым рядом. Если в этом ряду таких пар мест несколько, найдите пару с наименьшими номерами мест. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть. Определите наименьший номер ряда и наименьший номер места для найденной пары мест.
Входные данные представлены в файле следующим образом. В первой строке входного файла находятся три
числа: 
– количество занятых мест в зале (целое положительное число, не превышающее 10000), 
– количество
рядов (целое положительное число, не превышающее 100 000) и 
– количество, мест в каждом ряду (целое
положительное число, не превышающее 100 000). В следующих 
строках находятся пары натуральных чисел: номер
ряда и номер места занятого кресла соответственно (первое число не превышает значения 
, а второе –
).
Запишите в ответе два целых числа: искомый номер ряда и наименьший номер места в найденной паре.
Пример входного файла:
7 7 8
1 1
6 6
5 5
6 7
4 4
2 2
3 3
Условию задачи удовлетворяют места 1 и 2 в ряду 3: за креслами 1 и 2 нет занятых мест.
Решение 1
f = open("26.txt")
n, m, k = map(int, f.readline().split())
row = [[] for i in range(k + 1)]
for i in range(n):
x, y = map(int, f.readline().split())
row[y].append(x)
mn_r = 10 ** 10# минимальный ряд
mn_i = 0 # минимальное место
for i in range(1, len(row) - 1):
# из двух (вертикальных) соседних рядов берем макс место
# (номер горизонтального ряда - mn_r), за ним все будут свободны;
# соответствеенно, чем он меньше, тем ближе к сцене
if max(row[i + 1] + row[i]) <= mn_r:
mn_r = max(row[i + 1] + row[i])
mn_i = i
print(mn_r+1, mn_i)
Решение 2
f = open("26.txt")
n, m, k = map(int, f.readline().split())
a = [[0, m + 1] for i in range(k)]
for i in f:
x, y = map(int, i.split())
a[y-1].append(x)
mx = 0 # максимальная длина пустых мест
mn_r = 0 # минимальный ряд
mn_i = 0 # минимальное место
for i in range(k - 1):
t1 = sorted(a[i], reverse=True)
t2 = sorted(a[i + 1], reverse=True)
spot1 = t1[0] - t1[1] - 1 # выясняем сколько пустых мест за текщум
spot2 = t2[0] - t2[1] - 1 # и за соседним
if min(spot1, spot2) > mx: # если пустых мест больше чем нашлось раньше
mx = min(spot1, spot2) # то обновляем максимум
mn_r = m - mx + 1 # соханяем номер ряда
mn_i = i # сохраняем номер места
print(mn_r, mn_i + 1)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
