Aida Nana

VOSMAXK – spoj

October 1, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

Code mình viết bên dưới rất dễ hiểu các bạn có thể tham khảo

Code:

const   inp='';
        out='';
        maxn=1000000;
var     a:array[1..maxn] of longint;
        n,k,i:longint;
        res,tmp,hold:int64;
begin
    assign(input,inp); reset(input);
    assign(output,out); rewrite(output);
    readln(n,k);
    for i:=1 to n do read(a[i]);

    res:=0; hold:=0;
    for i:=1 to n do
    begin
        if a[i]=k then
                begin
                        res:=res+(i-hold);
                        tmp:=i-hold;
                end
                else
        if a[i]>k then begin hold:=i; tmp:=0; end
        else res:=res+tmp;
    end;

    writeln(res);
    close(input); close(output);
end.

Chủ đề: SPOJ Mức độ: normal

VPBINDEG – spoj

October 1, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

(đang cập nhập)

Code:

{$H+}
program Revolutions_VPbindeg;
const
  fi = '';//Revolutions.inp';
  fo = '';//Revolutions.out';
  maxn = 10001;
var
  n : longint;
  s : string;
  T,k : longint;

procedure open;
begin
  assign(input,fi); reset(input);
  assign(output,fo); rewrite(output);
end;

procedure clo;
begin
  close(input);
  close(output);
end;

function calc(k : longint) : longint;
var
  i,s1,s0,kq : longint;
begin
  s1:=0; s0:=0; kq:=0;
  for i:=1 to n do if s[i]='1' then inc(s1);
  for i:=1 to n do
    if s[i]='0' then
      begin
        inc(s0);
        if (s0>=k) and (s1>=k) then inc(kq,s1-k+1);
      end
    else dec(s1);
  calc:=kq;
end;

procedure main;
var
  test : longint;
begin
  readln(T);
  for test:=1 to T do
    begin
      readln(n,k);
      readln(S);
      writeln(calc(k)-calc(k+1));
    end;
end;

BEGIN
  open;
  main;
  clo;
END.

Chủ đề: SPOJ

PETROLM – spoj

October 1, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

Đây là một bài QHĐ cơ bản suy nghĩ một chút sẽ ra
Các bạn hãy đọc code của mình sẽ hiểu ngay

Code:

uses math;
const
  fi='';//petrolm.inp';
  fo='';//petrolm.out';
  maxn=4000;
  oo=trunc(1e18);
type
  arr1 = array[1..maxn] of longint;
var
  tram,xe,csxe,cstram,kq : array[1..maxn] of longint;
  f : array[0..maxn,0..maxn] of int64;
  i,j,n,m : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to n do read(xe[i]);
    read(m);
    for i:=1 to m do read(tram[i]);
    close(input);
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint; var a,b : arr1);
  var i,j,x : longint;
  begin
    i:=l;j:=r;
    x:=a[(l+r) div 2];
    repeat
      while x>a[i] do inc(i);
      while xj;
    if il then qs(l,j,a,b);
  end;
procedure process;
  begin
    for i:=1 to n do csxe[i] := i;
    for i:=1 to m do cstram[i] := i;
    qs(1,n,xe,csxe);
    qs(1,m,tram,cstram);
    for i:=0 to n do
      for j:=0 to n do
        f[i,j] := oo;
    f[0,0] := 0;
    for i:=1 to n do f[i,i] := f[i-1,i-1] + abs(xe[i]-tram[i]);
    for j:=1 to m do
      for i:=j+1 to n do
        begin
          f[i,j] := min(f[i-1,j-1] + abs(xe[i]-tram[j]), f[i-1,j] + abs(xe[i]-tram[j]) );
          f[i,j] := f[i,j];
        end;
  end;
procedure print;
  begin
    assigN(output,fo);rewrite(output);
    writeln(f[n,m]);
    i:=n; j:= m;
    while (i>0) and (j>0) do
      begin
        if f[i,j]=f[i-1,j-1] + abs(xe[i]-tram[j]) then
          begin
            kq[csxe[i]] := cstram[j];
            dec(i);dec(j);
            continue;
          end;
        if f[i,j]=f[i-1,j] + abs(xe[i]-tram[j]) then
          begin
            kq[csxe[i]] := cstram[j];
            dec(i);
            continue;
          end;
      end;
    for i:=1 to n do write(kq[i],' ');
    close(output);
  end;
