Polish version    English version  
  Historia OI -> II OI 1994/1995


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
Wyniki III etapu
Wyniki I etapu
Zadania
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
II Olimpiada Informatyczna 1994/95

Zadanie: SZE
Autor: Marcin Jurdziński
Szeregowanie czynności

Zawody III stopnia  
Plik źródłowy: SZE.??? (np. pas, c, cpp)
Plik wykonywalny: SZE.exe
Plik wejściowy: SZE.in
Plik wyjściowy: SZE.out

 

Danych jest n niezależnych i niepodzielnych czynności, ponumerowanych od 1 do n. 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 i wynosi hi(t) = ait + bi, jeśli rozpoczniemy ją w chwili t. Zakładamy, że 0 <= ai <= 1, 0 <= bi <= 1.

Należy uszeregować czynności w takiej kolejności, aby łączny czas ich wykonania był najmniejszy.

Zadanie

Napisz program, który:
  • wczytuje z pliku tekstowego SZE.IN liczbę czynności n nie większą niż 10000 oraz kolejno dla każdej czynności i - współczynniki ai oraz bi 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 w pliku tekstowym SZE.OUT numery czynności w takiej kolejności, w jakiej należy je wykonywać.

Wejście

  • W pierwszym wierszu pliku SZE.IN jest zapisana jedna liczba całkowita dodatnia nie większa niż 10000. Jest to liczba czynności n.
  • W każdym z n 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 ai oraz bi określających zależność czasu wykonania odpowiedniej i-tej czynności od chwili jej rozpoczęcia.

Wyjście

W pliku SZE.OUT należy zapisać uszeregowanie czynności, to znaczy odpowiednią permutację liczb 1, ..., n; każdą liczbę w osobnym wierszu.

Przykład

Dla pliku SZE.IN
5
0.002000 0.003000
0.016000 0.001000
0.100000 0.300000
0.016000 0.005000
0.030000 0.060000

w pliku SZE.OUT należy zapisać:
2
4
1
5
3

Twój program powinien szukać pliku SZE.IN w katalogu bieżącym i tworzyć plik SZE.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę SZE.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonywalnej powinien być zapisany w pliku SZE.EXE.




Wersja do druku