Поймай проблему с самолетом из мирового финала ACM ICPC 2018

Question

Несколько дней я думаю об алгоритме этой проблемы. Я придумал разные решения, но ни одно из них не дало правильного результата. Я думал о направленном ациклическом графе, но кажется, что пассажир может совершить поездку туда и обратно, например, от станции 0 до 3, затем от 3 до 0, а затем от 0 до 1. Я был бы признателен, если кто-то может описать алгоритм (а не код) этой проблемы. Чтобы облегчить поиск, я поставил здесь и проблему.

Ваш самолет до финала ICPC вылетает в скором времени, и единственный способ добраться до аэропорта - на автобусе. К сожалению, некоторые водители автобусов рассматривают возможность забастовки, поэтому вы не знаете, сможете ли вы добраться до аэропорта вовремя. Ваша цель состоит в том, чтобы спланировать свое путешествие таким образом, чтобы максимизировать вероятность попадания в ваш самолет. У вас есть подробная карта города, которая включает в себя все автобусные станции. Вы находитесь на станции 0, а аэропорт - на станции 1. У вас также есть полное расписание, когда каждый автобус покидает свою начальную станцию ​​и прибывает на конечную станцию. Кроме того, для каждого автобуса вы знаете вероятность того, что он действительно будет работать в соответствии с графиком, в отличие от того, что его водитель бастует и выводит автобус из эксплуатации. Предположим, что все эти события являются независимыми. То есть вероятность того, что данный автобус будет работать в соответствии с планом, не изменится, если вы знаете, работает ли какой-либо из других автобусов в соответствии с планом. Если вы прибываете до времени отправления автобуса, вы можете перейти на этот автобус. Но если вы прибудете точно во время отправления, у вас не будет достаточно времени, чтобы сесть на автобус. Вы не можете заранее проверить, будет ли данный автобус работать в соответствии с планом - вы узнаете, только когда попытаетесь сесть в автобус. Таким образом, если два или более автобусов покидают станцию ​​одновременно, вы можете попытаться сесть только на один из них.

вход

количество станций в городе. Следующая строка содержит одно целое число k (1 ≤ k ≤ 10^18), обозначающее время, в которое вы должны прибыть в аэропорт. Каждая из следующих m строк описывает один автобус. Каждая строка содержит целые числа a и b (0 ≤ a, b

Выход

Покажите вероятность того, что вы поймаете свой самолет, предполагая, что вы следуете оптимальному курсу действий. Ваш ответ должен быть правильным с точностью до абсолютной ошибки 10^−6 .

Пример ввода

8 4
1000
0 1 0 900 0.2
0 2 100 500 1.0
2 1 500 700 1.0
2 1 501 701 0.1
0 3 200 400 0.5
3 1 500 800 0.1
3 0 550 650 0.9
0 1 700 900 0.1

Пример вывода

0.3124

Первая строка ввода содержит два целых числа m (1 ≤ m ≤ 10^6) и n (2 ≤ n ≤ 10^6), обозначающих количество шин и

Answer 1

Рассмотрим событие прибытия, связанное с каждой запланированной поездкой.

Если вы участвуете в прибытии, т. Е. Действительно успешно отправляетесь в запланированное путешествие, то вы попадаете на станцию ​​в момент прибытия и решаете, что делать дальше.

Для каждого прибытия вы можете легко рассчитать наилучшую вероятность совершения рейса, если вы уже знаете лучшие вероятности прибытия, которое вы могли бы получить следующим.

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

Процесс заканчивается с наилучшей вероятностью вашего первоначального прибытия на станцию ​​0.

Если вы умны в реализации, все это занимает O(N log N) времени.