begin
  enter;
  process;
  print;
end.

Chủ đề: Quy hoạch động Mức độ: normal

QBPOINT – SPOJ

October 1, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

Duyệt n điểm, với mỗi điểm i ta:
- Duyệt các điểm j <> i rồi tính vector ij lưu lại vào 1 mảng ss[]
- Sort lại mảng ss[]
- 3 điểm i,j,k thẳng hàng nếu vector ij = vector ik

Code:

#include 
#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;
int n,x[2001],y[2001];
long long res;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("tripoint.inp", "r", stdin);
    freopen("tripoint.out", "w", stdout);
    #endif //
    cin>>n;
    FORE(i,1,n) cin>>x[i]>>y[i];
    FORE(i,1,n)
    {
        vector  ss; int cc=0;
        FORE(j,1,n)
        if (x[j]!=x[i])
            ss.push_back((double) (y[j]-y[i])/(x[j]-x[i]));
        else ++cc;
        sort(ss.begin(),ss.end());
        int sl=(cc-2)*(cc-1);
        if (ss.size())
        {
            int dem=1;
            FORE(j,1,ss.size()-1)
            if (ss[j]==ss[j-1]) ++dem;
            else
            {
                sl+=dem*(dem-1);
                dem=1;
            }
            sl+=dem*(dem-1);
        }
        res+=sl;
    }
    cout<

Chủ đề: Hình học, SPOJ Mức độ: basic, hinh hoc

BLGEN – spoj

October 1, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

(đang cập nhập)

Code:

uses math;
const   fi      ='';
        fo      ='';
        oo      =1000;
        maxc    =trunc(3e6);
var     n       :array[1..2] of longint;
        a       :array[1..2,1..1000] of qword;
        f       :array[0..oo,0..oo] of longint;
        mp      :longint;
        g       :array[1..maxc] of longint;
        nto     :Array[1..300000] of qword;
procedure nhap;
var     i :longint;
        k :longint;
        p :qword;
begin
        assign(input,fi);
        reset(input);
                k:=0;
                while not seekeof() do
                begin
                        inc(k);
                        while not seekeoln() do
                        begin
                                inc(n[k]);
                                read(p);
                                a[k,n[k]]:=p;
                        end;
                        readln;
                end;
        close(input);
end;
procedure sang;
var     i,j     :longint;
begin
        for i:=2 to trunc(sqrt(maxc)) do
        if g[i]=0 then
        begin
                j:=i*I;
                while j<=maxc do
                begin
                        g[j]:=i;
                        inc(j,i);
                end;
        end;
        for i:=2 to maxc do
        if g[i]=0 then
        begin
                inc(mp);
                nto[mp]:=i;
        end;
end;
function find(x:qword):boolean;
var     d,c,mid   :longint;
        t1,t2,t3      :qword;
begin
        d:=1; c:=mp;
        while d<=c do
        begin
                mid:=(d+c) div 2;
                t1:=x mod nto[mid];
                t2:=x div nto[mid];
                t3:=nto[mid]*nto[mid];
                if (t1=0) and (t2=t3) then exit(true);
                if (t3>t2) then c:=mid-1
                else d:=mid+1;
        end;
        exit(false);
end;
function kt(x:qword):boolean;
var     x1      :qword;
begin
        x1:=trunc(sqrt(x));
        if x1*x1=x then exit(true);
        if find(x) then exit(true);
        exit(false);
end;
procedure xuli;
var     i,j     :longint;
begin
        for i:=1 to n[1] do
        for j:=1 to n[2] do
        if (a[1,i]=a[2,j]) and kt(a[1,i]) then f[i,j]:=f[i-1,j-1]+1
        else f[i,j]:=max(f[i-1,j],f[i,j-1]);
end;
procedure xuat;
begin
        assign(output,fo);
        rewrite(output);
                writeln(f[n[1],n[2]]);
        close(Output);
end;
begin
        nhap;
        sang;
        xuli;
        xuat;
