const
   N = 20;
var
   JeObsazenySloupecek: array[1..N] of boolean;
   JeObsazenaDiagonalaMinus: array[1-N..N-1] of boolean;
   JeObsazenaDiagonalaPlus: array[1+1..N+N] of boolean;
   KdeJeDamaNaRadkuY: array[1..N] of integer;

procedure Tisk;
var x,y: integer;
begin
   for y:=1 to N do
   begin
      for x:=1 to N do
      if x = KdeJeDamaNaRadkuY[ y ] then write( ' D ' )
                                    else write( ' . ' );
      writeln
   end;
   writeln
end;



procedure UmistiDamuDoRadku( y: integer );
var x: integer;
begin
   if y > N then
               Tisk
            else
   for x:=1 to N do
   if    not JeObsazenySloupecek[ x ]
     and not JeObsazenaDiagonalaMinus[ x-y ]
     and not JeObsazenaDiagonalaPlus[ x+y ] then
   begin
      JeObsazenySloupecek[ x ]        := TRUE;
      JeObsazenaDiagonalaMinus[ x-y ] := TRUE;
      JeObsazenaDiagonalaPlus[ x+y ]  := TRUE;

      KdeJeDamaNaRadkuY[ y ] := x;
      UmistiDamuDoRadku( y+1 );

      JeObsazenySloupecek[ x ]        := FALSE;
      JeObsazenaDiagonalaMinus[ x-y ] := FALSE;
      JeObsazenaDiagonalaPlus[ x+y ]  := FALSE
   end

end;

var x,y: integer;
begin
   for y:=1 to N do
   for x:=1 to N do
   begin
      JeObsazenySloupecek[ x ]        := FALSE;
      JeObsazenaDiagonalaMinus[ x-y ] := FALSE;
      JeObsazenaDiagonalaPlus[ x+y ]  := FALSE
   end;

   UmistiDamuDoRadku( 1 )
end.








{ proskakat sachovnici konem - heuristika pokracovani s nejmensim poctem sousedu: }
const N = 6;

var  S: array[1..N,1..N] of integer;

procedure Tisk;
var x,y: integer;
begin
   for y:=1 to N do
   begin
      for x:=1 to N do
         if S[x,y]=-1 then write( ' . ' )
                      else write( S[x,y]:3 );
      writeln
   end;
   readln
end;

function PocetVolnychSousedu( x,y: integer ): integer;
var xx,yy, pocet: integer;
begin

   pocet := 0;

   for xx := x-2 to x+2 do
   for yy := y-2 to y+2 do
   if (xx>=1) and (xx<=N) and (yy>=1) and (yy<=N) then
   if abs(xx-x) + abs(yy-y) = 3 then
      if S[xx,yy]=-1 then
                       pocet := pocet+1;

   PocetVolnychSousedu := pocet
end;

procedure Skoc( x,y, krok: integer );
var xx,yy, i,j: integer;
    sousedi: array[0..8] of
             record
                x,y, pokracovani: integer;
             end;
    PocetSousedu: integer;

