cryptcow.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 111 行

{
ID:maigoak1
PROG:cryptcow
}

program cryptcow;
const
  msg='Begin the Escape execution at the Break of Dawn';
  key=['C','O','W'];
  bigprime=999983;
var
  fin,fout:text;
  adj:array[' '..'~',' '..'~']of boolean;
  letters1,letters2:array[' '..'~']of byte;
  impos:array[2000000..8999999]of boolean;
  s:string;
  msglen,steps,i:byte;
  c:char;
procedure fail;
  begin
    writeln(fout,'0 0');
    close(fout);
    halt;
  end;
procedure succeed;
  begin
    writeln(fout,'1 ',steps);
    close(fout);
    halt;
  end;
procedure decode(s:string;level:byte);
  var
    len,first,last,i,j,k:byte;
    t:string;
  function hash(s:string):longint;
    var
      i:byte;
    begin
      hash:=0;
      for i:=1 to len do
        hash:=(hash*100+ord(s[i])) mod bigprime;
      hash:=hash+level*1000000;
    end;
  function before(p:byte):string;
    var
      i:byte;
    begin
      before:='';
      for i:=p-1 downto 1 do
        if s[i] in key then exit else before:=s[i]+before;
    end;
  function after(p:byte):string;
    var
      i:byte;
    begin
      after:='';
      for i:=p+1 to len do
        if s[i] in key then exit else after:=after+s[i];
    end;
  function ok(t:string):boolean;
    begin
      if (t='') or (pos(t,msg)>0) then ok:=true else ok:=false;
    end;
  begin
    len:=length(s);
    if (level>1) and (level<steps) then if impos[hash(s)] then exit;
    if s=msg then succeed;
    if len=msglen then exit;
    first:=pos('C',s);
    if copy(s,1,first-1)<>copy(msg,1,first-1) then exit;
    for i:=len downto 1 do
      if s[i]='W' then begin last:=i;break;end;
    if copy(s,last+1,len-last)<>copy(msg,last+msglen-len+1,len-last) then exit;

    for j:=first+1 to last-1 do
      if s[j]='O' then
        for i:=first to j-1 do
          if s[i]='C' then
            if ok(before(i)+after(j)) then
              for k:=j+1 to last do
                if s[k]='W' then
                  if ok(before(k)+after(i)) and ok(before(j)+after(k)) then
                    decode(copy(s,1,i-1)+copy(s,j+1,k-j-1)+copy(s,i+1,j-i-1)+copy(s,k+1,len-k),level+1);
    if (level>1) and (level<steps) then impos[hash(s)]:=true;
  end;
begin
  fillchar(letters1,sizeof(letters1),0);
  fillchar(letters2,sizeof(letters2),0);
  assign(fin,'cryptcow.in');
  reset(fin);
  readln(fin,s);
  close(fin);

  for i:=1 to length(s) do
    inc(letters2[s[i]]);
  if (letters2['C']<>letters2['O']) or (letters2['O']<>letters2['W']) then fail;
  steps:=letters2['C'];
  letters2['C']:=0;letters2['O']:=0;letters2['W']:=0;
  msglen:=length(msg);
  for i:=1 to msglen do
    inc(letters1[msg[i]]);
  for c:=' ' to '~' do
    if letters1[c]<>letters2[c] then fail;

  assign(fout,'cryptcow.out');
  rewrite(fout);
  fillchar(impos,sizeof(impos),0);
  decode(s,1);
  fail;
end.