|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex 'Agent' Smith 2:464/34.74 28 Jul 2001 22:07:12
To : All
Subject : Задача об исполнителе со взвешенными штрафами
--------------------------------------------------------------------------------
>< >< >< Wake up, All. Менты окружают! >< >< ><
Задача:
Дано N пассажиров в буфете, Di - время отправления поезда у i-того пассажира,
Wi - величина убытка, которую понесет пассажир, если не успеет на поезд. Касса
обслуживает посетителя за единичное время и в начальный момент время равно нулю.
Кто до сих пор еще не понял задания: надо расположить пассажиров в очередь,
минимизировав их убытки.
Я - ламер, конечно, но почитав про похожие задачи нашел, что оказывается сабж
(если, конечно, данная задача - сабж) решается только перебором. Вспомнил про
эту задачу и вот спрашиваю: а она-то как решается?
Отсортировать по времени "отплытия" - не катит (штраф-то взвешенный); как-то
кантовать пассажиров - че-то плохо себе представляю, как...
ЗЫ: Это было в 99'м в Днепре на олимпиаде. Там еще про сервер была задача. Я ее
условие прочел и недопонимаю. Hет, случись мне в реальной жизни хачить такую
дебильную защиту - за пять минут бы управился, а тут - сказано проверять
модулем, в котором пароль каждый раз случайным образом генерится :-/ Если кто
там был, расскажите, где тут правда.
Good bye, mister All _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... Отчего, отчего, отчего Winamp поет? Оттого, что кто-то любит программиста!
--- А у твоего ГолДеда стоит... фильтрация мессаг???
* Origin: Эти программисты только о hex'е и думают!
(2:464/34.74)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