begin

   if (x>=1) and (x<=N) and (y>=1) and (y<=N)
      and (S[x,y] = -1) then
   begin
      S[x,y] := krok;
      { Tisk; {}

      if (krok=N*N) then Tisk
                    else
      begin
         PocetSousedu := 0;
         for xx := x-2 to x+2 do
         for yy := y-2 to y+2 do
         if abs(xx-x) + abs(yy-y) = 3 then
         begin
            PocetSousedu := PocetSousedu+1;
            sousedi[ PocetSousedu ].x := xx;
            sousedi[ PocetSousedu ].y := yy;
            sousedi[ PocetSousedu ].pokracovani := PocetVolnychSousedu( xx,yy );
         end;

         { seradit:
         for j := 1 to PocetSousedu-1 do
         for i := 1 to PocetSousedu-1 do
            if sousedi[ i ].pokracovani > sousedi[ i+1 ].pokracovani then
            begin
               sousedi[ 0 ] := sousedi[ i ];
               sousedi[ i ] := sousedi[ i+1 ];
               sousedi[ i+1 ] := sousedi[ 0 ];
            end;    {}

         { projit: }
         for i := 1 to PocetSousedu do
            Skoc( sousedi[ i ].x,sousedi[ i ].y, krok+1 );
      end;
      S[x,y] := -1
   end;
end;



var  i,j: integer;
begin
   for i:=1 to N do
   for j:=1 to N do
      S[i,j] := -1;

   Skoc( 1,2,  1 )


end.






const
   N = 6;
var
   S: array[1..N,1..N] of integer;


procedure Tisk;
var  x,y: integer;
begin
   for y:=1 to N do
   begin
      for x:=1 to N do
      if S[x,y] = 0 then write( ' . ' )
                    else write( S[x,y]:3 );
      writeln
   end;
   readln
end;

procedure Skoc( x,y, K: integer );
var  xx,yy: integer;
begin
   if (x>=1) and (x<=N) and (y>=1) and (y<=N) then
      if S[x,y]=0 then
      begin
         S[x,y] := K;

         { Tisk; {}

         if K=N*N then Tisk
                  else
         for xx := x-2 to x+2 do
         for yy := y-2 to y+2 do
         if abs(xx-x)+abs(yy-y) = 3 then
            Skoc( xx,yy, K+1 );

         S[x,y] := 0
      end

end;

begin
   Skoc( 1,1, 1 )
end.















const
   N = 12;
   P: array[1..N] of integer
    { = (17,5,-8,1,-2,-16, -27,49,50,16,-3,9); {}
    { = (5, 1000, 2, 1,1,2,16, 27,49,50,16,3); {}
    = (17,5,8,1,2,16, 27,49,50,16,30,9); {}


var
   pocetHer: integer;

function OKolikMuzuVyhrat( zac,kon: integer ): integer;
var  a,b: integer;
begin
   if zac > kon then begin OKolikMuzuVyhrat := 0; pocetHer := pocetHer+1 end
                else
   begin
      a := P[zac] - OKolikMuzuVyhrat( zac+1, kon );
      b := P[kon] - OKolikMuzuVyhrat( zac, kon-1 );

      if a > b then begin OKolikMuzuVyhrat := a; write('zac ') end
               else begin OKolikMuzuVyhrat := b; write('kon ' ) end

   end
end;

begin

   writeln;           e
   writeln( '=', OKolikMuzuVyhrat(1,N) );
   writeln( pocetHer )
end.


function OKolikMuzuVyhrat( zac,kon: integer ): integer;
var  a,b: integer;
begin
   if zac > kon then OKolikMuzuVyhrat := 0
                else
   begin
      a := P[zac] - OKolikMuzuVyhrat( zac+1, kon );
      b := P[kon] - OKolikMuzuVyhrat( zac, kon-1 );

      if a > b then OKolikMuzuVyhrat := a
               else OKolikMuzuVyhrat := b

   end
end;

begin

   writeln;
   writeln( '=', OKolikMuzuVyhrat(1,N) )
end.








function OKolikMuzeVyhratPrvniHrac( zac,kon,  prvni, druhy, natahu: integer )
                                                              : integer;
var  a,b: integer;
begin
   if zac > kon then
                   OKolikMuzeVyhratPrvniHrac := prvni-druhy
                else
      if natahu=1 then
      begin
            { OKolikMuzeVyhratPrvniHrac( zac,kon,  prvni, druhy, natahu ) }
         a := OKolikMuzeVyhratPrvniHrac( zac+1,kon, prvni+P[zac],druhy, 2 );
         b := OKolikMuzeVyhratPrvniHrac( zac,kon-1, prvni+P[kon],druhy, 2 );
         if a > b then OKolikMuzeVyhratPrvniHrac := a
                  else OKolikMuzeVyhratPrvniHrac := b
      end
         else
      if natahu=2 then
      begin
            { OKolikMuzeVyhratPrvniHrac( zac,kon,  prvni, druhy, natahu ) }
         a := OKolikMuzeVyhratPrvniHrac( zac+1,kon, prvni,druhy+P[zac], 1 );
         b := OKolikMuzeVyhratPrvniHrac( zac,kon-1, prvni,druhy+P[kon], 1 );
         if a < b then OKolikMuzeVyhratPrvniHrac := a
                  else OKolikMuzeVyhratPrvniHrac := b
      end
end;

begin

   writeln;

   writeln( OKolikMuzeVyhratPrvniHrac( 1,4, 0,0, 1 ) );
   writeln( OKolikMuzeVyhratPrvniHrac(1,12, 0,0, 1 ) ) {}
end.













var
   UzZnam:   array[1..100] of boolean;
   Vysledek: array[1..100] of longint;

function Fib( k: integer ): longint;
begin
   if UzZnam[ k ]=FALSE then
   begin
      if k<=2 then Vysledek[ k ] := 1
              else Vysledek[ k ] := Fib( k-1 ) + Fib( k-2 );
      UzZnam[ k ] := TRUE;
   end;

   Fib := Vysledek[ k ]
end;

var i: integer;
begin
   for i:=1 to 100 do
      writeln( i,': ', Fib(i) )
end.