BRACKET – SPOJ

July 15, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/BRACKET/

Thuật toán:

  • (đang cập nhập)

Code:

uses    math;
const   fi='';
        fo='';
        maxn=60+1;
var     f       :array[0..maxn,0..maxn,0..maxn] of int64;
        i,j,n,k :longint;
        s       :string;
        res,ans     :int64;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n,k);
        readln(s);
        close(input);
end;
function tinh(i,c,maxc:longint):int64;
var     sl      :int64;
begin
        if f[i,c,maxc]>-1 then exit(f[i,c,maxc]);
        if i>n then
                if (maxc=k) and (c=0) then
                        exit(1)
                else
                        exit(0);
        sl := 0;
        if c<k then sl := sl + tinh(i+1,c+1,max(maxc,c+1));
        if c>0 then sl := sl + tinh(i+1,c-1,max(maxc,c-1));
        f[i,c,maxc]:=sl;
        exit(sl);
end;
function lan(i,c,maxc:longint):longint;
begin
        if i>n then
                begin
                        inc(ans,1);
                        writeln(ans);
                        halt;
                end;
        if s[i]='(' then lan(i+1,c+1,max(maxc,c+1))
        else    ans := ans+ tinh(i+1,c+1,max(maxc,c+1));
        if s[i]=')' then lan(i+1,c-1,max(maxc,c-1));
end;
procedure process;
var     i,j,jj  :longint;
begin
assign(output,fo);rewrite(output);
        for i:=0 to n+1 do
                for j:=0 to k+1 do
                        for jj:=0 to k+1 do
                                f[i,j,jj]:=-1;
        res := tinh(1,0,0);
        writeln(res);
        ans := lan(1,0,0);
close(output);
end;
procedure print;
begin
end;
begin
        enter;
        process;
        print;
end.
Chủ đề: Đệ quy có nhớ

CATALAN – SPOJ

June 9, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/CATALAN/

Thuật toán:

  • Bài này sử dụng phương pháp đệ quy có nhớ. Bạn có thể đọc code để hiểu thêm

Code:

const
  fi='';
  fo='';
  maxn=21;
var
  f : array[1..2*maxn,0..2*maxn] of int64;
  i,j,n : longint;
  x,kq2 : array[1..2*maxn] of longint;
  res,kq1,k : int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to 2*n+1 do read(x[i]);
    readln(k);
    close(input);
  end;
function tinh(i,tr : longint) : int64;
  var sl : int64;
  begin
    if f[i,tr]>-1 then exit(f[i,tr]);
    if i>2*n+1 then
      if tr=0 then exit(1) else exit(0);
    sl := 0;
    sl := sl + tinh(i+1,tr+1);
    if tr>0 then
    sl := sl + tinh(i+1,tr-1);
    f[i,tr] := sl;
    exit(sl);
  end;
procedure truyvan1;
  begin
    kq1 := 0;
    for i:=2 to 2*n do
      if x[i]>x[i-1] then
        if x[i]-2>=0 then
          kq1 := kq1 + tinh(i+1,x[i]-2);
    inc(kq1);
  end;
procedure lankq(i : longint);
  begin
    if i>2*n then exit;
    if kq2[i-1]-1>=0 then
      begin
        if k>tinh(i+1,kq2[i-1]-1) then
          begin
            k:=k-tinh(i+1,kq2[i-1]-1);
            kq2[i] := kq2[i-1]+1;
            lankq(i+1);
            exit;
          end;
      end
      else
        begin
          kq2[i] := kq2[i-1]+1;
          lankq(i+1);
          exit;
        end;
    kq2[i] := kq2[i-1]-1;
    lankq(i+1);
  end;
procedure truyvan2;
  begin
    kq2[1] := 0;
    lankq(2);
  end;
procedure process;
  begin
    fillchar(f,sizeof(f),255);
    res := tinh(2,0);
    f[1,0] := res;
    truyvan1;
    truyvan2;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    //writeln(res);
    writeln(kq1);
    for i:=1 to 2*n+1 do write(kq2[i],' ');
    close(output);
  end;
begin
  enter;
  process;
  print;
end.
Chủ đề: Đệ quy có nhớ, Phương pháp, SPOJ

