分数: 600 点
问题陈述
给定的是一个正整数 N。考虑一个整数序列 A = (A_1, \ldots, A_K) 满足以下条件:
- \sum_{i=1}^K A_i = N;
- 每个 A_i 是一个正整数,其十进制表示法中的每个数字都是 1, 2,或 3.
找到以下的最小可能值 K,即该序列中的元素数量 A.
流程 T 每个输入文件的测试用例。
约束
- 1\leq T\leq 1000
- 1\leq N\leq 10^{18}
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个案例的格式如下:
N
输出
打印答案。
示例输入 1
5 456 10000 123 314 91
示例输出 1
2 4 1 2 4
对于每个 N,一个最佳 A 如下所示。
- 对于 N = 456: A = (133, 323).
- 对于 N = 10000: A = (323, 3132, 3232, 3313).
- 对于 N = 123: A = (123).
- 对于 N = 314: A = (312,2).
- 对于 N = 91: A = (22,23,23,23).