#B3689. [语言月赛202212] 宇宙密码

    ID: 238 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2022O2优化分支结构循环结构语言月赛

[语言月赛202212] 宇宙密码

题目描述

经历十九年的探索,人们终于找到了宇宙中的那份瑰宝。

这份瑰宝被装在一个密码箱里,按照情报,密码应为一串长度为 nn 的数字 aa

人们满怀希望地输入了密码,但是密码箱没有任何反应。

这时人们意识到,在十九年中,由于宇宙射线的侵蚀,密码箱的密码发生了改变。

现在人们知道,能够打开密码箱的新密码是由原密码 aa 变化而来。具体的,新密码相比原密码变化了 tt 位数字,其中 tt 满足 0tk0 \leq t \leq k,且对于变化的数字位,变化后的数字是在该位置原数字的基础上增加或减小 11 得到的数字。特别的,如果原数字是 00,在原数字基础上减少 11 得到的数字是 99;如果原数字是 99,在原数字基础上增加 11 得到的数字是 00

现在人们知道了 n,a,kn, a, k,想知道经过宇宙射线侵蚀后,所有可能打开密码箱的密码。

人类将重任交到了你身上,请你帮助人类解决这个问题。你需要由小到大输出所有可能的密码,每个一行。

特别的,有一些密码可能存在前导 00。为了方便操作,这时你不必也不应将这些前导 00 一并输出。

人类感谢你。

输入格式

输入只有一行三个整数,依次代表原密码位数 nn,去掉前导零后的原密码 aa,和变化位数的最大值 kk

输出格式

输出若干行,每一行包含一个整数,代表由小到大的所有可能的密码。

3 14 1
4
13
14
15
24
114
914

提示

样例 1 解释

原密码为 014014,允许至多 11 位有变化。

所有密码情况如下:

变化位数和位置 可能的结果
00 014014
11 位,从左向右第 11 114,914114, 914
11 位,从左向右第 22 024,004024, 004
11 位,从左向右第 33 013,015013, 015

77 个可能的密码,按从小到大排序输出即可。

数据规模与约定

  • 对于前 10%10\% 的数据,保证 n=k=1n = k = 1
  • 对于前 40%40\% 的数据,保证 k1k \leq 1
  • 对于另外 10%10\% 的数据,保证 k=nk = n
  • 对于 100%100\% 的数据,保证 1n61 \leq n \leq 60a<10n0 \leq a < 10 ^ n0kn0 \leq k \leq n,保证输入数据无前导 00

请注意,输出数据中不应存在前导 00