← 返回题目列表

Codeforces · 1690/A

A. 打印基座(Codeforces 徽标?)

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

给定整数 $$$n$$$ — 可用块的数量。您必须使用所有块来建造基座。

底座由 $$$3$$$ 平台组成,分别用于 $$$2$$$-nd、$$$1$$$-st 和 $$$3$$$-rd 个位置。 $$$1$$$-nd 地点的平台必须严格高于 $$$2$$$-nd 地点的平台,并且 $$$2$$$-nd 地点的平台必须严格高于 $$$3$$$-rd 地点的平台。此外,每个平台的高度必须大于零(即每个平台必须至少包含一个块)。

$$$n=11$$$ 块的基座示例:第二位高度等于 $$$4$$$ 块,第一位高度等于 $$$5$$$ 块,第三位高度等于 $$$2$$$ 块。

在 $$$n$$$ 块的所有可能基座中,推导一个使得第 $$$1$$$-st 位置的平台高度尽可能最小。如果有多个,则输出其中一个。

输入

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

每个测试用例包含一个整数 $$$n$$$ ($$$6 \le n \le 10^5$$$) — 基座的块总数。必须使用所有 $$$n$$$ 块。

保证所有测试用例的 $$$n$$$ 值的总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出 $$$3$$$ 数字 $$$h_2、h_1、h_3$$$ — $$$2$$$-nd、$$$1$$$-st 和 $$$3$$$-rd 的平台高度位于由 $$$n$$$ 块组成的基座上 ($$$h_1+h_2+h_3=n$$$, $$$0 < h_3 < h_2 < h_1$$$)。

在所有可能的基座中,输出 $$$h_1$$$ 的值最小的一个。如果有多个,则输出其中一个。

示例

输入 #1

6
11
6
10
100000
7
8

输出 #1

4 5 2
2 3 1
4 5 1
33334 33335 33331
2 4 1
3 4 1

注意

在第一个测试用例中,我们无法得到第一个位置的平台高度小于$$$5$$$,因为如果第一个位置的平台高度不超过$$$4$$$,那么我们最多可以使用$$$4 + 3 + 2 = 9$$$块。我们应该使用 $$$11 = 4 + 5 + 2$$$ 块。因此,答案 4 5 2 合适。

在第二组中,唯一合适的答案是:2 3 1。