Олімпіадні задачі

Дата: Нд, 08.02.2009, 18:26 | Повідомлення № 1

Новий користувач

Повідомлень: 3

Нагороди: 0

Рейтинг: 0

Службовий автобус з "Фабрика меблів "НОВА" здійснює один рейс по встановленому маршруту і, у випадку наявності вільних місць, підбирає робітників, котрі чекають на зупинці та відвозить їх на фабрику. Автобус також може чекати на зупинці робітників, які ще не прийшли. Відомо час приходу кожного робітника на свою зупинку і час проїзду автобуса від кожної зупинки до наступної. Автобус приходить на першу зупинку в нульовий момент часу. Тривалість посадки робітників в автобус вважаємо нульовою.
Завдання. Написати програму BUS, яка визначить мінімальний час, за який автобус привезе максимально можливу кількість робітників.
Вхідні дані.
Вхідний текстовий файл BUS.DAT в першому рядку містить кількість зупинок N i кількість місць в автобусі М. Кожний наступний і-й рядок з N рядків містить ціле число – час руху від зупинки і до зупинки і+1 (N+1-ша зупинка – фабрика), кількість робітників К, які прийдуть на і-ту зупинку, і час приходу кожного робітника на цю зупинку в порядку приходу (1≤М≤2000,1≤N,К≤200000).
Приклад вхідних даних.
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4
Вихідні дані.
Єдиний рядок вихідного текстового файлу BUS.SOL повинен містити мінімальний час, який необхідний для перевезення максимальної кількості робітників.
Приклад вихідних даних. 4

hottabych

Дата: Пн, 09.02.2009, 22:44 | Повідомлення № 2

Новий користувач

Повідомлень: 3

Нагороди: 0

Рейтинг: 0

Це районна олімпіада розвязку немає.

Додано (09.02.2009, 21:44)
---------------------------------------------
В інтернеті

hottabych

Дата: Вт, 10.02.2009, 20:23 | Повідомлення № 3

Новий користувач

Повідомлень: 3

Нагороди: 0

Рейтинг: 0

CN, де її розвязок???

dpi

Дата: Ср, 11.02.2009, 14:56 | Повідомлення № 4

Досвідчений вчитель

Повідомлень: 1438

Нагороди: 1

Рейтинг: 39

Quote (CN)

дают такие задачи на олимпиаду

Имеете ввиду легкие или трудные?

dpi

Дата: Ср, 11.02.2009, 19:27 | Повідомлення № 5

Досвідчений вчитель

Повідомлень: 1438

Нагороди: 1

Рейтинг: 39

Как в Виннице не смотрел.
Думаю так:
0 1 2 0 2 3 4 (время ожидания пасс. на каждой остановке)
На каждой последующей отнимаем время в пути: 0 1 1 0 0 1 2 (ехать то надо)
Три пассажира с мин временем уже есть.
Если кого и ждать, в этом случае, то первого (у остальных можно по секунде будет убрать). При других входных данных надо подумать, скорее всего смотреть, что даст минимальное время ожидания, затем следующее и т.д. в конце концов выбрать то время ожидания, которое выдаст необходимое кол-во пассажиров. Если есть одинаковое время, начинать с дальней.
0 1 0 0 0 0 1
Это пятерка пассажиров (красные), одного из них ждали 1 сек. + 3 сек. в дороге = 4 сек.

Відредаговано: dpi - Ср, 11.02.2009, 19:41