100827E – Codeforces

May 17, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Bài này sử dụng phương pháp đệ quy có nhớ
  • Bạn có thể đọc code bên dưới để hiểu rõ hơn

Code:

uses math;
const
  fi='';
  fo='';
  maxn=80;
var
  f : array[0..maxn,0..9,false..true,false..true,false..true] of int64;
  res : int64;
  i,j,n,tt,t : longint;
  ss : array[1..maxn] of longint;
  s,st : string;
function ok(s : string) : boolean;
  begin
    if s[1]<=s[2] then
      begin
        for i:=1 to length(s)-1 do if s[i]>s[i+1] then break;
        if (i=length(s)-1) then exit(true);
        for j:=i to length(s)-1 do
          if s[j+1]>s[j] then exit(false);
        exit(true);
      end
      else
      begin
        for i:=1 to length(s)-1 do if s[i]<s[i+1] then exit(false);
        {if (i=length(s)-1) then exit(true);
        for j:=i to length(s)-1 do
          if s[j+1]<s[j] then exit(false);  }
        exit(true);
      end;
  end;
function nhohon(x,y : string):boolean;
  begin
    while length(x)<length(Y) do x := '0'+x;
    while length(x)>length(y) do y:='0'+y;
    if x<y then exit(true) else exit(false);
  end;
function tinh(i,tr : longint; tangdan,nhohon,bigger0 : boolean) : int64;
  var j,last : longint;
      sl : int64;
  begin
    if f[i,tr,tangdan,nhohon,bigger0]>-1 then exit(f[i,tr,tangdan,nhohon,bigger0]);
    if i>n then
      if {nhohon and} bigger0 then exit(1) else exit(0);
    sl := 0;
    if nhohon then last := 9 else last := ss[i];
    if tangdan then
      begin
        for j:=tr to last do
          sl := sl + tinh( i+1,j,tangdan,(nhohon) or (j<ss[i]),(bigger0) or (j>0) );
        if bigger0 then
          for j:= min(tr-1,last) downto 0 do
            sl := sl + tinh(i+1,j,false,nhohon or (j<ss[i]),bigger0 or (j>0));
      end
      else
      begin
        for j:=min(last,tr) downto 0 do
          sl := sl + tinh(i+1,j,false,nhohon or (j<ss[i]),bigger0 or (j>0));
      end;
    f[i,tr,tangdan,nhohon,bigger0] := sl;
    exit(sl);
  end;
procedure process;
  var i : longint;
  begin
    n := length(s);
    //for i:=1 to n do ss[i] := ord(s[i])-ord('0');
    for i:=1 to n do ss[i] := ord(s[i])-48;
    fillchar(f,sizeof(f),255);
    res := tinh(1,0,true,false,false);
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(t);
  for tt:=1 to t  do
    begin
      readln(s);
      if not(ok(s)) then begin writeln(-1);continue; end;
      process;
      writeln(res);
    end;
  close(input);close(output);
end.
Chủ đề: Codeforces, Đệ quy có nhớ, OJ Mức độ:

DEMSO – SPOJ

May 5, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Bài này sử dụng phương pháp đệ quy có nhớ
  • (thuật toán đang cập nhập)

Bạn có thể đọc code để hiểu rõ hơn.

Code:

Pascal

const
  fi='';
  fo='';
  maxn=20;
var
  a,b,tg1,tg2 : int64;
  aa : array[1..maxn] of longint;
  i,j,n,k,d : longint;
  f : array[0..maxn,0..maxn,0..maxn,false..true,false..true] of int64;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure chuanbi(x : int64; var n : longint);
  var i,j : longint;
  begin
    n := 0;
    while x>0 do
      begin
        inc(n); aa[n] := x mod 10;
        x := x div 10;
      end;
    i:=1; j:=n;
    while (i<j) do
      begin
        swap(aa[i],aa[j]);
        inc(i);dec(j);
      end;
  end;
