Szeregowanie czynności
Limit pamięci: 32 MB
Danych jest niezależnych i niepodzielnych czynności, ponumerowanych
od
do
. Należy je wykonać sekwencyjnie w dowolnej
kolejności. Wykonanie każdej czynności trwa tym dłużej im później ją
rozpoczniemy - ściśle czas wykonania czynności
wynosi
, jeśli rozpoczniemy ją w chwili
.
Zakładamy, że
,
.
Należy uszeregować czynności w takiej kolejności, aby łączny czas ich wykonania był najmniejszy.
Zadanie
Napisz program, który:
- wczytuje ze standardowego wejścia liczbę czynności
nie większą niż
oraz kolejno dla każdej czynności
- współczynniki
oraz
określające zależność czasu wykonania tej czynności od chwili jej rozpoczęcia,
- znajduje takie uszeregowanie czynności, żeby łączny czas ich wykonania był minimalny i zapisuje na standardowym wyjściu numery czynności w takiej kolejności, w jakiej należy je wykonywać.
Wejście
- W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba
całkowita dodatnia nie większa niż
. Jest to liczba czynności
.
- W każdym z
kolejnych wierszy jest zapisana para liczb rzeczywistych nieujemnych w standardowej notacji z kropką i sześcioma cyframi po kropce. Są one oddzielone pojedynczym odstępem. Jest to para współczynników
oraz tex>b_i określających zależność czasu wykonania odpowiedniej
-tej czynności od chwili jej rozpoczęcia.
Wyjście
Na standardowym wyjściu należy zapisać uszeregowanie czynności, to znaczy
odpowiednią permutację liczb ; każdą liczbę w osobnym
wierszu.
Przykład
Dla danych wejściowych:
5 0.002000 0.003000 0.016000 0.001000 0.100000 0.300000 0.016000 0.005000 0.030000 0.060000
poprawną odpowiedzią jest:
2 4 1 5 3
Autor zadania: Marcin Jurdziński.