luogu#P6024. 机器人
机器人
题目背景
小 W 购买了一个机器人。
题目描述
现在,小 W 希望机器人去帮他完成 个任务。
每个任务有两种属性:完成需要花的钱 ,成功率 。
小 W 需要将任务按一定顺序排序,随后,机器人会按如下方式做任务:
- 从第一个任务开始做;
- 花费代价做完第 个任务后,如果成功,则继续做第 个任务,否则重新从第一个任务开始做;
- 成功做完第 个任务后,流程结束。
例如,当 时,一个可能的流程为:
- 做任务 ,失败;
- 做任务 ,成功;
- 做任务 ,失败;
- 做任务 ,成功;
- 做任务 ,成功;
- 流程结束,总花费为 。
现在,小 W 希望学 OI 的你帮他找到一种排列顺序,使得他的期望花费最小。
输入格式
第一行一个整数 ,表示任务的数量。
接下来一行 个整数 ,意义如上。
接下来一行 个整数 ,其中 , 的意义如上。
输出格式
如果无论如何也不可能完成任务,那么输出一行一个字符串Impossible
。
否则,输出一行 个整数 ,其为 的一个排列,表示任务的安排顺序,安排的第 件任务是输入中的第 件任务。
2
999 1
5000 10000
1 2
1
1
0
Impossible
提示
样例一解释:可以感性理解。既然任务 一定成功,那放到最后做肯定不劣。
样例二解释:显然这个任务不可能完成,它的成功率为 。
注意:无论任务是否成功,总是要花费 的代价去做。
本题带有 。如果你的输出与答案的输出一样优(或者都是Impossible
),那么你将在这个测试点获得满分,否则你将在这个测试点不获得任何分数。
由于某种原因,本题不提供 给选手。
数据范围:
对于 的数据,。
对于另外 的数据,所有 相等。
对于另外 的数据,所有 相等。
对于所有数据,,,。