/ 
実行時間制限: 5 sec / メモリ制限: 1024 MiB
配点 : 425 点
問題文
整数 N と M が与えられます。
以下の条件をすべて満たす長さ N の整数列 (A_1, A_2, \ldots, A_N) を辞書順にすべて出力してください。
- 1 \leq A_i
- 2 以上 N 以下の各整数 i に対して A_{i - 1} + 10 \leq A_i
- A_N \leq M
数列の辞書順とは
長さ N の数列 S = (S_1, S_2, \ldots, S_N) が長さ N の数列 T = (T_1, T_2, \ldots, T_N) より辞書順で小さいとは、ある整数 1 \leq i \leq N が存在して下記の 2 つがともに成り立つことをいいます。
- (S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1})
- S_i が T_i より（数として）小さい。
制約
- 2 \leq N \leq 12
- 10N - 9 \leq M \leq 10N
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
条件を満たす長さ N の整数列の個数を X として X + 1 行出力せよ。
1 行目には X の値を出力せよ。
i + 1 (1 \leq i \leq X) 行目には条件を満たす整数列のうち辞書順で i 番目に小さいものを空白区切りで出力せよ。
入力例 1
3 23
出力例 1
10 1 11 21 1 11 22 1 11 23 1 12 22 1 12 23 1 13 23 2 12 22 2 12 23 2 13 23 3 13 23
(1, 11, 21), (1, 11, 22), (1, 11, 23), (1, 12, 22), (1, 12, 23), (1, 13, 23), (2, 12, 22), (2, 12, 23), (2, 13, 23), (3, 13, 23) の 10 個の数列が条件を満たします。
Score: 425 points
Problem Statement
You are given integers N and M.
Print all integer sequences (A_1, A_2, \ldots, A_N) of length N that satisfy all of the following conditions, in lexicographical order.
- 1 \leq A_i
- A_{i - 1} + 10 \leq A_i for each integer i from 2 through N
- A_N \leq M
What is lexicographical order?
A sequence S = (S_1, S_2, \ldots, S_N) of length N is smaller in lexicographical order than a sequence T = (T_1, T_2, \ldots, T_N) of length N if and only if there exists an integer 1 \leq i \leq N such that both of the following hold:
- (S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1})
- S_i is less than T_i (as a number).
Constraints
- 2 \leq N \leq 12
- 10N - 9 \leq M \leq 10N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Let X be the number of integer sequences that satisfy the conditions, and print X + 1 lines.
The first line should contain the value of X.
The (i + 1)-th line (1 \leq i \leq X) should contain the i-th smallest integer sequence in lexicographical order, with elements separated by spaces.
Sample Input 1
3 23
Sample Output 1
10 1 11 21 1 11 22 1 11 23 1 12 22 1 12 23 1 13 23 2 12 22 2 12 23 2 13 23 3 13 23
(1, 11, 21), (1, 11, 22), (1, 11, 23), (1, 12, 22), (1, 12, 23), (1, 13, 23), (2, 12, 22), (2, 12, 23), (2, 13, 23), (3, 13, 23) are the 10 sequences that satisfy the conditions.