Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий условию. В ответе запишите два целых числа: номер ряда и наибольший номер места из найденных в этом ряду подходящих пар.
Входные данные.
В первой строке входного файла 9.txt находится одно число: N — количество занятых мест (натуральное число, не превышающее 10000). В следующих N строках находятся пары чисел: ряд и место выкупленного билета (числа не превышают 100000).
В ответе запишите два целых числа через пробел: сначала максимальный номер ряда, где нашлись обозначенные в задаче места и максимальный номер места.
Пример входного файла:
6
50 12
50 15
60 157
60 160
60 22
60 25
Для данного примера ответом будет являться пара чисел 60 и 159.
Решение (Excel/LibreOffice)
Откроем файл в электронной таблице, удалим первую строчку и отсортируем с помощью настраиваемой сортировки следующим образом: Столбец А по убыванию и столбец B по убыванию. В ячейку С1 запишем 0, а в ячейку С2 запишем следующую формулу:
=ЕСЛИ(И(A1=A2;B1-3=B2);1;0)
Сочетанием клавиш Ctrl+F откроем меню поиска и в столбце С найдем первую единицу. Как видно, между местами 225 и 228 ряда 20164 есть два свободных места. В ответ нужно указать максимальное место этой пары. Ответ: 20164 227
Решение (Python)
f = open(’D:/9.txt’)
n = int(f.readline())
a = []
for i in range(n):
a.append(list(map(int, f.readline().split())))
a = sorted(a)
mr = 0 # Наибольшее значение ряда
mm = 0 # Наибольшее значение места
for i in range(n-1):
# Во втором выражении разность должна быть равна 3,
# чтобы понять, что между двумя местами есть два свободных места
if a[i][0] == a[i+1][0] and abs(a[i][1] - a[i+1][1]) == 3:
mr = a[i][0]
# Номер второго занятого места минус 1
# это наибольший номер свободного места из пары
# (т.е. находящийся левее от второго занятого места из пары)
mm = a[i+1][1]-1
print(mr, mm)