unit libconq;

interface

const MAX_N = 2000;
      MAX_M = 1000000000;

procedure start(var N: longint; var stairs: array of longint);
function step(subset: array of longint): longint;

implementation
uses linux;

{ $define __DEBUG__}

const game_N: longint = 0;
      lib_usage: longint = 0;

var st: array[0..MAX_N] of longint;
    lib_txt: string;

procedure lib_error(code: longint; s: string);
var f:text;
begin
    assign(f,'libconq_haluzka.out'); rewrite(f);
    writeln(f,s);
    close(f);
    halt(code);
end;

function int2str(i:longint): string;
var s:string;
begin
    str(i,s);
    int2str:=s;
end;

procedure start(var N: longint; var stairs: array of longint);
var f: text;
    i: longint;
begin
    if (lib_usage<>0) then lib_error(1,'start() called too many times');
    inc(lib_usage);

    assign(f,'libconq.dat');
    {$I-}
    reset(f);
    {$I+}
    if IOResult<>0 then lib_error(2,'cannot open libconq.dat file')
    else
    begin
	read(f,N);
	for i:=0 to N-1 do read(f,stairs[i]);
	close(f);
    end;
  
    game_N:=N;
    for i:=1 to N do st[i]:=stairs[i-1];
end;

function decide(a: array of longint): longint;
var i,diff,n,ret: longint;
    va,vb: array[1..MAX_N] of longint;
begin
    ret:=1;
    
    for i:=1 to game_N do va[i]:=a[i-1];
    for i:=1 to game_N do vb[i]:=st[i]-a[i-1];

    { normalize va and vb }
    for i:=game_N downto 2 do
    begin
	n:=va[i] div 2;
	dec(va[i],2*n);
	inc(va[i-1],n);

	n:=vb[i] div 2;
	dec(vb[i],2*n);
	inc(vb[i-1],n);
    end;

{$ifdef __DEBUG__}
    writeln('va: '); for i:=game_N downto 1 do write(va[i],' '); writeln;
    writeln('vb: '); for i:=game_N downto 1 do write(vb[i],' '); write('  --> choosing ');
{$endif}

    { choose va or vb -- whichever has larger value }
    diff:=0;
    for i:=1 to game_N do
    begin
	if (va[i]<>vb[i]) then 
	begin
	    diff:=i; 
	    break;
	end;
    end;

    { if both va and vb >= 1/2, choose the one which left first soldier
       farther from stair No. 1  }
    if ((va[2]+va[1]>=1) and (vb[2]+vb[1]>=1)) then
    begin
	for i:=1 to game_N do
	  if (st[i]<>0) then
	  begin
	    if (a[i-1]<>0) then ret:=2 else ret:=1;
	    break;
	  end;
    end
    else
    begin
	if (diff<>0) then
	begin
	    if (va[diff]=0) then ret:=1   { i.e. vb has bigger value }
			    else ret:=2;
	end else ret:=1;
    end;

{$ifdef __DEBUG__}
    writeln(ret);
{$endif}
    
    decide:=ret;
end;

function step(subset: array of longint): longint;
var choice,i,wrong,cnt: longint;
begin
    if (lib_usage=0) then lib_error(1,'call start() first!');
    inc(lib_usage);

    { check if a is a valid subset }
    wrong:=0;
    for i:=1 to game_N do
    begin
	if ((subset[i-1]<0) or (subset[i-1]>st[i])) then wrong:=i;
	if (wrong<>0) then break;
    end;
  
    if (wrong<>0) then
    begin
	lib_txt:='wrong number of soldiers on stair '+int2str(wrong)+
		 ': '+int2str(subset[wrong-1])+
		 ' requested, '+int2str(st[wrong])+
		 ' available';
	lib_error(1,lib_txt);
    end;
  
    { decide }
    choice:=decide(subset);
    
    { choice 1: move subset one stair up, discard the rest }
    if (choice=1) then
    begin
	for i:=1 to game_N do st[i]:=subset[i-1];
	for i:=1 to game_N do st[i-1]:=st[i];
	st[game_N]:=0;
    end
    else  { choice 2: discard subset, move complement one stair up }
    begin
	for i:=1 to game_N do dec(st[i],subset[i-1]);
	for i:=1 to game_N do st[i-1]:=st[i];
	st[game_N]:=0;
    end;
  
    { check if there are any soldiers left }
    { check if there is any soldier at position 1 }
    cnt:=0;
    for i:=1 to game_N do if st[i]<>0 then inc(cnt);
  
    if (cnt=0) then
    begin
{$ifdef __DEBUG__}
        lib_txt:='You lost! (last choice='+int2str(choice)+')');
{$else}
        lib_txt:='You lost!';
{$endif}
	lib_error(0,lib_txt);
    end;
  
    if (st[1]<>0) then
    begin
{$ifdef __DEBUG__}
	lib_txt:='You won! (choice='+int2str(choice)+')';
{$else}
	lib_txt:='You won!';
{$endif}
	lib_error(0,lib_txt);
    end;

    step:=choice;
end;

end.