구두 수선공

• Exchange argument 를 통해 그리디한 풀이를 도출해낼수 있다.
• 현재 시간이 t0일때,
  • i번⇒j번 순서로 고르고 나면 시간은 t0+Ti+Tj 이고, 벌금은 t0*Si +(t0+Ti)*Sj
  • j번⇒i번 순서로 고르고 나면 시간은 t0+Ti+Tj 이고, 벌금은 t0*Sj +(t0+Tj)*Si
• t0*Si +(t0+Ti)*Sj < t0*Sj +(t0+Tj)*Si 이라면 i번⇒j번 순서대로 골라야 한다.
• 식을 정리하면 T_i/S_i < T_j/S_j 이므로, (T_i/S_i) 기준으로 정렬하면 된다.
• 시간복잡도는 정렬에 드는 O(nlogn)에 바운드된다.
• 소방서의 고민도 처음 식은 좀 달라보이지만, 결국 같은 식으로 정리되는 문제이다

"""Solution code for "BOJ 14908. 구두 수선공".

- Problem link: https://www.acmicpc.net/problem/14908
- Solution link: http://www.teferi.net/ps/problems/boj/14908

Tags: [greedy]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    T_and_S = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    answer = sorted(range(N), key=lambda x: T_and_S[x][0] / T_and_S[x][1])

    print(*(x + 1 for x in answer))


if __name__ == '__main__':
    main()