function tinh(i,tr,sl : longint; big0, small :boolean) : int64;
  var j,tg : longint;
      dem : int64;
  begin
    if f[i,tr,sl,big0,small] > -1 then exit(f[i,tr,sl,big0,small]);
    if i>n then
      if (sl<=k) and (small)  then exit(1) else exit(0);
    dem := 0;
    if not small then
      begin
        for j := 0 to aa[i] do
          begin
            if big0 then tg := sl + ord(abs(j-tr)<=d) else tg := 0;
            dem := dem + tinh(i+1,j,tg,big0 or (j>0),small or (j<aa[i]));
          end;
      end
      else
      begin
        for j := 0 to 9 do
          begin
            if big0 then tg := sl + ord(abs(j-tr)<=d) else tg := 0;
            dem := dem + tinh(i+1,j,tg,big0 or (j>0),small or (j<aa[i]));
          end;
      end;
    f[i,tr,sl,big0,small] := dem;
    exit(dem);
  end;
begin
  assign(input,fi);reset(input);
  assigN(output,fo);rewrite(output);
 
  readln(a,b,d,k);
 
  chuanbi(a, n);
 
  fillchar(f,sizeof(f),255);
  tg1 := tinh(1,0,0,false,false);
 
  chuanbI(b+1, n);
 
  fillchar(f,sizeof(f),255);
  tg2 := tinh(1,0,0,false,false);
 
  writeln(tg2-tg1);
 
  close(input);close(output);
end.

C++

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
 
long long l, r, D, K, n;
long long f[20][10][20][2][2];
int a[20];
 
bool check(long long x)
{
    bool ans = 1;
    int top = 0;
    int tmp = x;
    while (tmp){
        a[++top] = tmp % 10;
        tmp /= 10;
    }
    reverse(a + 1, a + top + 1);
    int dem = 0;
    FORE(i, 2, top) if (abs(a[i] - a[i - 1]) <= D) dem++;
    //if (x == 103) cout << dem<<" "<<k<<"??"<<endl;
    return (dem <= K);
}
 
long long trau()
{
    long long ans = 0;
    FORE(i, l, r) if (check(i)) ans++;
    cout << ans << endl;
    return 0;
}
long long duyet(int i, int dig, int worse, bool ok, bool greater0)
{
    if (i > n){
        return (worse <= K && greater0 > 0);
    }
    if (f[i][dig][worse][ok][greater0] > -1) return f[i][dig][worse][ok][greater0];
 
    long long ans = 0;
    if (i == 1){
        FORE(x, 0, a[i]) ans += duyet(i + 1, x, worse, ok | (x < a[i]), (x > 0));
    } else {
        int last = 9;
        if (ok == 0) last = a[i];
        int wnext;
        //if (i == 3) cout << last << "??"<<endl;
        FORE(x, 0, last) {
            if (greater0 == 0) wnext = worse; else wnext = worse + (abs(x - dig) <= D);
            //if (last == 3) cout << x<< ' '<<dig<<" "<<wnext<<endl;
            ans += duyet(i + 1, x, wnext, ok | (x < a[i]), greater0 | (x > 0));
        }
    }
    f[i][dig][worse][ok][greater0] = ans;
    return ans;
}
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("DEMSO.inp", "r", stdin);
    freopen("DEMSO.out", "w", stdout);
    #endif //MIKELHPDATKE
    cin >> l >> r >> D >> K;
    //trau();
 
    long long tmp = r, top = 0;
    while (tmp){
        a[++top] = tmp % 10;
        tmp /= 10;
    }
    reverse(a + 1, a + top + 1); n = top;
    memset(f, -1, sizeof(f));
 
    long long ans = duyet(1, 0, 0, 0, 0);
   // cout << ans << endl;
 
    tmp = l - 1, top = 0;
    while (tmp){
        a[++top] = tmp % 10;
        tmp /= 10;
    }
    reverse(a + 1, a + top + 1); n = top;
    memset(f, -1, sizeof(f));
    if (l - 1 == 0) cout << ans;
    else{
        ans -= duyet(1, 0, 0, 0, 0);
        cout << ans;
    }
    //cout<<check(103)<<endl;
    return 0;
}
Chủ đề: Đệ quy có nhớ, Phương pháp, SPOJ Mức độ: , , , ,

ADBRACK – SPOJ

February 9, 2016 by Leave a Comment

Đề 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.
Chủ đề: Đệ quy có nhớ, Phương pháp, SPOJ, Xử lý số lớn Mức độ: