← 返回题目列表

AtCoder · code_festival_china_a

A. 锁

中文机器翻译题面 查看原题

问题

爱丽丝有一个锁着的盒子 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