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