你的朋友 Kirchhoff 对电子设计的现状感到震惊。
“天哪!瓦特这个领域有问题吗?所有这些电路效率低下!还有很大的改进空间。电气工程师一定不能很好地上课。这绝对令人反感”他说。
消极情绪不断从他身上流淌出来,但即使在抱怨了很多次之后,他仍然没有机会直接改变任何事情。
“这些电路的总电阻太大。他们这样设计的电线?这只会导致电阻器的大量损耗!如果他们最大限度地发挥设计的潜力,他们的整个领域可以节省这么多钱。为什么他们不能尝试其他想法呢?”
他对电气工程系的抗议频率让你的灵魂颤抖,所以你决定自己负责并帮助他们。您计划创建一个程序来优化电路,同时保持相同的电路布局和相同的有效电阻。
电路有两个端点,并与某个常数 $$$R$$$ 相关联,称为其有效电阻。
我们将考虑的电路将由串联或并联连接在一起的各个电阻器组成,从而形成更复杂的电路。下图说明了串联或并联的组合电路。
根据你的朋友 Kirchhoff 的说法,通过这种方式连接电路时可以很容易地计算有效电阻:
- 当 $$$k$$$ 电路与有效电阻 $$$R_1、R_2、\ldots、R_k$$$ 串联时,所得电路的有效电阻 $$$R$$$ 为 $$$$$$R = R_1 + R_2 + \ldots + R_k 之和。$$$$$$
- 当 $$$k$$$ 电路与有效电阻 $$$R_1、R_2、\ldots、R_k$$$ 并联时,通过求解 $$$$$$\frac{1}{R} = \frac{1}{R_1} + \frac{1}{R_2} + \ldots + 中的 $$$R$$$ 来找到所得电路的有效电阻 $$$R$$$ \frac{1}{R_k},$$$$$$ 假设所有 $$$R_i > 0$$$;如果至少有一个$$$R_i = 0$$$,那么整个电路的有效电阻就是$$$R = 0$$$。
电路将由字符串表示。各个电阻器用星号“*”表示。对于更复杂的电路,假设 $$$s_1, s_2, \ldots, s_k$$$ 代表 $$$k \ge 2$$$ 电路。然后:
- “($$$s_1$$$ S $$$s_2$$$ S $$$\ldots$$$ S $$$s_k$$$)”代表它们的串联电路;
- “($$$s_1$$$ P $$$s_2$$$ P $$$\ldots$$$ P $$$s_k$$$)”表示它们的并联电路。
例如,“(* P (* S *) P *)”代表以下电路:
给定一个电路,您的任务是分配各个电阻器的电阻,使其满足以下要求:
- 每个单独的电阻器都有一个非负整数电阻值;
- 整个电路的有效电阻为$$$r$$$;
- 各个电阻器的电阻之和最小化。
如果有 $$$n$$$ 个单独的电阻,那么您需要输出列表 $$$r_1, r_2, \ldots, r_n$$$ ($$$0 \le r_i$$$,$$$r_i$$$ 是一个整数),其中 $$$r_i$$$ 是分配给输入中出现的第 $$$i$$$ 个单独电阻的电阻(来自从左到右)。如果不可能完成任务,你也必须说出来。
如果可能,则保证阻力的最小总和至多为$$$10^{18}$$$。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 32000$$$),表示测试用例的数量。接下来的几行包含测试用例的描述。
每个测试用例由一行组成,其中包含整数 $$$r$$$ ($$$1 \le r \le 10^6$$$)、空格,然后是表示电路的字符串。保证字符串有效并且遵循上面的描述。单个电阻器(符号“*”)的数量至少为$$$1$$$,最多为$$$80000$$$。
保证所有测试用例中的单个电阻器总数最多为 $$$320000$$$。
输出
对于每个测试用例,打印一行:
- 如果可以实现 $$$r$$$ 的有效电阻,请打印“REVOLTING”(不带引号),然后打印 $$$n$$$ 整数 $$$r_1, r_2, \ldots, r_n$$$ — 分配给各个电阻器的电阻。这里,$$$n$$$ 表示电路中各个电阻的数量。 可能有多种可能的此类分配,其中各个电阻器的电阻之和最小,您可以输出其中任何一个;
- 如果不可能,则打印字符串:“LOSS”(不带引号)。
示例
输入 #1
3 5 * 1 (* S *) 1 (* P (* S *))
输出 #1
REVOLTING 5 REVOLTING 1 0 REVOLTING 2 1 1
注意
下面说明了第三个示例案例:
这里,各个电阻器的电阻之和为 $$$2 + 1 + 1 = 4$$$,可以显示为最小值。请注意,可能还有其他作业达到此最低要求。