← 返回题目列表

AtCoder · arc222_f

F. 三重转变

中文机器翻译题面 查看原题

分数: 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.