Соседние места в концертном зале

Соседние места в концертном зале

 

Хотите готовиться со мной к ЕГЭ?
Пишите:  ydkras@mail.ru
Немного обо мне.

 

Язык Питон позволяет решать задачи ЕГЭ по информатике существенно проще, чем другие языки, которые можно использовать на ЕГЭ.

Рассмотрим задачу 26 варианта 1 с сайта Полякова:

(№ 4214) Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий условию.
Входные данные представлены в файле 26-59.txt следующим образом. В первой строке входного файла находится одно число: N – количество занятых мест (натуральное число, не превышающее 10 000). В следующих N строках находятся пары чисел: ряд и место выкупленного билета, не превышающие 100000. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.
Пример входного файла:

10
5 5
5 9
5 6
16 9
16 3
16 6
20 23
20 28
20 35
20 40

В данном примере есть следующие свободные места, удовлетворяющие условию: 7 и 8 в ряду 5, 4 и 5 в ряду 16, а также 7 и 8 в ряду 16. Выбираем наибольший номер ряда: 16 и наименьший номер места: 4. В ответе нужно указать: 16 4.

 

Упакуем номер ряда и номер места в одно целое число. Для этого умножим номер ряда на число, заведомо превышающее число мест в одном ряду, и сложим результат с номером места. Так как номер места не превышает 100 тысяч,  то в качестве множителя возьмём миллион: этого заведомо достаточно.

Для примера входной информации в условии задачи получаем следующие числа:

[5000005, 5000009, 5000006, 16000009, 16000003, 16000006, 20000023, 20000028, 20000035, 20000040]

Чтобы получить номер ряда, нужно разделить нацело число на миллион (x//1000000), а номер места -  взять остаток от деления числа на миллион (x%1000000).

Отсортируем полученный массив по возрастанию. Теперь соседние числа - это максимально близкие проданные места. Если они находятся в одном ряду, то их разность - это количество непроданных мест между проданными плюс 1. (Так как мы взяли множитель с солидным запасом, то исключаются ситуации, когда разность между первым местом в ряду и последним местом в предыдущем ряду будет мала.) Таким образом, нам достаточно рассмотреть весь массив и найти пары, разность между которыми равна трем. 

Проще всего отсортировать массив, воспользовавшись встоенной в Питон операцией sort.

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

Приведем полный текст программы, решающей данную задачу:

f=open("in.txt")
rm=[]
n=int(f.readline())
for i in range(n):
    r,m = map(int, f.readline().split())
    rm.append(r*1000000+m)
rm.sort()
r=0
m=0
for i in range(n-1):
    if rm[i+1] - rm[i] == 3 and rm[i]//1000000 > r:
        r=rm[i]//1000000
        m=rm[i]%1000000 + 1
print(r,m)

(c) Ю.Д.Красильников, 2021-2022 г.