← 返回题目列表

Codeforces · 1934/B

B. 又一个硬币问题

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

您有 $$$5$$$ 不同类型的硬币,每种硬币的价值等于前 $$$5$$$ 三角形数字之一:$$$1$$$、$$$3$$$、$$$6$$$、$$$10$$$ 和 $$$15$$$。这些硬币类型非常丰富。您的目标是找到所需的最少数量的硬币,使其总价值恰好为 $$$n$$$。

我们可以证明答案总是存在的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^9$$$) — 目标值。

输出

对于每个测试用例,输出一个数字 - 所需的最小硬币数量。

示例

输入 #1

14
1
2
3
5
7
11
12
14
16
17
18
20
98
402931328

输出 #1

1
2
1
3
2
2
2
3
2
3
2
2
8
26862090

注意

在第一个测试用例中,对于 $$$n = 1$$$,答案是 $$$1$$$,因为只有一枚 $$$1$$$ 价值的硬币就足够了。 $$$1 = 1 \cdot 1$$$。

在第四个测试用例中,对于$$$n = 5$$$,答案是$$$3$$$,这可以使用两个$$$1$$$价值硬币和一个$$$3$$$价值硬币来实现。 $$$5 = 2 \cdot 1 + 1 \cdot 3$$$。

在第七个测试用例中,对于$$$n = 12$$$,答案是$$$2$$$,这可以使用两个$$$6$$$价值的硬币来实现。

在第九个测试用例中,对于$$$n = 16$$$,答案是$$$2$$$,这可以使用一枚$$$1$$$价值硬币和一枚$$$15$$$价值硬币或使用一枚$$$10$$$价值硬币和一枚$$$6$$$价值硬币来实现。 $$$16 = 1 \cdot 1 + 1 \cdot 15 = 1 \cdot 6 + 1 \cdot 10$$$。