[AdditionalFile4812.zip](file://AdditionalFile4812.zip?type=additional_file)

#4812. 「USACO 2025.2 Platinum」Transforming Pairs

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目来自 USACO 2025 February Contest, Platinum Problem 2. Transforming Pairs

回答 $Q$（$1\le Q\le 10^5$）个独立查询，每个查询的形式如下：

给定四个整数 $a$，$b$，$c$，$d$（$-10^{18}\le a,b,c,d\le 10^{18}$）。在一次操作中，你可以执行 $a\mathrel{+}=b$，或 $b\mathrel{+}=a$。求将 $(a,b)$ 转变为 $(c,d)$ 所需要的最小操作次数，或者如果不可能完成，输出 $-1$。

输入格式

输入的第一行包含 $Q$。

以下 $Q$ 行，每行包含四个整数 $a$，$b$，$c$，$d$。

输出格式

每行输出一个查询的答案。

样例

输入

4
5 -3 -1 -3
5 3 5 2
5 3 8 19
5 3 5 3

输出

2
-1
3
0

第一个查询：$(5,-3)\to (2,-3)\to (-1,-3)$。

第二个查询：不可能。

第三个查询：$(5,3) \to (8, 3) \to (8, 11) \to (8, 19)$。

第四个查询：不需要任何操作。

测试点性质

• 测试点 $2$：$|a|, |b|, |c|,|d|\le 10$。
• 测试点 $3$：$a,b\ge 0$。
• 测试点 $4$：$a \geq 0 \geq b$。
• 测试点 $5$：$a \leq 0 \leq b$。
• 测试点 $6$：$a,b\le 0$。
• 测试点 $7$：$c,d\ge 0$。
• 测试点 $8$：$c \geq 0 \geq d$。
• 测试点 $9$：$c \leq 0 \leq d$。
• 测试点 $10$：$c,d\le 0$。
• 测试点 $11\sim 14$：$Q \leq 10^3$。
• 测试点 $15\sim 19$：没有额外限制。

供题：Benjamin Qi