P5429. 面试官无冲突组题

场次：2026年9月11日-非AI方向 · 来源：CodeFun2000 P5429

题目描述

出题官要编一套算法题。现有 $m$ 个知识点模块可供调用，模块各自带着互不重复的编号（取值 $1$ 到 $m$）以及一项难度系数。

调用这些模块拼成一道题时，须遵守下列约定：

1. 模块选择：在共计 $m$ 个模块里取出 $t$ 个，用来构成该题
2. 顺序排列：已取出的 $t$ 个模块须依编号从小到大排好
3. 冲突检测：紧挨着的两个模块禁止出现「知识冲突」。两模块编号相减后取绝对值，只要不大于 $g$，就判定为冲突
4. 难度约束：已取出的 $t$ 个模块，其难度系数加总后必须落在闭区间 $[lo, hi]$ 里

请枚举全部符合上述约定的组题方案。

输入格式

• 首行给出五个整数 $m, t, g, lo, hi$
  • $m$：模块一共有多少个（$1 \le m \le 20$）
  • $t$：取出几个模块（$1 \le t \le m$）
  • $g$：判定冲突用的阈值（$0 \le g \le m$）
  • $lo$：难度加总的下限（$1 \le lo \le 1000$）
  • $hi$：难度加总的上限（$lo \le hi \le 1000$）
• 次行给出 $m$ 个整数，即各模块的难度系数（$1 \le$ 难度系数 $\le 100$）

输出格式

• 首行打印符合约定的方案个数
• 个数一旦为正，再按字典序打印至多前 $3$ 份方案（一份占一行，模块编号之间以空格隔开）

示例

示例 1

输入：

6 3 1 8 16
4 2 5 3 6 1

输出：

3
1 3 5
1 3 6
1 4 6

说明：

• 编号依次为 $1$ 到 $6$，对应难度系数 $4,2,5,3,6,1$
• 取出 $3$ 个模块，紧邻编号差必须大于 $1$，难度加总落在 $[8,16]$
• 间隔够格的三元组里：
  • $(1,3,5)$：合法，加总 $4+5+6=15$
  • $(1,3,6)$：合法，加总 $4+5+1=10$
  • $(1,4,6)$：合法，加总 $4+3+1=8$
  • $(2,4,6)$：间隔够，但加总 $2+3+1=6$，低于下限
• 因而合法方案共 $3$ 份，按字典序即上面三行