Polish version    English version  
  About Olympic -> Problems -> II OI 1994/1995


 News
 About Olympic
About contest
Problems
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Problems archive
 History of OI
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
II Olympiad in Informatics 1994/1995

Task: SZE
Author: Marcin Jurdziński
Job Scheduling

III stage contest  

We are given n independent and indivisible jobs numbered from 1 to n. They should be executed sequentially in any order. The later the execution of a job starts the longer it lasts - precisely, the time of execution of the job i is hi(t)=ait+bi, if we start it in the moment t. We assume that 0<=ai<=1, 0<=bi<=1.

The goal is to schedule the jobs so that the total execution time is the shortest.

Task

Write a program that:
  • reads from the text file SZE.IN the number of jobs n not greater than 10000 and successively - for each job i - the coefficients ai and bi determining the dependence of the job execution time upon the time it starts,
  • finds such a scheduling of the jobs that the cumulative execution time is minimal; then the program writes to the file SZE.OUT the numbers of the jobs in the order they should be executed.

Input

  • In the first line of the file SZE.IN there is one positive integer not greater then 1000. It is the number of jobs n.
  • In each of the following n lines there is a pair of nonnegative real numbers. The numbers are written in a standard form with a decimal point and six digits after the point. The numbers are separated by a single space. It is the pair of coefficients ai and bi determining the dependence of the execution time of the corresponding i-th job upon the time it starts.

Output

One should write in the file SZE.OUT the scheduling of the jobs, i.e. an appropriate permutation of numbers 1,...,n; one number per line.

Example

For the file SZE.IN:
5
0.002000 0.003000
0.016000 0.001000
0.100000 0.300000
0.016000 0.005000
0.030000 0.060000
in the file SZE.OUT one should write:
2
4
1
5
3
Your program should look for the file SZE.IN in the current directory and create the file SZE.OUT also in the current directory. The source file containing the program written by you should be named SZE.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be written in a file SZE.EXE.



Print friendly version