History of OI -> II OI 1994/1995 -> Problems

 News About Olympic History of 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 Stage III - results Stage I - results Problems I OI 1993/1994 OI books National team Olympic camps Photo gallery Links SIO MAIN
Niebieskie ksi.eczki

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.

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