Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наименьшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий условию.
Входные данные.
В первой строке входного файла 26_8.txt находится одно число: N — количество занятых мест (натуральное число, не превышающее 10000). В следующих N строках находятся пары чисел: ряд и место выкупленного билета (числа не превышают 100000).
В ответе запишите два целых числа без пробелов и разделителей: сначала наименьший номер ряда, где нашлись обозначенные в задаче места и наименьший номер места в этом ряду.
Пример входного файла:
6
50 12
50 15
60 157
60 160
60 22
60 25
Для данного примера ответом будет являться пара чисел 50 и 13.
Решение (Excel/LibreOffice)
1. Сначала переносим столбец с рядами и местами из текстового файла в Excel, а затем сортируем столбец А по возрастанию, после сортируем столбец В по возрастанию. Таким образом получится, что в файле сначала идут ряды от наименьших к наибольшим с упорядоченными местами
2. Далее в ячейке С2 пишем следующую формулу: =ЕСЛИ(A2=A1;B2-B1;0). Так мы считаем разницу между местами, если они находятся в одном ряду.
3. Теперь пробегаемся по столбцу С и ищем первую попашуюся тройку. Она находится в ячейке С13 и связывает 136 ряд и места 114 и 117. Тогда наименьший ряд 136, а наименьшее место 115.
Решение (Python)
f = open(’26_8__1kubw.txt’)
n = int(f.readline())
a = [] # список координат занятых мест
for i in range(n):
x, y = [int(_) for _ in f.readline().split()] # считывание текущей строки
a.append([x, y])
a.sort()
ans = [0, 0]
for i in range(n-1): # проход по всем координатам занятых мест
# если ряд двух рядом стоящих в списке мест совпадает и при этом между ними есть 2 свободных места
if a[i][0] == a[i + 1][0] and a[i][1]+3 == a[i+1][1]:
row = a[i][0] # вычисляем ряд
place = a[i][1] + 1 # вычисляем минимальное свободное место
print(row,place)
break