Условие
Поезд, в котором К мест (с номерами от 1 до К), следует по магистрали через M населенных пунктов. мест. Дан список из N заявок на поездку, для каждой из которых известно, на какой станции пассажир собирается садиться, а на какой — выходить. При посадке на некоторой станции контроллер отдает предпочтение тому пассажиру, который едет дальше остальных, определяя место пассажира, как свободное с минимальным номером. При этом сначала осуществляется высадка пассажиров, а затем посадка.
Определите, сколько пассажиров смогут добраться до пункта своего назначения и на скольких перегонах в поезде будут заняты все места (перегон – это участок магистрали между соседними населенными пунктами).
Входные данные представлены в файле следующим образом. Первая строка входного файла содержит три натуральных числа: M (2 ≤ M ≤ 2000) – количество населенных пунктов со станциями на магистрали, K (1 ≤ K ≤ 1000) – количество мест в поезде и N (1 ≤ N ≤ 10000) – количество пассажиров, желающих проехать на поезде.
В каждой из последующих N строк располагаются пары чисел: сначала номер населенного пункта, откуда хочет начать свою поездку пассажир, затем номер населенного пункта, где пассажир собирается сойти с поезда.
В ответе запишите два числа: количество пассажиров, которые смогут добраться до пункта своего назначения, и количество перегонов, на которых в поезде будут заняты все места.
Пример работы программы:
При таких исходных данных добраться до нужного пункта смогут 4 пассажира ((2, 6), (2, 4), (3, 8), (4, 9)). При этом свободных мест не будет на перегонах 3 перегонах (3-4, 4-5 и 5-6).
Решение
Разберем пример
Правую границу можно уменьшить, если обратить внимание на то, что в R записанном в двоичной системе счисления, минимум на 2 разряда больше, чем в исходном числе N. Так как остаток от деления на 3 это числа 1 или 2. Умножая 1 на 3 — получим в двоичной системе счисления число 112, а 2 на 3 — число 6, соответственно в двоичной системе счисления 1102.
Отсюда следует, что можно перевести число 170 в двоичную систему счисления — 101010102, откинуть 2 разряда справа, перевести обратно в десятичную, и на всякий случай увеличить на 1. Получим правую границу равную 43.
Левой границей диапазона стало число 4, так как 3 кратно 3, и по алгоритму к нему нужно дописать 3 последние цифры двоичной записи, но 3 в двоичной системе счисления равно 112. Чтобы не противоречить алгоритму, начинаем с числа, в котором точно есть 3 цифры в двоичной записи
Перейдем к написанию алгоритма. Объявим переменную max_R, в которую будем записывать максимальное значение результатов выполнения алгоритма. Затем в цикле for выполним все действия алгоритма преобразования числа, для начала построим двоичную запись для числа N. Сделаем срез со второго символа, чтобы в R записались только цифры (0b не нужно).
#начало фрагмента
max_R = 0
for i in range(4, 171):
R = int(i)[2:]
#конец фрагмента
Дальше в зависимости от кратности N числу три изменим число, согласно алгоритму.
Если число кратно трем, то допишем к двоичной записи числа три последние цифры. Для этого сделаем срез [-3:]. Если число некратно, то найдем остаток от деления на три — i % 3. Затем умножим его на три. Переведем в двоичную системы счисления.
#начало фрагмента
if i % 3 == 0:
R += R[-3:]
else:
R += bin((i % 3) * 3)[2:]
#конец фрагмента
Оператор сложения с присваиванием += добавляет значение правого операнда к переменной и присваивает переменной результат.
Переведем полученное число в десятичную систему счисления.
#начало фрагмента
R = int(R, 2)
#конец фрагмента
Каждый полученный результат сравним с максимальным.
#начало фрагмента
if R <= 170:
max_R = max(max_R, R)
#конец фрагмента
Функция max() возвращает наибольшее значение элемента итерируемого объекта или самое большое из двух или более переданных позиционных аргументов.
Выведем результат на экран.
#начало фрагмента
print(max_R)
#конец фрагмента
Листинг программы
f = open('files/26-126.txt')
point, place, people = map(int, f.readline().split())
sp = []
full = 0
luckers = 0
for i in f:
sp.append(list(map(int, i.split())))
sp.sort()
train = []
for i in range(1, point + 1):
station = []
while len(sp) != 0 and sp[0][0] == i:
station.append(sp[0][1])
sp.pop(0)
station.sort(reverse=True)
while len(train) != 0 and train[0] == i:
luckers += 1
train.pop(0)
while len(train) != place and len(station) != 0:
train.append(station[0])
station.pop(0)
if len(train) == place:
full += 1
train.sort()
print(luckers, full)
Ответ
2873 267