Сб, 18.11.2017, 13:54
Форум інформатиків України
Головна Реєстрація Вхід
Вітаю Вас, Гість · RSS
Вітання на форумі
Незнайомець
Вітаємо на форумі,
Незнайомцю!

   
зареєструйтесь
Перед реєстрацією обов’язково прочитайте:
Оновлення Учасники Пошук
Особисті повідомлення
Видавництво ’’Аспект’’ Видавництво

Сторінка 1 з 11
Модератор форуму: Bandalak, Ktara, НІКОЛЯ, volevikt 
Форум інформатиків » РОЗДІЛ VIІІ: ОБМІН ДОСВІДОМ (УРОКИ, ФАКУЛЬТАТИВИ, ПОЗАКЛАСНА РОБОТА) » 8.6 Факультатив з програмування » Олімпіадні задачі (Автобус)
Олімпіадні задачі
hottabych Дата: Нд, 08.02.2009, 17: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, 21:44 | Повідомлення № 2
Новий користувач
Повідомлень: 3
Нагороди: 0
Рейтинг: 0
Це районна олімпіада розвязку немає.

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

hottabych Дата: Вт, 10.02.2009, 19:23 | Повідомлення № 3
Новий користувач
Повідомлень: 3
Нагороди: 0
Рейтинг: 0
CN, де її розвязок???
dpi Дата: Ср, 11.02.2009, 13:56 | Повідомлення № 4
Досвідчений вчитель
Повідомлень: 1438
Нагороди: 1
Рейтинг: 39
Quote (CN)
дают такие задачи на олимпиаду

Имеете ввиду легкие или трудные?
dpi Дата: Ср, 11.02.2009, 18: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, 18:41
Форум інформатиків » РОЗДІЛ VIІІ: ОБМІН ДОСВІДОМ (УРОКИ, ФАКУЛЬТАТИВИ, ПОЗАКЛАСНА РОБОТА) » 8.6 Факультатив з програмування » Олімпіадні задачі (Автобус)
Сторінка 1 з 11
Пошук:


© Форум інформатиків України, 2007-2017.