시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 3 3 75.000%

문제

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 standard input the number of jobs n not greater than 10,000 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 standard output the numbers of the jobs in the order they should be executed.

입력

  • In the first line of the standard input there is one positive integer not greater then 10,000. 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 standard output the scheduling of the jobs, i.e. an appropriate permutation of numbers 1, ..., n; one number per line.

예제 입력 1

5
0.002000 0.003000
0.016000 0.001000
0.100000 0.300000
0.016000 0.005000
0.030000 0.060000

예제 출력 1

2
4
1
5
3

출처

Olympiad > Polish Olympiad in Informatics > POI 1994/1995 > Stage 3 5번

  • 스페셜 저지를 만든 사람: koosaga