P13328 [GCJ 2012 #3] Perfect Game

你正在玩一款电子游戏，如果能够连续通关所有关卡且中途没有死亡，你将获得一个成就。你可以以任意顺序游玩各个关卡，每次游玩某一关时，你要么通关，要么死亡。每一关都有一定的通关概率，并且每一关都需要一定的时间。不论你通关还是死亡，所用时间都相同。你应该以怎样的顺序游玩关卡，才能使获得成就所需的期望时间最小？假设每当你死亡后，会立刻从你设定的顺序的第一关重新开始。 **注意**：如果你未能通关某一关，你本人并不会真的死亡——只是游戏角色死亡而已。如果不是这样，恐怕只有极少数人会尝试获得这个成就。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据，每组测试数据包含三行。第一行为一个整数 $N$，表示关卡数量。第二行为 $N$ 个以空格分隔的整数 $L_i$，表示第 $i$ 关所需的秒数，无论通关还是死亡用时相同。第三行为 $N$ 个以空格分隔的整数 $P_i$，表示你每次尝试第 $i$ 关时死亡的概率（百分数）。

对于每个测试用例，输出一行 "Case #$x$: "，其中 $x$ 是测试用例编号（从 1 开始），后接 $N$ 个以空格分隔的整数。第 $j$ 个整数表示你应该第 $j$ 个挑战的关卡编号，以最小化获得成就所需的期望时间。 编号从 $0$ 到 $N-1$。若有多种顺序能获得相同的期望时间，请输出字典序最小的那一个。对于两个顺序，字典序较小的是在第一个不同位置上编号较小的那个；对于多个顺序，字典序最小的是在所有顺序中字典序最小的那个。

**样例说明** 请注意，第二组和第三组样例并不满足小数据的约束条件。 **限制条件** $1 \leq T \leq 100$。 $0 \leq P_i < 100$。 **测试集 1（3 分，结果可见）** - $1 \leq N \leq 20$。 - $L_i = 1$。 **测试集 2（7 分，结果隐藏）** - $1 \leq N \leq 1000$。 - $1 \leq L_i \leq 100$。 翻译由 ChatGPT-4.1 完成。