记录编号	39023	评测结果	WEEEEEEEEE
题目名称	基因重组	最终得分	0
用户昵称	wo shi 刘畅	是否通过	未通过
代码语言	Pascal	运行时间	0.002 s
提交时间	2012-07-03 15:04:13	内存使用	43.08 MiB

var
  s1,s2,nq,now:string;
  e:array[0..20]of longint;
  d:array['A'..'Z']of longint;
  q,b:array[0..5000000]of longint;
  n,i,h,t,aim,qs:longint;
  head1,head2,p,pp,s,qq,tail,head:int64;
  v:array[0..5000000]of boolean;

function deal(ss:string):longint;
var
  now:string;
  nn,i:longint;
begin
  now:='';
  for i:=1 to n do now:=now+ss[i];
  nn:=0;
  for i:=1 to n do
    inc(nn,(ord(now[i])-48)*e[i+1]);
  deal:=nn;
end;

function re(s:longint):int64;
var
  now:string;
  num:int64;
  x:longint;
begin
  now:='';
  while s<>0 do
  begin
    x:=s mod 4;
    now:=chr(x+48)+now;
    s:=s div 4;
  end;
  val(now,num);
  re:=num;
end;

procedure print(k:longint);
begin
  writeln(k);
  close(input);
  close(output);
  halt;
end;

begin
  assign(input,'genea.in'); reset(input);
  assign(output,'genea.out'); rewrite(output);
  readln(n);
  readln(s1);
  readln(s2);
  d['A']:=0;
  d['C']:=1;
  d['G']:=2;
  d['T']:=3;
  e[n+1]:=1;
  for i:=n downto 1 do e[i]:=e[i+1]*4;
  h:=1;
  t:=1;
  b[1]:=0;
  now:='';
  for i:=1 to n do now:=now+chr(d[s1[i]]+48);
  q[1]:=deal(now);
  v[deal(s1)]:=true;
  now:='';
  for i:=1 to n do now:=now+chr(d[s2[i]]+48);
  aim:=deal(now);
  p:=1;
  for i:=1 to n-1 do p:=p*10;
  pp:=1;
  for i:=1 to n-2 do pp:=pp*10;
  repeat
    qs:=q[h];
    s:=re(qs);
    inc(t);
    head:=s div p;
    tail:=s mod p;
    qq:=tail*10+head;
    str(qq,nq);
    q[t]:=deal(nq);
    b[t]:=b[h]+1;
    if q[t]=aim then print(b[t]);
    if not v[q[t]] then
      v[q[t]]:=true
    else dec(t);

    inc(t);
    head1:=s div p;
    head2:=s div pp mod 10;
    tail:=s mod pp;
    qq:=head2*p+head1*pp+tail;
	str(qq,nq);
    q[t]:=deal(nq);
    b[t]:=b[h]+1;
    if q[t]=aim then print(b[t]);
    if not v[q[t]] then
      v[q[t]]:=true
    else dec(t);

    inc(h);
  until h>t;
  close(input);
  close(output);
end.