#P1168. The Circle

The Circle

描述
有一个被划分为若干扇形区域的圆圈。给定三个正整数:n(n≤6)、m(m≤20)和k(k≤20)。n表示扇形区域的数量。需为每个扇形区域选择整数,所有整数必须大于或等于k。当圆圈填满整数后,可以使用单个扇形区域的整数,或将两个或多个相邻扇形区域的整数相加得到新数。利用这些新数,需构造一个从m到i的连续整数序列(m, m+1, m+2, …, i)。

任务是选择扇形区域的整数,使得序列中的最大数i尽可能大。下图1展示了n=5、m=2、k=1时如何生成从2到21的所有数。扇形区域下方的^符号表示通过相加哪些区域来得到序列中的数。

输入
程序从标准输入读取数据,输入包含三个整数(n、m和k)。

输出
程序需向标准输出写入以下内容:

  • 可生成的连续序列中的最大数i。
  • 所有能生成从m到i的连续序列的圆圈数字排列(每行一个)。每个排列以最小数字开头(最小数字可能不唯一)。排列按升序排序。

示例说明:
(2 10 3 1 5) 不是有效解,因为未以最小数字开头。必须包含(1 3 10 2 5)和(1 5 2 10 3)。注意,(1 1 2 3)、(1 3 2 1)、(1 2 3 1)和(1 1 3 2)都应输出。

输入数据1
5
2
1

输出数据1
21
1 3 10 2 5
1 5 2 10 3
2 4 9 3 5
2 5 3 9 4

提示

FIGURE 1 (all circles have been cut open as indicated by arrow):

|----------| |----------| |----------| |----------|

.->|1|3|10|2|5|-. |1|3|10|2|5| |1|3|10|2|5| |1|3|10|2|5|

| |----------| | |----------| |----------| |----------|

| ^ | ^ ^ ^ ^

"---------------"

|----------| |----------| |----------| |----------|

.->|1|3|10|2|5|-. |1|3|10|2|5| |1|3|10|2|5| |1|3|10|2|5|

| |----------| | |----------| |----------| |----------|

| ^ ^ | ^ ^ ^ ^ ^ ^ ^ ^

"---------------"

|----------| |----------| |----------| |----------|

.->|1|3|10|2|5|-. |1|3|10|2|5| |1|3|10|2|5| |1|3|10|2|5|

| |----------| | |----------| |----------| |----------|

| ^ | ^ ^ ^ ^ ^ ^ ^ ^ ^

"---------------"

|----------| |----------| |----------| |----------|

.->|1|3|10|2|5|-. |1|3|10|2|5| |1|3|10|2|5| |1|3|10|2|5|

| |----------| | |----------| |----------| |----------|

| ^ ^ | ^ ^ ^ ^ ^ ^ ^ ^

"---------------"

|----------| |----------| |----------| |----------|

.->|1|3|10|2|5|-. |1|3|10|2|5| |1|3|10|2|5| |1|3|10|2|5|

| |----------| | |----------| |----------| |----------|

| ^ ^ ^ ^ | ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

"---------------"

|----------| |----------|

.->|1|3|10|2|5|-. |1|3|10|2|5|

| |----------| | |----------|

| ^ ^ ^ ^ | ^ ^ ^ ^ ^

"---------------"