A11293 | Yet Another Coin Problem
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You have $5$ different types of coins, each with a value equal to one of the first $5$ triangular numbers: $1$ , $3$ , $6$ , $10$ , and $15$ . These coin types are available in abundance. Your goal is to find the minimum number of these coins required such that their total value sums up to exactly $n$ .
We can show that the answer always exists.
We can show that the answer always exists.
输入格式
The first line contains one integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer $n$ ( $1 \leq n \leq 10^9$ ) — the target value.
The first line of each test case contains an integer $n$ ( $1 \leq n \leq 10^9$ ) — the target value.
输出格式
For each test case, output a single number — the minimum number of coins required.
输入输出样例
输入 #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
In the first test case, for $n = 1$ , the answer is $1$ since only one $1$ value coin is sufficient. $1 = 1 \cdot 1$ .
In the fourth test case, for $n = 5$ , the answer is $3$ , which can be achieved using two $1$ value coins and one $3$ value coin. $5 = 2 \cdot 1 + 1 \cdot 3$ .
In the seventh test case, for $n = 12$ , the answer is $2$ , which can be achieved using two $6$ value coins.
In the ninth test case, for $n = 16$ , the answer is $2$ , which can be achieved using one $1$ value coin and one $15$ value coin or using one $10$ value coin and one $6$ value coin. $16 = 1 \cdot 1 + 1 \cdot 15 = 1 \cdot 6 + 1 \cdot 10$ .
In the fourth test case, for $n = 5$ , the answer is $3$ , which can be achieved using two $1$ value coins and one $3$ value coin. $5 = 2 \cdot 1 + 1 \cdot 3$ .
In the seventh test case, for $n = 12$ , the answer is $2$ , which can be achieved using two $6$ value coins.
In the ninth test case, for $n = 16$ , the answer is $2$ , which can be achieved using one $1$ value coin and one $15$ value coin or using one $10$ value coin and one $6$ value coin. $16 = 1 \cdot 1 + 1 \cdot 15 = 1 \cdot 6 + 1 \cdot 10$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted