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.