1142rnd.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

{$Q-,$R-}
program tju1142;
var
  num:array['A'..'Z']of byte;
  used:array[0..25]of boolean;
  pre,next:array[-1..26]of shortint;
  s:array[1..3]of string;
  n,i,p,t:shortint;
  found:boolean;
procedure out;
  var
    c:char;
  begin
    for c:='A' to chr(63+n) do
      write(num[c],' ');
    writeln(num[chr(64+n)]);
    found:=true;
  end;
procedure search(l,p,d:byte);
  var
    i,t:shortint;
  function check:boolean;
    var
      i,x,y,z,t:byte;
    begin
      check:=false;
      x:=num[s[1,1]];y:=num[s[2,1]];z:=num[s[3,1]];
      case ord(x<26)*4+ord(y<26)*2+ord(z<26) of
        7:if x+y>z then exit;
        6:if x+y>=n then exit;
        5:if x>z then exit;
        3:if y>z then exit;
      end;
      for i:=1 to l-1 do begin
        x:=num[s[1,i]];y:=num[s[2,i]];z:=num[s[3,i]];
        case ord(x<26)*4+ord(y<26)*2+ord(z<26) of
          7:if (n+z-x-y) mod n>1 then exit;
          6:if used[(x+y) mod n] and used[(x+y+1) mod n] then exit;
          5:if used[(n+z-x) mod n] and used[(n+z-1-x) mod n] then exit;
          3:if used[(n+z-y) mod n] and used[(n+z-1-y) mod n] then exit;
        end;
      end;
      check:=true;
    end;
  begin
    if l=0 then begin out;exit;end;
    if p=3 then begin
      t:=num[s[1,l]]+num[s[2,l]]+d;
      if num[s[3,l]]<26 then
        if num[s[3,l]]=t mod n then search(l-1,1,ord(t>=n)) else exit
      else
        if used[t mod n] then exit else begin
          num[s[3,l]]:=t mod n;used[t mod n]:=true;
          if check then begin
            pre[next[t mod n]]:=pre[t mod n];next[pre[t mod n]]:=next[t mod n];
            search(l-1,1,ord(t>=n));
            pre[next[t mod n]]:=t mod n;next[pre[t mod n]]:=t mod n;
          end;
          num[s[3,l]]:=26;used[t mod n]:=false;
        end;
    end
    else
      if num[s[p,l]]<26 then
        search(l,p+1,d)
      else begin
        i:=next[-1];
        repeat
          if not used[i] then begin
            num[s[p,l]]:=i;used[i]:=true;
            if check then begin
              pre[next[i]]:=pre[i];next[pre[i]]:=next[i];
              search(l,p+1,d);if found then exit;
              pre[next[i]]:=i;next[pre[i]]:=i;
            end;
            num[s[p,l]]:=26;used[i]:=false;
          end;
          i:=next[i];
        until i=26;
      end;
  end;
begin
  repeat
    readln(n);
    readln(s[1]);readln(s[2]);readln(s[3]);
    fillchar(num,sizeof(num),26);
    fillchar(used,sizeof(used),0);
    for i:=0 to n-1 do pre[i]:=i;
    for i:=0 to n-1 do begin
      p:=random(n);t:=pre[i];pre[i]:=pre[p];pre[p]:=t;
    end;
    next[-1]:=pre[0];for i:=0 to n-2 do next[pre[i]]:=pre[i+1];next[pre[n-1]]:=26;
    for i:=-1 to n-1 do pre[next[i]]:=i;
    found:=false;
    search(n,1,0);
  until seekeof;
end.