构建一个程序，为给定的电阻创建一个最小的一欧姆电阻图。

Question

你是一家公司的承包商，为他们生产的各种产品设计电路。有一天，公司意外地收到了大量的一欧姆电阻和绝对没有其他东西，并给你的任务是让他们在他们正在生产的最新产品中得到良好的使用。

您的任务是构建一个以正有理数作为输入的程序，形式如下：

a / b

并返回一个电阻图与精确给定的电阻，使用尽可能少的一个欧姆电阻。

您的电阻图将包括：

• 这个数字N，表示有多少SPTs有。(我将在下面描述一个SPT。)
• N线，每条线包含两个数字A和B，表示电路板上有编号的电极，后面跟着一个SPT。
• 一行包含两个数字，P和Q表示哪两个电极测量之间的电阻。

SPT是一种“串联并行树”，是一种以树格式描述串联并行电路的方法。

有效的SPT是：

• 数字1，表示单个电阻器。
• S( )，包含一个数字，后面跟着零或多个P( ) SPTs。
• P( )，包含一个数字，后面跟着零或多个S( ) SPTs。

有效SPTS的例子：

1 <- has a resistance of 1
S(1) <- equivalent to 1 and P(1)
S(2, P(3)) <- has a resistance of 7/3, using 5 resistors
P(1, S(2), S(3), S(4, P(2))) <- has a resistance of 18/37, using 12 resistors

无效的SPTS示例：

2 <- the two resistors are in an unknown configuration. Use P(2) or S(2) instead.
P(2, P(1)) <- use P(3) instead.
P(4, P(1, S(3), S(2))) <- use P(5, S(3), S(2)) instead.

Specifications

您的程序必须为任何分子和分母工作，直到150 000。

您的程序的源代码，不包括任何导入的标准或第三方库，总容量不得超过1 or (1,048,576字节)。

您的程序将被测试在一个特定的，随机选择的一组10,000分数(待稍后日期确定)，并得分的电阻，它需要建立所有10,000个电路。使用最少电阻的程序是赢家。

测试数据

输入

3 / 8

可能会回来

1
1 2 S(0, P(8), P(4))
1 2

表示一系列的8个电阻器，然后4个电阻器并联。这可能不是最优的解决方案；但就这个问题而言，它是有效的输出。

输入

5 / 6

可能还会：

12
1 2 1
1 3 1
1 5 1
2 4 1
2 6 1
3 4 1
3 7 1
4 8 1
5 6 1
5 7 1
6 8 1
7 8 1
1 8

表示一个由一个欧姆电阻组成的立方体，其顶点通过1通过8，其电阻测量在相对的拐角之间。当然，只使用五个电阻就可以完成S(P(2), P(3))，但这是一个例子，说明了如何使用符号来表示非串联并行图。

Answer 1

Python

作为最后一种参考解决方案，这里有一个天真的解决方案，它总是有效的：

frac = raw_input().split(" / ")
num = int(frac[0])
den = int(frac[1])
print 1
print 1, 2,

pstr = ""
for x in range(den):
    pstr += "S(%s), " % num
pstr = pstr[:-2]

print "P(%s)" % pstr

print 1, 2

每次使用n电阻，总是为电阻m/n创建m电阻系列的mn并行。