IOI '94 - Haninge, Sweden
The Circle
You have a circle, divided into sectors. You are given three positive numbers: n (n ≤ 6), m (m ≤ 20) and k (k ≤ 20). n is the number of sectors. Choose integers 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 add the integers in two or more adjacent sectors to make a new number. Using these 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 generate all numbers from 2 to 21 (for n=5, m=2, k=1). The caret sign ^ below the sectors shows which sectors to add together to make numbers in the sequence.
Input Format
The input consists of the three integers: n, m, and k, in that order, on three separate lines.
Output Format
The output should contain, in the format of the sample output case shown below:- 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 smallest number (which is not necessarily unique).
(2 10 3 1 5) is NOT a valid solution, since it does not start with the smallest number. (1 3 10 2 5) and (1 5 2 10 3) must both be included in the output. Note that (1 1 2 3), (1 3 2 1), (1 2 3 1) and (1 1 3 2) should all be output. That is, all possible solutions in which the first number is minimal should be printed, even if they do not represent unique circles. Of course, you should not print a particular sequence more than once. Solutions should be printed in lexicographical order. That is, one sequence should come before another if the first position at which the two differ contains a lower value in the first sequence than in the second.
Sample Input
5 2 1
Sample Output
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|
| |----------| | |----------|
| ^ ^ ^ ^ | ^ ^ ^ ^ ^
"---------------"
All Submissions
Best Solutions
Point Value: 17 (partial)
Time Limit: 2.00s
Memory Limit: 8M
Added: Aug 20, 2009
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
It's quiet in here...