← 返回题目列表

Codeforces · 1872/A

A. 两艘船

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

你有两个装有水的容器。第一个容器含有 $$$a$$$ 克水,第二个容器含有 $$$b$$$ 克水。这两艘船都非常大,可以容纳任意数量的水。

您还有一个空杯子,最多可容纳 $$$c$$$ 克水。

在一个动作中,您可以从任何容器中舀出最多 $$$c$$$ 克的水并将其倒入另一个容器中。请注意,一次倒入的水的质量不必是整数。

使容器中水的质量相等所需的最少移动次数是多少?请注意,您无法执行除所描述的移动之外的任何操作。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例由一行组成,其中包含三个整数 $$$a$$$、$$$b$$$ 和 $$$c$$$ ($$$1 \le a, b, c \le 100$$$)——分别是容器中水的质量和杯子的容量。

输出

对于每个测试用例,输出一个数字 - 使容器中的水质量相等所需的最小移动次数。可以证明,这总是可能的。

示例

输入 #1

6
3 7 2
17 4 3
17 17 1
17 21 100
1 100 1
97 4 3

输出 #1

1
3
0
1
50
16

注意

在第一个测试用例中,只需一次操作就足够了:如果我们将 $$$2$$$ 克水从第二个容器倒入第一个容器中,则两个容器将包含 $$$5$$$ 克水。

在第二个示例测试用例中,三步就足够了:

- 将第一个容器中的 $$$3$$$ 克水倒入第二个容器中。完成此移动后,第一个容器将包含 $$$17 - 3 = 14$$$ 克水,第二个容器将包含 $$$4 + 3 = 7$$$ 克水。
- 将第一个容器中的 $$$2$$$ 克水倒入第二个容器中。完成此移动后,第一个容器将包含 $$$14 - 2 = 12$$$ 克水,第二个容器将包含 $$$7 + 2 = 9$$$ 克水。
- 最后,将第一个容器中的 $$$1.5$$$ 克水倒入第二个容器中。完成此移动后,第一个容器将包含 $$$12 - 1.5 = 10.5$$$ 克水,第二个容器将包含 $$$9 + 1.5 = 10.5$$$ 克水。

请注意,这不是在 $$$3$$$ 移动中均衡船只的唯一方法,但在 $$$2$$$ 移动中无法做到这一点。

在第三个示例测试用例中,容器最初包含相同量的水,因此不需要移动。答案是$$$0$$$。