program CycleChain;
{$APPTYPE CONSOLE}
uses sysutils;
type
  TChainGenerator=class
  private
    FRandSeed: integer;
    FBits: array of Boolean;
    FIndex: integer;
    FIterCounter: integer;
    function GetState: boolean;
    procedure SetState(const Value: boolean);
  public
    procedure Init(N: integer);
    procedure Reset(AsRandom: boolean);

    property State: boolean read GetState write SetState;
    property NIter: integer read FIterCounter;
    procedure Move(FF: boolean);
  end;

{ TChainGenerator }

function TChainGenerator.GetState: boolean;
begin
  Result:=FBits[FIndex];
end;

procedure TChainGenerator.Init(N: integer);
begin
  SetLength(FBits, N);
  Randomize;
  FRandSeed:=RandSeed;
end;

procedure TChainGenerator.Move(FF: boolean);
begin
  if FF
    then FIndex:=(FIndex+1) mod length(FBits)
  else if FIndex=0
    then FIndex:=high(FBits)
    else dec(FIndex);
  inc(FIterCounter);
end;

procedure TChainGenerator.Reset(AsRandom: boolean);
var i: integer;
begin
  RandSeed:=FRandSeed;
  for i:=0 to high(FBits) do
  if AsRandom
    then FBits[i]:=random<0.5
    else FBits[i]:=odd(i);
  FIndex:=0;
  FIterCounter:=0;
end;

procedure TChainGenerator.SetState(const Value: boolean);
begin
  FBits[FIndex]:=value;
end;


//========= поиск в одном направлении =====================//
function SearchUni(CG: TChainGenerator): integer;
var
  i, CCounter: integer;
begin
  repeat
    CG.State:=false; //устанавливаем начальную позицию в 0
    CCounter:=0;     //cбрасываем счетчик
    repeat
      CG.Move(true);
      inc(CCounter);
    until not CG.State; //дошли нуля

    CG.State:=true; //переключили в 1

    for i:=CCounter-1 downto 0 do //возвращаемся назад
      CG.Move(false);

    if CG.State
      then Break; //изменился переключатель

    //перенос точки проверки
    CG.State:=true; //переключаем
    for i:=0 to CCounter-1 do //двигаемся обратно
      CG.Move(true);

  until false;
  Result:=CCounter;
end;


//========= поиск в двух направлениях =====================//
function SearchBi(CG: TChainGenerator): integer;
var
  i: integer;
  C: array[boolean] of Integer;
  FF: boolean;

begin
  C[false]:=0; C[true]:=0; FF:=true;
  repeat
    CG.State:=not FF; //устанавливаем начальную позицию в обратном направлении

    //движение без проверки
    for i:=0 to C[ff]-1 do begin
      CG.Move(FF);
      CG.State:=FF;
    end;

    //движение с проверкой
    repeat
      CG.Move(FF);
      inc(C[FF]);
      if (CG.State<>FF) then begin
        CG.State:=FF; //переключаем состояние
        Break;
      end;
    until false;

    //возврат в точку для проверки
    FF:=not FF;
    for i:=C[not FF]-1 downto 0 do begin
      CG.Move(FF);
      if i<>0
        then CG.State:=FF; //переключаем состояние для всех кроме точки проверки
    end;

    if CG.State<>FF
      then Break //изменился переключатель, нашли конец
    else begin
      //выбор направления движения
      if C[FF]>C[not FF] then
        FF:=not FF;

      //перенос точки проверки
      for i:=0 to C[FF] do begin
        CG.State:=FF;
        CG.Move(FF);
      end;
      inc(C[not FF], C[FF]);
      C[FF]:=0;
    end;
  until false;
  Result:=C[not FF];
end;



//================ Вызывалка ====================================//
var
  Rnd: boolean;
  i, N: integer;
  CG: TChainGenerator;

begin
  CG:=TChainGenerator.Create;

  for rnd:=false to true do begin
    if Rnd
      then Writeln('========Random test=========')
      else Writeln('========Regular test========');

    for i:=1 to 9 do begin
      N:=i*10;
      CG.Init(i*10);
      Write(format('N=%d',[N]));
      CG.Reset(Rnd);
      Write(format(' uni N/C %d/%d',[SearchUni(CG), CG.NIter]));
      CG.Reset(Rnd);
      Writeln(format(' bi N/C %d/%d',[SearchBi(CG), CG.NIter]));
    end;
    Writeln;
  end;
  Readln;
end.