Описание
Задан круг, разделенный на N секторов, и два целых числа М и К. В каждый из секторов круга помещается одно целое число, не меньшее К. Когда секторы заполнены числами, из них можно получать новые числа по следующим правилам:

  • взять число из одного сектора,

  • взять число, равное сумме двух или более чисел в смежных секторах

Из новых чисел составляется наибольшая последовательность подряд идущих чисел, начинающаяся с числа М: (М, М+1, М+2, ..., I ).

Пример на рис. 2.3 показывает, как получить все новые числа от 2 до 21 для приведенных на нем чисел в секторах. Песочным цветом выделены суммируемые числа

Задание
Напишите программу, которая определяет способ расстановки чисел в секторах, максимизирующий длину указанной последовательности.


Входные данные
Входной файл содержит три целых числа N, М и К (N 6, M 20, 0 K 20).

Выходные данные
Выведите в первую строку выходного файла наибольшее число I для неразрывной последовательности новых чисел от М до I, которая может быть получена из чисел в секторах. Далее выведите все наборы чисел в секторах, из которых можно получить такую последовательность. Каждый набор записывается в отдельную строку выходного файла в виде списка чисел, начинающегося с наименьшего из них (оно может быть не единственным). Числа в списке должны идти в том же порядке, в котором они записаны в секторах круга. Если наименьшее число встречается несколько раз, следует вывести все возможные комбинации. Например, (1 1 2 3), (1 2 3 1), (1 3 2 1) и (1 1 3 2)


Например:

GOCIRCLE.IN
5
2
1

GOCIRCLE.OUT
21
1 3 10 2 5
1 5 2 10 3
2 4 9 3 5
2 5 3 9 4





Комментарии
Пусть, для определенности, минимальное из чисел находится в первом секторе. Очевидно, что это число должно принадлежать интервалу от К до М (если К>М, то задача решений не имеет). Пусть S[i] - число в i-ом секторе. Задачу можно решать с помощью рекурсивного алгоритма расстановки чисел в секторах: на каждом шаге заполняется очередной сектор, корректируется множество новых чисел, которые можно получить, и осуществляется переход к следующему сектору. Какие числа мы можем ставить в секторы? В условии задачи сказано, что они обязаны быть не меньше К, но ничего не говорится о верхней границе.

Пусть N -1 секторов круга заполнено числами, а какой-то один пуст. Легко заметить, что мы, не используя этот сектор, можем получить не более, чем N·(N-1)/2 различных новых чисел. Обозначим через X первое число из последовательности М, М+1,..., которое мы не сможем получить. Понятно, что в оставшийся пустым сектор не имеет смысла ставить число, большее X. Поскольку Х не превосходит N·(N-1)/2+M, то последнее выражение является верхней границей на числа в секторах. Если S[1]<M, то эту границу можно уменьшить еще на 1. В секторы с номерами 2,3,...,N нужно помещать числа, не меньшие S[1], - это будет нижней границей

Для последнего сектора рассматриваемый диапазон чисел можно еще уменьшить. В качестве нижней границы (если N>2) можно взять число S[2] для того, чтобы исключить симметричные варианты, а в качестве верхней - то число X, о котором мы говорили выше. Если при этом сумма чисел, стоящих в секторах 1,...,N-1, и числа Х меньше наилучшего из найденных значений, то при любом варианте заполнения последнего сектора новое решение мы не получим.

Еще одно наблюдение. Пусть М<2К. Тогда числа М, М+1,...,2К-1 не могут быть получены как сумма чисел из нескольких (более одного) секторов, следовательно, либо (если 2K-M N) все они должны находиться в круге, либо (если 2K-M>N) в круге должны находиться числа М, М+1,...,M+N-1 и только они

Для ускорения работы программы введем матрицу Sum размера N×N, элемент Sum[i,j] которой будет равняться сумме чисел в j последовательных секторах, начиная с сектора i (если, конечно, все они уже заполнены). К моменту заполнения очередного сектора р у нас должны быть сформированы текущее множество S новых чисел, которые можно образовать, и числа Sum[i,j] (1 i<p, i+j p). После заполнения сектора р (при переходе к следующему сектору) необходимо вычислить числа Sum[i, p-i+1] (1 i р) и включить их в множество S

Если сектор последний (р=N), то вычисляем и оставшиеся элементы матрицы Sum, также занося их в множество S. Затем для получившегося набора чисел в секторах нужно найти число I из условия задачи и сравнить его с максимальным из ранее найденных (MaxI). Если I=MaxI, то добавляем набор к списку решений, если же I>MaxI, то очищаем список решений, вносим в него найденный набор и обновляем значение MaxI

При выводе результата для каждого из найденных решений с S[2]<S[N] нужно выдать также симметричное ему решение с S[2]>S[N], полученное путем зеркального отражения относительно биссектрисы первого сектора



Решение

{$A+,B-,D+,E+,F-,G+,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V-,X+} 
{$M 65520,0,655360} 
 
{$DEFINE GenAnswer} 
 
program gocircle; 
const NMax=6; 
      MMax=20; 
type O=array[1..Nmax] of byte; 
     Sums=array[1..NMax,1..NMax] of byte; 
     Sets=Set of byte; 
var N,M,K,Max,Num,Need,Up:integer; 
    A:O; 
    Best:array[1..100] of O; 
    Sum:Sums; 
    S,S1:Sets; 
 
Procedure Init; 
Begin 
  Close(input); 
  Assign(input,'gocircle.in'); ReSet(input); 
  read(N,M,K); 
  FillChar(A,SizeOf(A),0); 
End(*Init*); 
 
Procedure Check; 
Var i,j:integer; 
Begin 
  For i:=3 to N do 
    For j:=N-i+2 to N-1 do 
      Begin 
        Sum[i,j]:=Sum[i,j-1]+A[j-N+i-1]; 
        Include(S1,Sum[i,j]) 
      End; 
 
  i:=M; 
  While i in S1 do inc(i); 
 
  If i>Max then 
    Begin 
      Num:=1; 
      Best[Num]:=A; 
      Max:=i 
    End 
  Else 
    If i=Max then 
      Begin 
        inc(Num); 
        Best[Num]:=A 
      End 
End(*Check*); 
 
Procedure AddSum(k:integer); 
Var i:integer; 
Begin 
  Sum[k,1]:=A[k]; 
  Include(S1,A[k]); 
  For i:=k-1 downto 1 do 
    Begin 
      Sum[i,k-i+1]:=Sum[i,k-i]+A[k]; 
      Include(S1,Sum[i,k-i+1]) 
    End; 
End(*AddSum*); 
 
Function NewUp(k:integer):integer; 
Var i:integer; 
Begin 
  If k then NewUp:=Up 
  Else 
   Begin 
     i:=M; 
     While i in S1 do inc(i); 
     NewUp:=i 
   End 
End(*NewUp*); 
 
Procedure Solving(k:integer); 
Var i,Down,Need_,Up:integer; 
    S1_,S_:Sets; 
    Sum1:Sums; 
Begin 
  If k=N+1 then 
    Begin 
      Check; 
      Exit 
    End; 
 
  If k=N then Down:=A[2] 
  Else Down:=A[1]; 
 
  Up:=NewUp(K); 
  If (k=N) and (Sum[1,N-1]+Up then 
    Exit; 
 
  S1_:=S1; 
  Sum1:=Sum; 
  Need_:=Need; 
  S_:=S; 
 
  For i:=Down to Up do 
    If (Need>0) and ((N-k+1)<=Need) and (i in S) or 
       (Need=0) or (N-k+1>Need) then 
      Begin 
        A[k]:=i; 
        If (i in S) then 
          Begin 
            dec(Need); 
            Exclude(S,i) 
          End; 
 
        AddSum(k); 
        Solving(k+1); 
 
        Need:=Need_; 
        S:=S_; 
        S1:=S1_; 
        Sum:=Sum1 
      End; 
End(*Solving*); 
 
Procedure Solve; 
Var i:integer; 
Begin 
  Max:=M-1; 
  Up:=N*(N-1) div 2+M-1; 
  Num:=0; 
  FillChar(Sum,SizeOf(Sum),0); 
 
  For i:=K to M do 
    Begin 
      A[1]:=i; 
      Sum[1,1]:=i; 
      Need:=2*i-M; 
      If Need<0 then Need:=0; 
      If Need>0 then S:=[M..2*i-1]; 
      If (i=M) and (Need>0) then 
        Begin 
          dec(Need); 
          Exclude(S,M) 
        End; 
 
      S1:=[i]; 
      If i<>M then dec(Up); 
      Solving(2); 
      If i<>M then inc(Up) 
    End; 
End(*Solve*); 
 
Procedure Done; 
Var i,j:integer; 
Begin 
  Close(input); Close(output); 
  Assign(output,'gocircle.out'); ReWrite(output); 
 
{$IFDEF GenAnswer} 
  writeLn(2*Num); 
{$ENDIF} 
 
  writeln(Max-1); 
  For i:=1 to Num do 
    Begin 
      For j:=1 to N do write(Best[i,j],' '); 
      writeln; 
      write(Best[i,1],' '); 
      For j:=0 to N-2 do write(Best[i,N-j],' '); 
      writeln 
    End; 
 
  Close(output) 
End(*Done*); 
 
BEGIN 
  Init; 
  Solve; 
  Done 
END.

© Особенности национальных задач по информатике