end.

Chủ đề: Tìm kiếm nhị phân Mức độ: normal, tknp

C11SEQ – spoj

September 27, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

Gọi S[i] là tổng từ a[1] đến a[i]
Ta biến đổi yêu cầu đề bài
- ```
L <= a[i] + a[i+1] + ... + a[j] <= R
```
- ```
=>    L<=s[i] - s[j-1]<=R
```
- => s[j-1]>=s[i]-r;
  
  s[j-1]<=s[i]-l;
Lưu các giá trị s[i] – r và s[i] – l và mảng kt 2*n ——> rời rạc hóa thành mảng b[1..2*n] ——> lưa vào cây BIT để tính:
```
ans := ans + get(b[i]) - get(b[n+i]);
```

Code:

const
  fi='';//c11seq.inp';
  fo='';//c11seq.out';
  maxn=trunc(1e5);
var
  s,sr,sl : array[0..maxn] of int64;
  a  : array[0..maxn*3] of int64;
  b,cs,t  : array[0..maxn*3] of longint;
  i,j,n,l,r : longint;
  ans : int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    read(n,l,r);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do if (l<=a[i]) and (r>=a[i]) then inc(ans);
    close(input);
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg := x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint);
  var i,j : longint;
      x : int64;
  begin
    i :=l;j:=r;
    x := a[cs[(l+r) div 2]];
    repeat
      while a[cs[i]]j;
    if il then qs(l,j);
  end;
procedure init;
  var i,hold : longint;
  begin
    for i := 1 to n do s[i] := s[i-1] + a[i];
    for i := 1 to n do sl[i] := s[i] - l;
    for i := 1 to n do sr[i] := s[i] - r - 1;
    for i := 1 to n do
      begin
        a[i] := sl[i];
        a[n+i] := sr[i];
        a[n+n+i] := s[i-1];
      end;
    //a[2*n+1] := s[0] - l;
    //a[2*n+2] := s[0] - r;
    for i:=1 to 3*n do cs[i] := i;
    qs(1,3*n);
    b[cs[1]] := 1; hold := 1;
    for i:=2 to n*3 do
      if a[cs[i]] = a[cs[i-1]] then
        begin
          b[cs[i]] := hold;
        end
        else
        begin
          inc(hold);
          b[cs[i]] := hold;
        end;
  end;
procedure update(i : longint);
  begin
    while i<=3*n do
      begin
        t[i] := t[i] + 1;
        i := i + i and (-i);
      end;
  end;
function get(i : longint) : longint;
  begin
    get := 0;
    while i>0 do
      begin
        get := get + t[i];
        i := i - i and (-i);
      end;
  end;
procedure process;
  var i : longint;
  begin
    for i:=1 to n do
      begin
        ans := ans + get(b[i]) - get(b[n+i]);
        update(b[2*n+i]);
      end;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(Output);
    writeln(ans);
    close(output);
  end;
begin
  enter;
  init;
  process;
  print;
end.

Chủ đề: BIT, Nén số (rời rạc hóa mảng) Mức độ: hard

VDANGER – spoj

September 27, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

Gợi ý là sử dụng thuật toán Floyd rồi cộng lại ra kết quả bài toán

Code:

VAR
  a :array[1..10000] of byte;
  c :array[1..100,1..100] of longint;
  t :array[1..100,1..100] of byte;
  n :byte;
  m :word;

procedure Enter;
  var i,j :word;
  begin
    readln(n,m);
    for i:=1 to m do readln(a[i]);
    for i:=1 to n do
      begin
        for j:=1 to n do
          begin
            read(c[i,j]); t[i,j]:=j;
          end;
        readln;
      end;
  end;

procedure Optimize;
  var i,j,k :byte;
  begin
    for k:=1 to n do
    for i:=1 to n do
    for j:=1 to n do
    if (c[i,j]>c[i,k]+c[k,j]) then
      begin
        c[i,j]:=c[i,k]+c[k,j];
        t[i,j]:=t[i,k];
      end;
  end;

