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.