Олимпиадные задачи по программированию

В этом номере мы разберем задачу «Автобус», предлагавшуюся в 2000 г. участникам XIII Всеукраинской олимпиады по информатике.

Условие

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

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

Входные данные

Первая строка входного текстового файла BUS.DAT включает число остановок N и число мест в автобусе M. Каждая i-я строка из N последующих содержит целое число — время движения от остановки i к остановке i+1 (N+1-я остановка — завод), количество рабочих K, уезжающих с i-й остановки, и время прихода каждого из них туда же в порядке появления (1 < M < 2000, 1 < N, K < 200000).

3 5

1 2 0 1

1 1 2

1 4 0 2 3 4

Выходные данные

Единственная строка выходного текстового файла BUS.SOL должна содержать минимальное время, необходимое для перевозки максимального числа рабочих.

4

Решение

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

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

Считывая данные из входного файла, следует определить время прихода последнего человека, т.е. тот момент, когда все люди уже стоят на остановках. Это будет максимум в двоичном поиске, обозначенный как T_max. Минимум — T_min — равен нулю. Будем считать, что если автобус задерживается на остановке, чтобы дождаться пассажиров, то это произойдет на первой остановке. Ведь если он подъедет к первой остановке, заберет людей и сразу же отъедет, а потом будет ждать на второй остановке, то за это время на первую еще могут прийти люди. А если ждать на первой, то люди со второй никуда не уйдут. Таким образом, мы получим минимум и максимум двоичного поиска.

Определим среднюю задержку как T = (T_min + T_max)/2. С помощью процедуры, описанной ниже, вычислим, сколько человек успеет до момента T добраться до первой остановки; для второй остановки задержка выйдет равной T + a[1], где a[1] — время следования от первой остановки до второй; для третьей задержка составит T + a[1] + a[2] и т.д. Если число пассажиров, севших в автобус на всех остановках, больше либо равно его вместимости, то нужно заменить T на (T_min + T)/2, а если в автобусе остались места, то T = (T + T_max)/2. Условие выхода будет следующим: если при некоторой задержке T автобус заполнен, а при задержке (T - 1) — нет, то ответ равен T. Его-то и следует записать в выходной файл.

Теперь рассмотрим вторую дихотомию, т.е. процедуру, определяющую, сколько человек успеет прийти на определенную остановку до установленного момента. Обозначим искомый ответ как P. В этой дихотомии максимум (P_max) — число людей на остановке, минимум (P_min) — ноль. Берем усредненного человека. Если время его прихода меньше, чем задержка, то P = (P + P_max)/2, а если он опоздает, то P = (P_min + P)/2. Условие выхода из поиска такое: если какой-либо человек вовремя добирается до остановки, а тот, что за ним, — нет, то ответом станет номер первого человека (P).

Отдельно необходимо рассмотреть случай, когда на автобус сядут все люди с остановки.