#6578. 黄金和 (Golden Sum / Златна сума)

黄金和 (Golden Sum / Златна сума)

题目名称:黄金和 (Golden Sum / Златна сума)

版权信息:2021年马其顿编程竞赛 - 社区与地区赛 (Macedonian Programming Contests 2021 - Community and Regional Competition)

题目描述

基雷(Kire)是个酷家伙,他为自己的汽车换了一个很漂亮的车牌:KT 7777 AB。这类包含重复数字的车牌被称为“黄金车牌”,通常价格不菲。

在本题中,我们定义:

  1. 黄金数:指仅由同一种数字组成的自然数(例如:22, 333, 7, 55555...)。
  2. 黄金和:指一个或多个黄金数的总和。

艾米利亚(Emilija)的车牌号里没有黄金数,但她想向基雷证明,她的车牌号可以表示为一个“黄金和”(毕竟任何数字都可以拆分成若干个数字的和)。

你的任务是:给定一个正整数 NN,将其表示为一个黄金和,并确保该黄金和中包含的加数个数最少


输入格式

输入只有一行,包含一个正整数 NN (1N<100,000,000,0001 \le N < 100,000,000,000)。

评分说明:

  • 对于 20% 的测试用例:N200,000N \le 200,000
  • 对于 50% 的测试用例:N100,000,000N \le 100,000,000
  • 对于 100% 的测试用例:NN 最高可达 101110^{11}

输出格式

  • 第一行:输出一个整数 KK,代表最少的加数个数。
  • 第二行:输出这 KK 个黄金数,用空格隔开(顺序不限)。

限制条件

  • 时间限制:100 毫秒
  • 内存限制:64 MB

样例数据

输入 (NN) 输出 解释
338 2
5 333
338 = 333 + 5
11124 3
2 11 11111
11124 = 11111 + 11 + 2
22222222222 1
22222222222
本身就是黄金数