Cod sursa(job #138007)

Utilizator vladianavladiana micu vladiana Data 17 februarie 2008 19:30:27
Problema Nivele Scor 20
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.5 kb
var fi,fo:text;
    n,i,ct,max,T,j:longint;
    a:array[1..2,1..70001]of longint;
procedure solve;
var i,niv,aux,nn:longint;
begin
  ct:=0; niv:=1; nn:=2;
  while n<>1 do
    begin
      i:=1;
      while i<n do
        if (a[niv,i]=max)and(a[niv,i+1]=max) then
          begin
            inc(ct);
            a[nn,ct]:=max-1;
            inc(i,2);
            if i=n then
              begin
                inc(ct);
                a[nn,ct]:=a[niv,i];
              end;
          end
      else
       if a[niv,i]=max then
          begin
            writeln(fo,'NU');
            exit;
          end
        else
          begin
            inc(ct);
            a[nn,ct]:=a[niv,i];
            inc(i);
            if i=n then
              begin
                inc(ct);
                a[nn,ct]:=a[niv,i];
              end;
          end;
      if ct=n then begin writeln(fo,'NU'); exit; end;
      if (n-ct)*2>(1 shl (max-1)) then begin writeln(fo,'NU'); exit; end;
      max:=max-1;
      n:=ct;
      ct:=0;
      aux:=niv;
      niv:=nn;
      nn:=aux;
    end;
  if n=1 then writeln(fo,'DA')
         else writeln(fo,'NU');
end;
begin
  assign(fi,'nivele.in'); reset(fi);
  assign(fo,'nivele.out'); rewrite(fo);
  read(fi,T);
  for j:=1 to T do
    begin
      read(fi,n);
      max:=0;
      for i:=1 to n do
        begin
          read(fi,a[1,i]);
          if a[1,i]>max then max:=a[1,i];
        end;
      solve;
    end;
  close(fi);
  close(fo);
end.