分数: 700 点
问题陈述
考虑 操作 三重 (x,y,z) 非负整数。在操作中, (x,y,z) 按照以下规则替换:
- If y+z<x:替换为 (x-y-z,\ 2y,\ 2z).
- If x+z<y:替换为 (2x,\ y-x-z,\ 2z).
- If x+y<z:替换为 (2x,\ 2y,\ z-x-y).
- 如果上述条件都不成立:替换为 (y+z-x,\ x+z-y,\ x+y-z).
请注意,每个非负整数三元组恰好属于上述四种情况之一。
给你非负整数 A_1, A_2, A_3, B_1, B_2, B_3。考虑对三元组执行操作 (A_1,A_2,A_3) 零次或多次获取 (B_1,B_2,B_3)。找出执行此操作所需的最少操作数。如果无法获得 (B_1,B_2,B_3) 无论执行多少次操作,都会输出 -1.
T 给出了测试用例;解决它们中的每一个。
约束
- 1\leq T\leq 300
- 0\leq A_1, A_2, A_3, B_1, B_2, B_3\leq 10^8
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
A_1 A_2 A_3 B_1 B_2 B_3
输出
每个测试用例输出一行。
对于每个测试用例,输出获得所需的最少操作数 (B_1,B_2,B_3) 通过对三元组执行操作 (A_1,A_2,A_3) 零次或多次。如果无法获得 (B_1,B_2,B_3) 无论执行多少次操作,都会输出 -1.
示例输入 1
6 2 3 4 2 3 4 2 3 4 5 3 1 2 3 4 1 6 2 2 3 4 4 3 2 1 0 0 0 0 1 0 0 0 0 0 0
示例输出 1
0 1 2 -1 -1 0
对于 (A_1,A_2,A_3)=(2,3,4),重复应用该操作时,三元组变化如下:
- (2,3,4)\to (5,3,1)\to (1,6,2)\to (2,3,4)\to (5,3,1)\to (1,6,2)\to\cdots
由此可见,前三个测试用例的答案是 0, 1, 2.