问题
爱丽丝有一个锁着的盒子 n 数字拨号锁定。锁的每个转盘都可以设置为以下数字: 0 to 9。 不幸的是,她忘记了密码( n 数字)。现在她将尝试所有可能的数字组合来解锁钥匙。
她每次都可以执行以下操作之一。
- 选择 1 拨打并添加 1 到该数字。 9,这将是 0).
- 选择 1 拨号和减法 1 从该数字开始。 0,这将是 9).
奇怪的是,即使她在试验期间找到了正确的密码,她也想尝试所有组合。但要尝试所有的方法是一件很困难的事 10^n 组合。 通过向她展示如何尽可能减少手术次数来帮助她。
最初,锁定的数字组合设置为 00..0.
计算 m,尝试所有数字组合的最少程序数,并显示 m+1 每个过程后的数字组合,包括初始组合 00..0。 如果有多个可能的答案,您可以选择其中之一。
检查当前数字组合是否与密码匹配不算一个过程。
输入
输入按以下格式给出。
n
- 在第一行,您将得到 n (1 \leq n \leq 5),拨号锁的位数。
输出
第一行,输出 m,尝试所有数字组合的最少程序数。
关于以下内容 m+1 行,按顺序输出试验过程中出现的数字组合。 如果有超过 1 可能的答案,您可以选择其中任何一个。 确保在最后一行的末尾插入换行符。
输入示例 1
1
输出示例 1
9 0 1 2 3 4 5 6 7 8 9
不要忘记输出最少的程序数 9 在第一行。
在下面的行中,请注意您必须输出 m+1 行包括初始组合 0.
输入示例 2
2
输出示例 2
99 00 01 02 03 04 05 06 07 08 09 19 18 17 16 15 14 13 12 11 10 20 21 22 23 24 25 26 27 28 29 39 38 37 36 35 34 33 32 31 30 40 41 42 43 44 45 46 47 48 49 59 58 57 56 55 54 53 52 51 50 60 61 62 63 64 65 66 67 68 69 79 78 77 76 75 74 73 72 71 70 80 81 82 83 84 85 86 87 88 89 99 98 97 96 95 94 93 92 91 90