procedure Quit;
  var
    i :word;
    sum :longint;
  begin
    sum:=0;
    if (a[1]<>1) then sum:=sum+c[1,a[1]];
    for i:=2 to m do sum:=sum+c[a[i-1],a[i]];
    if (a[m]<>n) then sum:=sum+c[a[m],n];
    write(sum);
  end;

BEGIN
  assign(input,''); reset(input);
  assign(output,''); rewrite(output);
  Enter;
  Optimize;
  Quit;
  close(input); close(output);
END.

Chủ đề: Floyd Mức độ: normal

COUNTPL – spoj

September 27, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

Tính trước mảng pan[i][j] = true nếu xâu s[i..j] là palindrome và ngược lại
Gọi f[i][j]=true nếu xâu s[1..i] có thể chia làm j xâu palindrome và ngược lại
Code đoạn tính f[i][j] cho các bạn dễ hiểu:

        f[0,0] := true;
        res := oo;
        for i:=1 to n do
                for j:=1 to i do
                        begin
                                for k:=i downto 1 do
                                        begin
                                                if pan[k,i] then
                                                        if f[k-1,j-1] then
                                                                f[i,j] :=true;
                                        end;
                                if i=n then if f[i,j] then res := min(res,j);
                        end;

Code:

uses    math;
const   fi='';
        fo='';
        maxn=300;
        oo=1000;
var     pan     :array[1..maxn,1..maxn] of boolean;
        i,j,n   :longint;
        s       :string;
        f       :array[0..maxn,0..maxn] of boolean;
        res     :longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(s);
        close(input);
end;
function check(i,j      :longint):boolean;
var     tg      :string;
begin
        tg := copy(s,i,j-i+1);
        for i :=1 to length(tg) div 2 do
                if tg[i]<>tg[length(tg)-i+1] then exit(false);
        exit(true);
end;
procedure process;
var     i,j,k   :longint;
begin
        n := length(s);
        for i:=1 to n do
                for j:=i to n do
                        if check(i,j) then pan[i,j] := true;
        f[0,0] := true;
        res := oo;
        for i:=1 to n do
                for j:=1 to i do
                        begin
                                for k:=i downto 1 do
                                        begin
                                                if pan[k,i] then
                                                        if f[k-1,j-1] then
                                                                f[i,j] :=true;
                                        end;
                                if i=n then if f[i,j] then res := min(res,j);
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

Chủ đề: Quy hoạch động Mức độ: normal

ROBOCON – vn.spoj.com

September 27, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

Bạn loang con robot 1 trong khi loang robot 1 bạn cũng đồng thời loang robot 2. Ta phải suy luận ra một số trường hợp để mà dừng loang
Bạn có thể đọc code của mình để hiểu thêm. Mình viết rất dễ hiểu, bạn đọc có thể hiểu ngay

Code:

const
  fi='';
  fo='';
  maxn=501;
  maxq=20*maxn*maxn;
  oo=trunc(1e9);
type
  point = record
    x,y,d : longint;
  end;
var
  dau1,cuoi1,dau2,cuoi2,i,j,n,m : longint;
  a : array[0..maxn,0..maxn] of boolean;
  q1,q2 : array[1..maxq] of point;
  d1,d2 : array[1..maxn,1..maxn] of longint;
  nowd,res : longint;
  kt : boolean;

procedure enter;
var u,v : longint;
begin
  assign(input,fi);reset(input);
  fillchar(a , sizeof(a) , false);
  readln(n,m);
  for i:=1 to n do for j:=1 to n do a[i,j] := true;
  for i:=1 to m do
    begin
      read(u,v);
      a[u,v] := false;
    end;
end;
procedure push1(x,y,z : longint);
begin
  inc(cuoi1);
  q1[cuoi1].x := x;
  q1[cuoi1].y := y;
  q1[cuoi1].d := z;
  d1[x,y] := z;
  if d2[x,y]=z then
    begin
      res := z;
      kt:=true;
      exit;
    end;
end;
procedure push2(x,y,z : longint);
begin
  inc(cuoi2);
  q2[cuoi2].x := x;
  q2[cuoi2].y := y;
  q2[cuoi2].d := z;
  d2[x,y] := z;
end;
procedure bfs2(dd : longint);
var u : point;
    i,j : longint;
