Why I got WA?
Posted by
qwt 11 May 2002 13:59
const
maxn=100;
var
a:array[1..maxn,1..maxn] of integer;
fa:array[1..maxn,1..maxn] of integer;
s:string[maxn];
p,q,i,j,k:integer;
procedure sub(x,y:integer);
begin
case fa[x,y] of
-1:begin
write('(');
if x+1<=y-1 then sub(x+1,y-1);
write(')');
end;
-2:begin
write('(');
if x+1<=y then sub(x+1,y);
write('(');
end;
-3:begin
write('[');
if x+y<=y-1 then sub(x+1,y-1);
write(']');
end;
-4:begin
write('[');
if x+1<=y then sub(x+1,y);
write(']');
end;
-5:begin
write('(');
if x<=y-1 then sub(x,y-1);
write(')');
end;
-6:begin
write('[');
if x<=y-1 then sub(x,y-1);
write(']');
end;
0:begin
if (s[x]='(')or(s[x]=')') then write('()') else write('[]');
end;
else begin
sub(x,fa[x,y]);sub(fa[x,y]+1,y);
end;
end;
end;
begin
fillchar(a,sizeof(a),0);
fillchar(fa,sizeof(fa),0);
readln(s);
for p:=1 to length(S) do
for q:=1 to length(S)-p+1 do begin
i:=q;j:=q+p-1;
if i=j then begin
a[i,i]:=1;
end else begin
a[i,j]:=maxint;
for k:=i to j-1 do
if a[i,k]+a[k+1,j]<a[i,j] then begin
a[i,j]:=a[i,k]+a[k+1,j];
fa[i,j]:=k;
end;
if (s[i]='(')and(s[j]=')') then begin
if a[i+1,j-1]<a[i,j] then begin
a[i,j]:=a[i+1,j-1];
fa[i,j]:=-1;
end
end else
if (s[i]='(') then begin
if a[i+1,j]+1<a[i,j] then begin
a[i,j]:=a[i+1,j]+1;
fa[i,j]:=-2;
end;
end else
if (s[i]='[')and(s[j]=']') then begin
if a[i+1,j-1]<a[i,j] then begin
a[i,j]:=a[i+1,j-1];
fa[i,j]:=-3;
end
end else
if (s[i]='[') then begin
if a[i+1,j]+1<a[i,j] then begin
a[i,j]:=a[i+1,j]+1;
fa[i,j]:=-4;
end;
end else
if s[j]=')' then begin
if a[i,j-1]+1<a[i,j] then begin
a[i,j]:=a[i,j-1]+1;
fa[i,j]:=-5;
end;
end else
if s[j]=']' then begin
if a[i,j-1]+1<a[i,j] then begin
a[i,j]:=a[i,j-1]+1;
fa[i,j]:=-6;
end;
end;
end;
end;
sub(i,j);
writeln;
end.