Đề bài: http://vn.spoj.com/problems/ADBRACK/
Thuật toán
- Bài này sử dụng phương pháp đệ quy có nhớ kết hợp với thuật toán xử lý số lớn
- Các bạn có thể đọc code bên dưới để hiểu hơn
Code:
const fi=''; fo=''; maxn=100+3; var f :array[-maxn..maxn,-maxn..maxn] of ansistring; i,j,n,k :longint; st :ansistring; p :longint; res :ansistring; stack :array[1..maxn] of char; procedure enter; begin assign(input,fi);reset(input); readln(n,k); readln(st); close(input); end; procedure init; begin for i:=0 to n+1 do for j:=0 to n+1 do f[i,j]:='-1'; end; function cong (a,b: ansistring): ansistring; var nho,tam,i:longint; res :ansistring; begin while length(a)<length(b) do a:='0'+a; while length(b)<length(a) do b:='0'+b; nho:=0; res:=''; for i:=length(a) downto 1 do begin tam:=ord(a[i])+ord(b[i])-96+nho; nho:=tam div 10; tam:=tam mod 10; res:=chr(tam+48)+res; end; if nho>0 then res:='1'+res; exit(res); end; function tinh(i,c:longint):ansistring; var sl :ansistring; begin if f[i,c]<>'-1' then exit(f[i,c]); if i>n then if c=0 then begin f[i,c]:='1'; exit('1') end else begin f[i,c]:='0'; exit('0'); end; sl:= '0'; if c<k then begin stack[c+1]:='('; sl := cong( sl, tinh(i+1,c+1) ); stack[c+1]:='['; sl := cong( sl, tinh(i+1,c+1) ); stack[c+1]:='{'; sl := cong( sl, tinh(i+1,c+1) ); end; if c>0 then sl := cong( sl, tinh(i+1,c-1) ); f[i,c]:=sl; exit(sl); end; procedure timkq(i,c:longint); begin if i>n then begin res:=cong(res,'1'); writeln(res); halt; end; if st[i]='(' then begin stack[c+1]:='('; timkq(i+1,c+1); end else if c<k then begin stack[c+1]:='('; res:=cong(res, tinh(i+1,c+1)); end; if st[i]=')' then begin timkq(i+1,c-1); end else begin if c>0 then if stack[c]='(' then res:=cong(res,tinh(i+1,c-1)); end; if st[i]='[' then begin stack[c+1]:='['; timkq(i+1,c+1) ; end else if c<k then begin stack[c+1]:='['; res:=cong(res, tinh(i+1,c+1)); end; if st[i]=']' then begin timkq(i+1,c-1) ; end else begin if c>0 then if stack[c]='[' then res:=cong(res,tinh(i+1,c-1)); end; if st[i]='{' then begin stack[c+1]:='{'; timkq(i+1,c+1); end else if c<k then begin stack[c+1]:='{'; res:=cong(res,tinh(i+1,c+1)); end; if st[i]='}' then begin timkq(i+1,c-1); end else begin if c>0 then if stack[c]='{' then res:=cong(res,tinh(i+1,c-1)); end; end; procedure process; var tam:ansistring; begin assign(output,fo);rewrite(output); tam := tinh(1,0); res:='0'; stack:=''; timkq(1,0); close(output); end; begin enter; init; process; end. |
Speak Your Mind