begin
  while dau2<=cuoi2 do
    begin
      u := q2[dau2]; inc(dau2);
      if u.d>dd then begin dec(dau2); exit; end;
      i:=u.x;j:=u.y;
      if a[i,j-1] and (d2[i,j-1]<>dd+1) then push2(i,j-1,dd+1);
      if a[i+1,j] and (d2[i+1,j]<>dd+1) then push2(i+1,j,dd+1);
      if a[i+1,j-1] and (d2[i+1,j-1]<>dd+1) then push2(i+1,j-1,dd+1);
    end;
end;
procedure bfs1;
var u : point;
    i,j : longint;
begin
  fillchar(d1,sizeof(d1),255);
  fillchar(d2,sizeof(d2),255);
  kt := false;
  dau1 :=1; cuoi1 := 0;
  dau2 := 1; cuoi2 := 0;
  push1(1,1,0); push2(1,n,0);
  nowd := 0;
  while dau1<=cuoi1 do
    begin
      if kt then break;
      u := q1[dau1]; inc(dau1);
      if u.d=nowd then
        begin
          bfs2(nowd);
          inc(nowd);
        end;
      i := u.x ; j:=u.y;
      if a[i+1,j] and (d1[i+1,j]<>u.d+1) then push1(i+1,j,u.d+1);
      if a[i,j+1] and (d1[i,j+1]<>u.d+1) then push1(i,j+1,u.d+1);
      if a[i+1,j+1] and (d1[i+1,j+1]<>u.d+1) then push1(i+1,j+1,u.d+1);
    end;
end;
procedure process;
begin
  res := oo;
  bfs1;
end;
procedure print;
begin
  assign(output,fo);rewrite(output);
  writeln(res);
  close(output);
end;
begin
  enter;
  process;
  print;
end.

Chủ đề: BFS Mức độ: hard, hsgqg

MATCH1 – SPOJ

September 27, 2016 by Aida Nana Leave a Comment

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

Thuật toán:

Đây là bài cơ bản cho thuật toán Cặp ghép
Bạn có thể tham khảo tài liệu cực hay và dễ hiểu về thuật toán này tại: http://yeulaptrinh.de/150/tong-hop-tai-lieu-ve-thuat-toan-cap-ghep/

Code:

const
  fi='';
  fo='';
  maxn=100;
var
  a : array[1..maxn,1..maxn] of boolean;
  match : array[1..maxn] of longint;
  i,j,n,m,res : longint;
procedure enter;
  var u,v : longint;
  begin
    assign(input,fi);reset(input);
    readln(n,m);
    while not eof(input) do
      begin
        readln(u,v);
        a[u,v] := true;
      end;
  end;
procedure process;
  var found : boolean;
      nlist,i,j,old : longint;
      list : array[1..maxn] of longint;
      cx : array[1..maxn] of boolean;
  procedure dfs(u : longint);
    var i,v : longint;
    begin
      for v:=1 to m do
        if a[u,v] then
          if cx[v] then
          begin
            cx[v] := false;
            if match[v]=0 then found := true else dfs(match[v]);
            if found then
              begin
                match[v] := u;
                exit;
              end;
          end;
    end;
  begin
    nlist := n;
    for i:=1 to n do list[i ] := i;
    repeat
      old := nlist;
      fillchar(cx,sizeof(cx),true);
      for i:=nlist downto 1 do
        begin
          found := false;
          dfs(list[i]);
          if found then
            begin
              list[i] := list[nlist];
              dec(nlist);
            end;
        end;
    until old = nlist;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    for i:=1 to m do if match[i]<>0 then inc(res);
    writeln(res);
    for i:=1 to m do if match[i]<>0 then writeln(match[i],' ',i);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.

Chủ đề: Cặp ghép Mức độ: cap ghep, co ban

VOSMAXK – spoj

VPBINDEG – spoj

PETROLM – spoj

QBPOINT – SPOJ

BLGEN – spoj

C11SEQ – spoj

VDANGER – spoj

COUNTPL – spoj

ROBOCON – vn.spoj.com

MATCH1 – SPOJ

Recent Posts

Recent Comments

Archives

Categories

Meta