BRACKET - Dãy ngoặc

Tác giả: RR

Ngôn ngữ: Pascal

const   fi='';
        fo='';
        maxn=61;
type    mang=array[0..maxn,-1..maxn] of int64;
var     f:text;
        n,k,i,j,l,t:longint;
        sl1,sl2:mang;
        s:string;
        res1,res2:int64;
procedure doc;
begin
  assign(f,fi);
  reset(f);
  readln(f,n,k);
  readln(f,s);
  close(f);
end;
function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;
procedure tinh(b:longint;var sl:mang);
var i,j:longint;
begin
  sl[0,0]:=1;
  for i:=1 to n do
    for j:=0 to b do
      sl[i,j]:=sl[i-1,j-1]+sl[i-1,j+1];
end;
procedure xuli1;
begin
  tinh(k,sl1);tinh(k-1,sl2);
  res1:=sl1[n,0]-sl2[n,0];
end;
procedure xuli2;
begin
  t:=0;
  for i:=1 to n do
    begin
      if s[i]='(' then inc(t) else dec(t);
      if s[i]=')' then res2:=res2+sl1[n-i,t+2];
    end;
  for i:=1 to n do
    begin
      if s[i]='(' then inc(t) else dec(t);
      if t=k then break;
      if s[i]=')' then res2:=res2-sl2[n-i,t+2];
    end;
end;
procedure ghi;
begin
  assign(f,fo);
  rewrite(f);
  writeln(f,res1);
  writeln(f,res2+1);
  close(f);
end;
begin
  doc;
  xuli1;
  xuli2;
  ghi;
end.

Download