#P3274. Circle

    ID: 2461 传统题 1000ms 512MiB 尝试: 127 已通过: 26 难度: 7 上传者: 标签>难度分类提高枚举与搜索暴力枚举动态规划有限候选集缩减对称性去重位运算位集求并枚举置位位置数据结构有序集合CF2200

Circle

Circle

题目描述

有 nn 个格子围成一圈。在每个格子中填入一个不小于 kk 的正整数。从任意格子开始,沿圆周选取连续的一段格子,将其中的数相加。可以只选一个格子,也可以选完整的一圈。每个格子在一次求和中最多使用一次。

设所得的连续段和能够取到 m,m+1,…,im,m+1,\ldots,i,但取不到 i+1i+1。求 ii 的最大值,并输出达到该值的所有填数方案。

输入格式

输入三个整数 n,m,kn,m,k,依次表示格子数、连续取值的起点和每个数的下界。

输出格式

第一行输出最大的 ii。

接下来每行输出一个最优方案 a1,a2,…,ana_1,a_2,\ldots,a_n,表示沿圆周依次填入的数,且 a1a_1 必须是这些数中的最小值。所有符合要求的方案按字典序升序输出。如果有多个位置上都是最小值,旋转后得到不同序列的方案都要输出。例如 (1,1,2,3)(1,1,2,3)、(1,3,2,1)(1,3,2,1)、(1,2,3,1)(1,2,3,1) 和 (1,1,3,2)(1,1,3,2) 是四种不同的排列。

样例 1

5
2
1
21
1 3 10 2 5
1 5 2 10 3
2 4 9 3 5
2 5 3 9 4

数据规模与约定

1≤n≤61\le n\le6,1≤k≤m≤201\le k\le m\le20。

BZOJ 归档题面