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
The goal is to schedule the jobs so that the total execution time is
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.
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.
One should write in the file SZE.OUT the scheduling of the jobs,
i.e. an appropriate permutation of numbers 1,...,n; one number
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.