|
Название задачи: Круги . |
 |
Условие
Задан круг, разделенный на N секторов, и два целых числа M и K. В каждый из секторов круга помещается одно целое число, не меньшее K. Когда секторы заполнены числами, из них можно получать новые числа по следующим правилам:взять число из одного сектора;
взять число, равное сумме двух или более чисел в смежных секторах.
Из новых чисел составляется наибольшая последовательность подряд идущих чисел, начинающаяся с числа M: (M, M+1, M+2, ..., I).
Пример на рисунке показывает, как получить все новые числа от 2 до 21 для приведенных на нем чисел в секторах. Серым цветом выделены суммируемые числа.
Напишите программу, которая определяет способ расстановки чисел в
секторах, максимизирующий длину указанной последовательности.
Входные данные
Входной файл содержит три целых числа N, M и K
(N ≤ 6, M ≤ 20, 0 ≤ K ≤ 20).
Выходные данные
Выведите в первую строку выходного файла наибольшее число I для
неразрывной последовательности новых чисел от M до I, которая может быть
получена из чисел в секторах. Далее выведите все наборы чисел в секторах, из
которых можно получить такую последовательность. Каждый набор
записывается в отдельную строку выходного файла в виде списка чисел,
начинающегося с наименьшего из них (оно может быть не единственным).
Числа в списке должны идти в том же порядке, в котором они записаны в
секторах круга. Если наименьшее число встречается несколько раз, следует
вывести все возможные комбинации. Например, (1 1 2 3), (1 2 3 1), (1 3 2 1) и (1
1 3 2).
Пример входного файла
5
2
1
Пример выходного файла
21
1 3 10 2 5
1 5 2 10 3
2 4 9 3 5
2 5 3 9 4
Решение
Скачать архив тестов и решенийПусть, для определенности, минимальное из чисел находится в первом секторе. Очевидно, что это число должно принадлежать интервалу от K до M (если K > M, то задача решений не имеет). Пусть S[i] – число в i-м секторе. Задачу можно решать с помощью рекурсивного алгоритма расстановки чисел в секторах: на каждом шаге заполняется очередной сектор, корректируется множество новых чисел, которые можно получить, и осуществляется переход к следующему сектору. Какие числа мы можем ставить в секторы? В условии задачи сказано, что они обязаны быть не меньше K, но ничего не говорится о верхней границе.
Пусть 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], полученное путем зеркального отражения относительно биссектрисы первого сектора.
