Пример на рисунке показывает, как получить все новые числа от 2 до 21 для приведенных на нем чисел в секторах. Серым цветом выделены суммируемые числа.
Напишите программу, которая определяет способ расстановки чисел в
секторах, максимизирующий длину указанной последовательности.
Входные данные
Входной файл содержит три целых числа N, M и K
(N ≤ 6, M ≤ 20, 0 ≤ K ≤ 20).
Выходные данные
Выведите в первую строку выходного файла наибольшее число I для
неразрывной последовательности новых чисел от M до I, которая может быть
получена из чисел в секторах. Далее выведите все наборы чисел в секторах, из
которых можно получить такую последовательность. Список наборов должен быть
отсортирован в порядке возрастания. Каждый набор
записывается в отдельную строку выходного файла в виде списка чисел,
начинающегося с наименьшего из них (оно может быть не единственным).
Числа в списке должны идти в том же порядке, в котором они записаны в
секторах круга. Если наименьшее число встречается несколько раз, следует
вывести все возможные комбинации. Например, (1 1 2 3), (1 1 3 2), (1 2 3 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
Пусть N-1 секторов круга заполнено числами, а какой-то один пуст. Легко заметить, что мы, не используя этот сектор, можем получить не более, чем N(N-1)/2 различных новых чисел. Обозначим через X первое число из последовательности M, M+1, ..., которое мы не сможем получить. Понятно, что в оставшийся пустым сектор не имеет смысла ставить число, большее X. Поскольку X не превосходит N(N-1)/2+M, то последнее выражение является верхней границей на числа в секторах. Если S[1] < M, то эту границу можно уменьшить еще на 1. В секторы с номерами 2, 3, ..., N нужно помещать числа, не меньшие S[1], – это будет нижней границей.
Для последнего сектора рассматриваемый диапазон чисел можно еще уменьшить. В качестве нижней границы (если N > 2) можно взять число S[2] для того, чтобы исключить симметричные варианты, а в качестве верхней – то число X, о котором мы говорили выше. Если при этом сумма чисел, стоящих в секторах 1, ..., N-1, и числа X меньше наилучшего из найденных значений, то при любом варианте заполнения последнего сектора новое решение мы не получим.
Еще одно наблюдение. Пусть M < 2K. Тогда числа M, M+1, ..., 2K-1 не могут быть получены как сумма чисел из нескольких (более одного) секторов, следовательно, либо (если 2K-M ? N) все они должны находиться в круге, либо (если 2K-M > N) в круге должны находиться числа M, M+1, ..., M+N-1 и только они.
Для ускорения работы программы введем матрицу Sum размера N × N, элемент Sum[i, j] которой будет равняться сумме чисел в j последовательных секторах, начиная с сектора i (если, конечно, все они уже заполнены). К моменту заполнения очередного сектора p у нас должны быть сформированы текущее множество S новых чисел, которые можно образовать, и числа Sum[i, j] (1 ≤ i < p, i+j ≤ p). После заполнения сектора p (при переходе к следующему сектору) необходимо вычислить числа Sum[i, p-i+1] (1 ≤ i ≤ p) и включить их в множество S.
Если сектор последний (p = N), то вычисляем и оставшиеся элементы матрицы Sum, также занося их в множество S. Затем для получившегося набора чисел в секторах нужно найти число I из условия задачи и сравнить его с максимальным из ранее найденных (MaxI). Если I = MaxI, то добавляем набор к списку решений, если же I > MaxI, то очищаем список решений, вносим в него найденный набор и обновляем значение MaxI.
При выводе результата для каждого из найденных решений с S[2] < S[N] нужно выдать также симметричное ему решение с S[2] > S[N], полученное путем зеркального отражения относительно биссектрисы первого сектора.