← 返回题目列表

AtCoder · abc382_d

G. 保持距离

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

分数: 425 点

问题陈述

给你整数 N 和 M.

打印所有整数序列 (A_1, A_2, \ldots, A_N) 长度 N 满足以下所有条件(按字典顺序排列)。

  • 1 \leq A_i
  • A_{i - 1} + 10 \leq A_i 对于每个整数 i 来自 2 通过 N
  • A_N \leq M
什么是字典顺序?

一个序列 S = (S_1, S_2, \ldots, S_N) 长度 N is 按字典顺序较小 比序列 T = (T_1, T_2, \ldots, T_N) 长度 N 当且仅当存在一个整数 1 \leq i \leq N 使得以下两者成立:

  • (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

输出

让 X 为满足条件的整数序列的个数,并打印 X + 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 满足条件的序列。