INFOMAN брой 5

{
                                ИГРА С ЧИСЛА
                                ------------
     Разглежда се следната игра. Дадени са N (0 < N < 50) пула и константа M
 (0 < M < 20 ). Играчите A и B започват да правят ходове последователно,като
 A започва пръв. На всеки ход съответния играч избира цяло положително число
 k <= min (M,N) и взима толкова пула. Остават N-k пула и на ход идва другият
 играч. Не е позволено някой да избира числа, които вече са били избирани от
 единия или от другия играч в предишни ходове. Играта приключва когато едини-
 ят от играчите не може да направи ход. Победител е този,който е направил по-
 следния ход. При дадени числа N и M да се напише програма, която намира кой
 от играчите (A или B) има печеливша стратегия.На първия ред в изходния файл
 да се запише играчът,който има печеливша стратегия. На следващите редове да
 се изведат всички възможни първоначални ходове на играч A. За всеки от тези
 ходове да се изведе "печеливш" ако е печеливш за играч A или един от печели-
 вшите ходове на играч B, ако съответния ход не е печеливш за играч A.

     РЕШЕНИЕ: Решението на задачата се основава на основния принцип, че един
 ход е печеливш за играч A, тогава и само тогава, когато играч A може да взе-
 ме толкова пула, че позицията,  която се създава да е непечеливша заиграч B.
 С други думи една ситуация е печеливша за играч A,  ако той може така да иг-
 рае, че да постави играч B в губеща ситуация. Същото се отнася и за играч B.
 Една ситуация е печеливша за играч B, ако той може дака да играе, че да пос-
 тави играч A в губеща ситуация.  Правилата са дефинирани рекурсивно и могат
 да бъдат реализирани с рекурсивн функции.  Естествено, ако играчът, който е
 на ход няма какво да мести, той губи,  а иначе трябва да се проверят всички
 възможни ходове. Ако сред тези ходове има ход, при който другият играч губи,
 то текущият играч печели. Ясно е, че ако има поне 1 печеливш ход, то остана-
 лите няма нужда да се проверяват, защото ситуацията е печеливша.  Понеже се
 иска в решението да се отпечатат отговорите на B при всеки възможен начален
 ход на A, е необходимо да си пазим за всяка една ситуация дали B печели или
 губи и ако печели, кой е печелившият му ход  (колко пула трябва да вземе за
 да постави A в губеща позиция). Ако условието допускаше един играч да взема
 пулове, които са вече използвани, то можеше да се разчита, че винаги когато
 се търси дали една позиция (N,M) е печеливша, отговорът да е еднакъв.  Това
 би довело до линеен алгоритъм. Но понеже една позиция (ситуация в играта)се
 определя не само от числата (N,M), но и от множество недопустими ходове, то
 трябва да се изчерпят всички възможности за ход при всяка ситуация. Само то-
 ва гарантира правилно решение,  въпреки, че води до експоненциална сложност
 на алгоритъма. Понеже нас ни интересуват само ходовете на B, когато играч A
 е взел от 1 до M пула, става ясно, че ако имаме останали между N-M и N пула,
 трябва да изчерпваме всички възможни ходове на A и B. Ако имаме по-малко пу-
 лове, вече не е нужно да изчерпваме всички варианти, а е достатъчно като на-
 мерим един печеливш ход на играча, който е на ход,  да обявим ситуацията за
 печеливша за този играч и да излезем от функцията. Така ускоряваме значител-
 но алгоритъма.
}

{$R-,Q-,S-}
CONST InFileName  = '';
      OutFileName = '';
      MaxN = 200;


VAR N,M: integer;
    Used: array[1..MaxN] of boolean;
    Bpech: array[0..MaxN] of boolean;
    HodB: array[0..MaxN] of integer;


Procedure ReadData;
Var F: Text;
Begin
  Assign(F,InFileName); Reset(F);
  ReadLn(F,N,M); Close(F);
End;

Function Min(a,b:integer): integer;
Begin if a<b then Min:=a else Min:=b; End;

Function Apecheli(X:integer): boolean; forward;

Function Bpecheli(X:integer): boolean;
{Връща дали B печели, при условие че е на ход и има останали X пула}
Var I: integer;
    pecheli: boolean;
Begin
  pecheli:= false;
  for I:= 1 to min(M,X) do
    if not Used[I] then
      begin
        Used[I]:=true;
        if not Apecheli(X-I) then
          begin {B печели, ако при вземене на I пула, A губи}
	    pecheli:=true;
            if X < N-M then
	      begin Used[I]:=false; Break; end
            else HodB[X]:=I;
	  end;
        Used[I]:=false;
      end;
  Bpech[X]:= pecheli;
  Bpecheli:= pecheli;
End;

Function Apecheli(X:integer): boolean;
{Връща дали A печели, при условие че е на ход и има останали X пула}
Var I: integer;
    pecheli: boolean;
Begin
  pecheli:= false;
  for I:= 1 to min(M,X) do
    if not Used[I] then
      begin
        Used[I]:=true;
        if not Bpecheli(X-I) then
	  pecheli:=true;  {A печели, ако при вземене на I пула, B губи}
        Used[I]:=false;
        if X < N-M then
          if pecheli then Break;
      end;
  Apecheli:= pecheli;
End;

Procedure Solve;
Var OutF: Text;
    I: integer;
Begin
  Assign(OutF,OutFileName); Rewrite(OutF); WriteLn(OutF);
  FillChar(Used,SizeOf(Used),false);
  if Apecheli(N) then
    WriteLn(OutF,'A побеждава')
  else WriteLn(OutF,'B побеждава');
  {Печатаме отговора на B или "печеливш" при всички начални ходове на A}
  for I:= 1 to min(M,N) do
    if Bpech[N-I] then
      WriteLn(OutF,I,' ',HodB[N-I])
    else WriteLn(OutF,I,' печеливш');
  Close(OutF);
End;

BEGIN
  ReadData;
  Solve;
END.