← 返回题目列表

AtCoder · toyota2023spring_final_b

B. 最佳策略

中文机器翻译题面 查看原题

配点 : 300 点

問題文

1 减去 N 包含 N 道题目问题,你将参与使用这些题目的游戏。

在该游戏中,你要对题目 1 道进行回答。 你可以自由选择回答题目的顺序。 题目 i 的回答将以 P_i % 的概率正确。 如果回答正确,你将 S_i 获得点数后,(如果还有未回答的测验)将移至下一个测验的回答。 如果未答对,游戏将立即结束,无法回答剩余的测验。

你希望最大化获得分数总和的期望值。 请找出为实现这一目标的策略(即回答测验的顺序)。 各测验答对与否的概率相互之间都是独立的。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq S_i \leq 10^9
  • 0 \leq P_i \leq 100
  • 所有输入值均为整数

入力

输入是按以下格式从标准输入给出的。

N
S_1 P_1
S_2 P_2
\vdots
S_N P_N

出力

按以下格式输出您的答案。

x_1 x_2 \cdots x_N

这里 x_i 表示,如果最初的(i-1)题答对了, i 表示第几题测验将被回答的编号。 如果解答有多个,输出其中任意一个均视为正确。


入力例 1

2
1000 10
300 50

出力例 1

2 1

如果按照测验 1,2 的顺序回答,获得的分数总和的期望值将是 115 。 测验 2,1 的顺序回答,获得的分数总和的期望值将是 200 。 因此,按照测验 2,1 的顺序回答是最优策略。


入力例 2

6
1 0
1 20
1 40
1 60
1 80
1 100

出力例 2

6 5 4 3 2 1

入力例 3

9
88994950 78
405248480 35
561113280 28
22802150 2
946582650 25
201425280 52
669650 41
128877450 71
1396050 25

出力例 3

1 5 8 2 3 6 4 7 9