← 返回题目列表

Codeforces · 1836/B

B. 天体物理学家

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

在很多很多年之后,在很远很远的地方,将会发射第一次飞往火星的航班。为了庆祝成功,参与该项目的 $$$n$$$ 天体物理学家将获得总价值 $$$k$$$ 金币的奖金。

你必须将钱分配给天体物理学家,为了更容易,你必须以银币分配奖金。每枚金币价值 $$$g$$$ 银币,因此您必须将所有 $$$k \cdot g$$$ 银币分发给 $$$n$$$ 人。

不幸的是,该公司目前遇到一些财务问题。因此,他们决定不支付奖金上写的银币数量,而是将这个金额四舍五入到最接近的金币整数。

舍入过程如下。如果天体物理学家的奖金等于 $$$x$$$ 银币,并且我们表示 $$$r = x \bmod g$$$,那么:

- 如果$$$r \geq \lceil \frac{g}{2} \rceil$$$,天体物理学家收到$$$x + (g - r)$$$银币;
- 否则,天体物理学家将收到 $$$x - r$$$ 银币。

你的目标是分配奖金,以便公司因四舍五入而节省尽可能多的银币。请注意,总有一种分配方式是公司花费不超过 $$$k \cdot g$$$ 银币。

输入

在输入的第一行中,有一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) 表示测试用例的数量。

以下 $$$t$$$ 行描述一个测试用例,并包含三个整数 $$$n$$$、$$$k$$$、$$$g$$$ ($$$1 \le n \le 10^9$$$、$$$0 \le k \le 10^9$$$、$$$2 \le g \le 10^9$$$) — 分别是公司的天体物理学家,分配的金币总数以及1枚金币对应的银币数量。

输出

在每个测试用例的单独行中,输出一个整数——由于舍入而可以节省的最大银币数量。

示例

输入 #1

5
3 3 100
2 1 14
91 2 13
36 16 6
73 8 22

输出 #1

100
0
26
72
176

注意

在第一个测试用例中,最佳分配之一可能如下:

- 第一人称:$$$x = 30$$$银币:公司支付$$$0$$$,节省$$$30$$$银币,
- 第二人:$$$x = 140$$$银币:公司支付$$$100$$$,节省$$$40$$$银币,
- 第三人称:$$$x = 130$$$银币:公司支付$$$100$$$,节省$$$30$$$银币。

在第二个测试用例中,我们可以进行以下分配:

- 第一人称:$$$x = 8$$$银币:公司支付$$$14$$$,额外花费$$$6$$$银币,
- 第二人:$$$x = 6$$$银币:公司支付$$$0$$$,节省$$$6$$$银币。

如果两位天体物理学家的奖金分配为 $$$7$$$ 银币,那么公司将必须支付额外的金币来支付奖金。