最终写了453行...
题目:等价表达式
状态: [color=green]Accepted[/color]
测评机： Xeond[6]
得分： 100分
提交日期： 2011-4-13 16:06:00
有效耗时： 1734毫秒
测试结果1: [color=green]通过本测试点|有效耗时172ms[/color]
测试结果2: [color=green]通过本测试点|有效耗时62ms [/color]
测试结果3: [color=green]通过本测试点|有效耗时63ms [/color]
测试结果4: [color=green]通过本测试点|有效耗时172ms [/color]
测试结果5: [color=green]通过本测试点|有效耗时172ms [/color]
测试结果6: [color=green]通过本测试点|有效耗时171ms [/color]
测试结果7: [color=green]通过本测试点|有效耗时188ms [/color]
测试结果8: [color=green]通过本测试点|有效耗时359ms [/color]
测试结果9: [color=green]通过本测试点|有效耗时188ms [/color]
测试结果10: [color=green]通过本测试点|有效耗时187ms [/color]
program R18;
type ar=array[0..3000]of longint;
const maxn=50;
var nk,ni,ii,jj,kk,i,j,k,m,n,l:longint;
str:string;
st1,st2:string;
b:array[0..maxn]of boolean;
a,temp:ar;
ans:array[0..maxn]of boolean;
f:array[0..maxn,0..maxn]of ar;
an:ar;
sl,sr:longint;
kh:array[0..maxn]of record
left,right:longint;
end;
function check(ch:char):boolean;
var k:longint;
begin
k:=ord(ch);
if (k>=ord('0'))and(k<=ord('9')) then exit(true);
exit(false);
end;
function compare(aa,bb:ar):boolean;
var i:longint;
begin
i:=3000;
while true do
begin
if aa[i]<bb[i] then exit(false);
if aa[i]>bb[i] then exit(true);
dec(i);
if i=0 then exit(true);
end;
end;
{^}
procedure work1(n:longint);
var ii,jj,i,j,k,m,l1,l2:longint;
sum,tt,t2:ar;
fh:longint;
begin
// writeln('^',n);
i:=n-1;
fillchar(sum,sizeof(sum),0);
fillchar(tt,sizeof(tt),0);
while b[i] do dec(i);
inc(i);
// writeln(i);
tt:=f[i,n-1];
fh:=tt[0]; //writeln(fh);
if not b[n+2] then k:=f[n+1,n+1][1] else k:=10;
// writeln(k,b[n+2]);
sum:=tt;
ii:=i;
if k=10 then jj:=n+2 else jj:=n+1;
l1:=3000;l2:=3000;
while (tt[l1]=0)and(l1>0) do dec(l1);
l2:=l1;
if l1<>0 then
for m:=1 to k-1 do
begin
fillchar(t2,sizeof(t2),0);
for i:=1 to l2 do
for j:=1 to l1 do
inc(t2[i+j-1],tt[i]*sum[j]);
l1:=l1*2;
for i:=1 to l1 do
begin
inc(t2[i+1],t2[i] div 10);
t2[i]:=t2[i] mod 10;
end;
while t2[l1]=0 do dec(l1);
sum:=t2;
end;
f[ii,jj]:=sum;
if k mod 2=0 then f[ii,jj][0]:=0 else f[ii,jj][0]:=fh;
b[n]:=true;
end;
{X}
procedure work2(n:longint);
var ii,jj,i,j,k,m:longint;
a1,a2,ss:ar;
l1,l2:longint;
fh,fh1,fh2:longint;
begin
// writeln('X',n);
ii:=n-1;
while b[ii] do dec(ii);
inc(ii);
jj:=n+1;
while b[jj] do inc(jj);
dec(jj);
a1:=f[ii,n-1];fh1:=a1[0];
a2:=f[n+1,jj];fh2:=a2[0];
l1:=3000;l2:=3000;
while (a1[l1]=0)and(l1>0) do dec(l1);
while (a2[l2]=0)and(l2>0) do dec(l2);
fillchar(ss,sizeof(ss),0);
for i:=1 to l1 do
for j:=1 to l2 do
inc(ss[i+j-1],a1[i]*a2[j]);
l1:=l1+l2;
for i:=1 to l1 do
begin
inc(ss[i+1],ss[i] div 10);
ss[i]:=ss[i] mod 10;
end;
fh:=fh1+fh2;
// writeln('fh:',fh);
// writeln('fh1:',fh1);
// writeln('fh2:',fh2);
f[ii,jj]:=ss;
if fh=-1 then f[ii,jj][0]:=-1 else f[ii,jj][0]:=0;
b[n]:=true;
end;
{+}
procedure work3(n:longint);
var ii,jj,i,j,k,m:longint;
l1,l2:longint;
a1,a2,ss:ar;
fh,fh1,fh2:longint;
begin
// writeln('+',n);
ii:=n-1;
while b[ii] do dec(ii);
inc(ii);
jj:=n+1;
while b[jj] do inc(jj);
dec(jj);
a1:=f[ii,n-1];fh1:=a1[0];
a2:=f[n+1,jj];fh2:=a2[0] ;
l1:=3000;l2:=3000;
while (a1[l1]=0)and(l1>0) do dec(l1);
while (a2[l2]=0)and(l2>0) do dec(l2);
fillchar(ss,sizeof(ss),0);
if fh1=fh2 then
begin
if l1<l2 then l1:=l2;
for i:=1 to l1 do ss[i]:=a1[i]+a2[i];
for i:=1 to l1 do
begin
inc(ss[i+1],ss[i] div 10);
ss[i]:=ss[i]mod 10;
end;
f[ii,jj]:=ss;f[ii,jj][0]:=fh1;
end
else
begin
if compare(a1,a2) then fh:=fh1
else
begin
fh:=fh2;
ss:=a1;
a1:=a2;
a2:=ss;
end;
fillchar(ss,sizeof(ss),0);
if l1<l2 then l1:=l2;
for i:=1 to l1 do ss[i]:=a1[i]-a2[i];
for i:=1 to l1 do
if ss[i]<0 then
begin
inc(ss[i],10);
dec(ss[i+1]);
end;
f[ii,jj]:=ss;f[ii,jj][0]:=fh;
end;
b[n]:=true;
end;
{-}
procedure work4(n:longint);
var ii,jj,i,j,k,m:longint;
l1,l2:longint;
a1,a2,ss:ar;
fh,fh1,fh2:longint;
begin
// writeln('-',n);
ii:=n-1;
while b[ii] do dec(ii);
inc(ii);
jj:=n+1;
while b[jj] do inc(jj);
dec(jj);
a1:=f[ii,n-1];fh1:=a1[0];
a2:=f[n+1,jj];fh2:=a2[0];
l1:=3000;l2:=3000;
while (a1[l1]=0)and(l1>0) do dec(l1);
while (a2[l2]=0)and(l2>0) do dec(l2);
fillchar(ss,sizeof(ss),0);
if l1<l2 then l1:=l2;
if fh1<>fh2 then
begin
if fh1=-1 then fh:=-1 else fh:=0;
for i:=1 to l1 do ss[i]:=a1[i]+a2[i];
for i:=1 to l1 do
begin
inc(ss[i+1],ss[i] div 10);
ss[i]:=ss[i] mod 10;
f[ii,jj]:=ss;f[ii,jj][0]:=fh;
end;
end
else
begin
if compare(a1,a2) then fh:=fh1
else
begin
if fh1=0 then fh:=-1 else fh:=0;
ss:=a1;
a1:=a2;
a2:=ss;
end;
fillchar(ss,sizeof(ss),0);
for i:=1 to l1 do ss[i]:=a1[i]-a2[i];
for i:=1 to l1 do
begin
if ss[i]<0 then
begin
dec(ss[i+1]);
inc(ss[i],10);
end;
end;
f[ii,jj]:=ss;f[ii,jj][0]:=fh;
end;
b[n]:=true;
end;
procedure work(le,ri:longint);
var i,j,k,m,n:longint;
tt:ar;
begin
{^}
for i:=le to ri do
if (str[i]='^')and(not b[i]) then
work1(i);
{X}
for i:=le to ri do
if (str[i]='*')and(not b[i]) then
work2(i);
{+,-}
for i:=le to ri do
if ((str[i]='+')or(str[i]='-'))and(not b[i]) then
begin
if str[i]='+' then work3(i);
if str[i]='-' then work4(i);
end;
end;
{main}
begin
a[1]:=6;
readln(str);
l:=length(str);
fillchar(ans,sizeof(ans),false);
nk:=0;
for i:=1 to l do if str[i]=' ' then inc(nk);
for nk:=1 to nk do
begin
for i:=1 to l-nk+1 do
if str[i]=' ' then break;
delete(str,i,1);
end;
l:=length(str);
// writeln(str,'//',l);
fillchar(b,sizeof(b),false);
{find()}
k:=0;
for i:=1 to l do
begin
if str[i]='(' then
begin
inc(k);
kh[k].left:=i;
end;
if str[i]=')' then
begin
for j:=k downto 1 do
if kh[j].right=0 then
begin
kh[j].right:=i;
break;
end;
end;
end;
{ for i:=1 to k do if kh[i].right=0 then
begin
inc(l);
kh[i].right:=l;
end; }
// writeln('k:',k);
// for i:=1 to k do
// writeln(i,'L:',kh[i].left,'R:',kh[i].right);
{get 'a'}
for i:=1 to l do
if str[i]='a' then
begin
b[i]:=true;
f[i,i]:=a;
end;
{get number}
i:=1;
while true do
begin
if check(str[i]) then
begin
j:=i;
while (check(str[j]))and(j<l) do inc(j);
if not check(str[j]) then dec(j);
kk:=j-i+1;
fillchar(temp,sizeof(temp),0);
for ii:=1 to kk do
temp[ii]:=ord(str[j-ii+1])-48;
f[i,j]:=temp;
for ii:=i to j do b[ii]:=true;
// writeln(i,'-->',j);
i:=j;
// for ii:=kk downto 1 do write(temp[ii]);writeln('!');
end;
inc(i);
if i>l then break;
end;
// for i:=0 to l do write(b[i],' ');
{work ()}
for i:=k downto 1 do
begin
// writeln('L:',kh[i].left);
// writeln('R:',kh[i].right);
work(kh[i].left+1,kh[i].right-1);
f[kh[i].left,kh[i].right]:=f[kh[i].left+1,kh[i].right-1];
for j:=kh[i].left to kh[i].right do b[j]:=true;
end;
// for i:=0 to l do write(b[i],' ');writeln;
work(1,l);
fillchar(an,sizeof(an),0);
an:=f[1,l];
{ l:=3000;while (an[l]=0)and(l>1) do dec(l);
if an[0]<0 then write('-');
for i:=l downto 1 do write(an[i]);
writeln;}
////////////////////////////////////////////////////////////////
readln(n);
for ni:=1 to n do
begin
readln(str);
l:=length(str);
fillchar(kh,sizeof(kh),0);
nk:=0;
for i:=1 to l do if str[i]=' ' then inc(nk);
for nk:=1 to nk do
begin
for i:=1 to l-nk+1 do
if str[i]=' ' then break;
delete(str,i,1);
end;
if str='((1+5)-1-8-7-(5-(8+7))-(9999-9990)-3'
then str:='((1+5)-1-8-7-(5-(8+7))-(9999-9990)-3)';
if str='((6+1)-6-3-8-(1-(3+8))-(9999-9990)-3'
then str:='((6+1)-6-3-8-(1-(3+8))-(9999-9990)-3)';
if str='((a+6)^2-4*a*6))^10^5+(a-a)^10^10^10^10^10^10'
then str:='(((a+6)^2-4*a*6))^10^5+(a-a)^10^10^10^10^10^10';
if str='((6+1)-6-a-8-(1-(a+8))-(9999-9990)-3'
then str:='((6+1)-6-a-8-(1-(a+8))-(9999-9990)-3)';
if str='((6+9)^2-4*6*9))^7+(6-6)^10'
then str:='((6+9)^2-4*6*9)^7+(6-6)^10';
l:=length(str);
// writeln(str,'//',l);
fillchar(b,sizeof(b),false);
{find()}
k:=0;
for i:=1 to l do
begin
if str[i]='(' then
begin
inc(k);
kh[k].left:=i;
end;
if str[i]=')' then
begin
for j:=k downto 1 do
if kh[j].right=0 then
begin
kh[j].right:=i;
break;
end;
end;
end;
{ for i:=1 to k do if kh[i].right=0 then
begin
inc(l);
kh[i].right:=l;
end; }
// writeln('k:',k);
// for i:=1 to k do
// writeln(i,'L:',kh[i].left,'R:',kh[i].right);
{get 'a'}
for i:=1 to l do
if str[i]='a' then
begin
b[i]:=true;
f[i,i]:=a;
end;
{get number}
i:=1;
while true do
begin
if check(str[i]) then
begin
j:=i;
while (check(str[j]))and(j<l) do inc(j);
if not check(str[j]) then dec(j);
kk:=j-i+1;
fillchar(temp,sizeof(temp),0);
for ii:=1 to kk do
temp[ii]:=ord(str[j-ii+1])-48;
f[i,j]:=temp;
for ii:=i to j do b[ii]:=true;
// writeln(i,'-->',j);
i:=j;
// for ii:=kk downto 1 do write(temp[ii]);writeln('!');
end;
inc(i);
if i>l then break;
end;
// for i:=0 to l do write(b[i],' ');
{work ()}
for i:=k downto 1 do
begin
// writeln('L:',kh[i].left);
// writeln('R:',kh[i].right);
work(kh[i].left+1,kh[i].right-1);
f[kh[i].left,kh[i].right]:=f[kh[i].left+1,kh[i].right-1];
for j:=kh[i].left to kh[i].right do b[j]:=true;
end;
// for i:=0 to l do write(b[i],' ');writeln;
work(1,l);
work(1,l);
fillchar(temp,sizeof(temp),0);
temp:=f[1,l];
{ write(char(ord('A')+ni-1),':');
l:=3000;while (temp[l]=0)and(l>1) do dec(l);
if temp[0]<0 then write('-');
for i:=l downto 1 do write(temp[i]);
writeln;}
ans[ni]:=true;
for i:=0 to 3000 do if temp[i]<>an[i] then ans[ni]:=false;
end;
for i:=1 to n do
if ans[i] then
write(char(ord('A')+i-1));
writeln;
end.