Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: IOI'94 - Day 2 - Problem 3: The Circle
发信站: 哈工大紫丁香 (2002年03月29日13:27:08 星期五), 站内信件

IOI'94 - Day 2 - Problem 3: The Circle
You have a circle, divided into sectors. You are given three positive number
s: n (n<=6), m (m<=20) and k (k<=20). n is the number of sectors. Choose int
egers to place in each sector. All integers have to be greater or equal to k
. When the circle is filled you can use the integer in a single sector or ad
d the integers in two or more adjacent sectors to make a new number. Using t
hese new numbers you can create an unbroken sequence of all integers between
 m and i (m,m+1,m+2 ... i).
Your task is to choose integers for the sectors such that the largest number
 (i) in the sequence is as high as possible. Figure 1 below shows how to gen
erate all numbers from 2 to 21 (for n=5, m=2, k=1). The ^-sign below the sec
tors shows which sectors to add together to make numbers in the sequence.
Input Data
The INPUT.TXT file contains three integers (n, m and k). Example:
5
2
1
Output Data
The file OUTPUT.TXT must contain:
The highest number (i) that can be generated with the list of numbers.
All arrangements of numbers in a circle that produce a sequence from m to i.
 (One per line.) Each arrangement is a list of numbers starting with the sma
llest number (which is not necessarily unique).
(2 10 3 1 5) is NOT a valid solution, since it does not start with the small
est number. (1 3 10 2 5) and (1 5 2 10 3) must both be included in the outpu
t. Note that (1 1 2 3), (1 3 2 1), (1 2 3 1) and (1 1 3 2) should all be out
put.
The output for the example above might be:
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|
|  |----------| |    |----------|
|     ^ ^  ^ ^  |     ^ ^ ^  ^ ^
"---------------"

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]