← 返回题目列表

Codeforces · 1551/A

A. 坡旅甲和硬币

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

Polycarp 必须在结账时准确支付 $$$n$$$ burles。他有两种面值的硬币:$$$1$$$ burle 和 $$$2$$$ burle。波利卡普同样喜欢这两种硬币。因此,他不想用一种类型的硬币比另一种类型的硬币多。

因此,Polycarp 希望最小化所使用的 $$$1$$$ burles 和 $$$2$$$ burles 硬币数量之间的差异。帮助他确定两个非负整数值 $$$c_1$$$ 和 $$$c_2$$$,分别是 $$$1$$$ burle 和 $$$2$$$ burles 的硬币数量,使得该数量的硬币的总价值恰好是 $$$n$$$(即 $$$c_1 + 2 \cdot c_2 = n$$$),以及两者之间差值的绝对值$$$c_1$$$ 和 $$$c_2$$$ 尽可能小(即您必须最小化 $$$|c_1-c_2|$$$)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例由一行组成。这一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^9$$$) — 波利卡普要支付的 burles 数量。

输出

对于每个测试用例,输出一个单独的行,其中包含两个整数 $$$c_1$$$ 和 $$$c_2$$$ ($$$c_1, c_2 \ge 0$$$),中间用空格分隔,其中 $$$c_1$$$ 是 $$$1$$$ burle 的硬币数量,$$$c_2$$$ 是 $$$2$$$ 的硬币数量布尔斯。如果有多个最优解,则打印任意一个。

示例

输入 #1

6
1000
30
1
32
1000000000
5

输出 #1

334 333
10 10
1 0
10 11
333333334 333333333
1 2

注意

第一个测试用例的答案是“334 333”。所有硬币的面值总和为 $$$334 \cdot 1 + 333 \cdot 2 = 1000$$$,而 $$$|334 - 333| = 1$$$。无法获得更好的值,因为如果 $$$|c_1 - c_2| = 0$$$,则 $$$c_1 = c_2$$$ 且 $$$c_1 \cdot 1 + c_1 \cdot 2 = 1000$$$,但 $$$c_1$$$ 的值不是整数。

第二个测试用例的答案是“10 10”。名义值之和为 $$$10 \cdot 1 + 10 \cdot 2 = 30$$$ 和 $$$|10 - 10| = 0$$$,而没有数字的绝对值小于$$$0$$$。