PALINY – spoj

January 5, 2017 by Leave a Comment

Đề bài:

Thuật toán:

Chặt nhị phần + Hash

Code:

{$H+}
uses math;
const
  fi='';//paliny.inp';
  fo='';//paliny.out';
  maxn=50003;
  pp=307;
  base=trunc(1e9)+7;
var
  i,j,n,d,c,g,top,ans : longint;
  ha,hb,pow : array[0..maxn] of int64;
  a : array[1..maxn] of longint;
  s : string;
function gethash1(l,r : longint) : int64;
  begin
    gethash1 := (ha[r] - ha[l-1] * pow[r-l+1] + base * base) mod base;
  end;
function gethash2(l,r : longint) : int64;
  begin
    gethash2 := (hb[r] - hb[l+1] * pow[l-r+1] + base * base) mod base;
  end;
function ok ( le : longint) : boolean;
  var i,j : longint;
  begin
    for i := 1 to n - le + 1 do
      if gethash1(i,i+le-1) = gethash2(i+le-1,i) then exit(true);
    exit(false);
  end;
procedure process;
  begin
  d := 1 ;
  c := top ;
  g := (d+c) div 2;
  while (G<>d) and (g<>C) do
    begin
      if ok (a[g]) then d := g else c := g;
      g := (d+c) div 2;
    end;
  for g := c downto d do
    if ok (a[g]) then
      begin
        ans := max(ans,a[g]);
        exit;
      end;
  end;
procedure push(x : longint);
  begin
    inc(top);
    a[top] := x;
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(n);
  readln(s);
  pow[0] := 1;
  for i := 1 to n do pow[i] := pow[i-1] * pp mod base;
  for i := 1 to n do ha[i] := ( ha[i-1] * pp + ord(s[i]) ) mod base;
  for i := n downto 1 do hb[i] := ( hb[i+1] * pp + ord(s[i]) ) mod base;
  top := 0;
  for i := 1 to n do
    if i mod 2 = 0 then push(i);
  process;
  top := 0;
  for i := 1 to n do
    if i mod 2 = 1 then push(i);
  process;
  writeln(ans);
  close(input);close(output);
end.
Chủ đề: Hashing, Tìm kiếm nhị phân

NKSGAME – spoj

December 24, 2016 by Leave a Comment

Đề bài:

Thuật toán:

Bài yêu cầu với mỗi số \(b[i]\) tìm \(c[j]\) sao cho \(|b[i]+c[j]|\) nhỏ nhất. Suy ra chọn sao cho \(b[i]+c[j]\) có giá trị gần \(0\) nhất

Thuật toán sẽ là:

  1. Sắp xếp lại mảng \(c[]\).
  2. Với mỗi \(b[i]\) tìm kiếm nhị phân \(c[j]\) thỏa mãn \(b[i]+c[j]\) có giá trị gần \(0\) nhất.

Nếu chưa hiểu rõ bạn có thể xem code bên dưới.

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 100009;
const int oo = 2000000009;
int i, j, n, ans, tmp, b[maxn], a[maxn];
 
bool cmp (int x, int y) {
     return(x < y);
}
 
int main() {
    cin >> n;
    for (i = 1; i <= n; i++) cin >> a[i];
    for (i = 1; i <= n; i++) cin >> b[i];
    sort (b+1, b+n+1, cmp);
    ans = oo;
    for (i = 1; i <= n; i++) {
        tmp = lower_bound(b+1,b+n+1,0-a[i]) - b;
        if (tmp > n) tmp = n;
        ans = min(ans, abs(a[i] + b[tmp]));
        if (tmp == 1) continue;
        ans = min(ans, abs(a[i] + b[tmp-1]));
    }
    cout << ans;
    return 0;
}
Chủ đề: SPOJ, Tìm kiếm nhị phân Mức độ:

NKJUMP – spoj

October 30, 2016 by Leave a Comment

Đề bài: [xem đề bài]

Thuật toán:

  • Nhận thấy một vòng bất kỳ chỉ có thể nhảy đến vòng có số lớn hơn. Ta nghĩ đến sử dụng phương pháp Quy hoạch động để giải.
  • Ban đầu sắp xếp lại mảng A.
  • Gọi F[i] là số bước lớn nhất để nhảy đến ô thứ i.
  • F[i] = max(F[j]+1, F[i]) với i=1..n, j=1..i-1 và tồn tại k sao cho a[k]+a[j]=a[i].
  • Kiểm tra xem có tồn tại k bằng cách sử dụng tìm kiếm nhị phân

Code:

C++ (xem code trên ideone)

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 1009;
int i, j, n, a[maxn], b[maxn], f[maxn];
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    int tmp, ans = 0;
    for (int i = 1; i <= n; i++) f[i] = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            bool tmp = binary_search(a+1,a+j,a[i] - a[j]);
            if (tmp == 1) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

Pascal (xem code trên ideone)

uses    math;
const   fi='';
        fo='';
        maxn=1000;
type    arra=array[1..maxn] of longint;
var     f:text;
        a,l:arra;
        i,j,n:integer;
        tmp2:longint;
        res:longint;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n);
    for i:=1 to n do
    begin
        read(f,a[i]);
    end;
    close(f);
end;
procedure sort;
var     w:longint;
begin
    for i:=1 to n do
        for j:=i+1 to n do
        if a[i]>a[j] then
        begin
            w:=a[i];
            a[i]:=a[j];
            a[j]:=w;
        end;
end;
procedure init;
begin
    res:=0;
    for i:=1 to n do l[i]:=1;
end;
function kt(x,k:longint):boolean;
var     d,c,g,ii:longint;
begin
    d:=1; c:=k;
    kt:=false;
    while d<=c do
    begin
        g:=(d+c) div 2;
        if a[g]=x then begin tmp2:=g; exit(true); end;
        if a[g]<x then d:=g+1 else c:=g-1;
    end;
end;
function max3(x,y,z:longint):longint;
begin
    max3:=x;
    if y>max3 then max3:=y;
    if z>max3 then max3:=z;
end;
procedure xuly;
var     tmp:longint;
begin
    for i:=1 to n do
    begin
        tmp:=a[i];
        for j:=i-1 downto 1 do
        begin
            if a[j]>=tmp div 2 then
                begin
                   if kt(tmp-a[j],j-1) then
                        begin
                        l[i]:=max3(l[i],l[j]+1,l[tmp2]+1);
                        if l[i]>res then res:=l[i];
                        end;
                end
            else break;
        end;
    end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    sort;
    init;
    xuly;
    xuat;
end.
Chủ đề: Quy hoạch động, Tìm kiếm nhị phân Mức độ:

BLGEN – spoj

October 1, 2016 by 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 độ: ,

SPSEQ – SPOJ

July 21, 2016 by Leave a Comment

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

Thuật toán:

  • Gọi f1[i] là độ dài dãy con không giảm dài nhất kết thúc là a[i] của dãy a[1..i]
  • Gọi f2[i] là độ dài dãy con không tăng dài nhất bắt đầu là a[i] của dãy a[i..n]
  • Kết quả bài toán là:
    <span class="nu0">2</span>*min<span class="br0">(</span>f1<span class="br0">[</span>i<span class="br0">]</span>,f2<span class="br0">[</span>i<span class="br0">]</span><span class="br0">)</span> -<span class="nu0">1   với i=1..n;</span>

Code:

uses    math;
const   fi='';
        fo='';
        maxn=trunc(1e5)+3;
        oo=trunc(1e9)+7;
var     a:array[0..maxn] of longint;
        b1,b2:array[0..maxn] of longint;
        f1,f2:array[0..maxn] of longint;
        i,j,n,m,res:longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        for i:=1 to n do read(a[i]);
        close(input);
end;
function tim1(r,x:longint):longint;
var     d,c,g:longint;
begin
        d:=0;c:=r;
        g:=(d+C) div 2;
        while (g<>d) and (g<>c) do
                begin
                        if b1[g]>=x then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
        for g:=c downto d do
                begin
                        if b1[g]<x then exit(g);
                end;
        exit(0);
end;
function tim2(r,x:longint):longint;
var     d,c,g:longint;
begin
        d:=0;c:=r;
        g:=(d+c) div 2;
        while (g<>d) and (g<>c) do
                begin
                        if b2[g]>=x then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
        for g:=c downto d do
                if b2[g]<x then exit(g);
        exit(0);
end;
procedure process;
var     tam1,tam2:longint;
        res1,res2:longint;
begin
        res1:=1;
        b1[0]:=-oo;
        b1[1]:=a[1];
        f1[1]:=1;
        for i:=2 to n do
                begin
 
                        tam1:=tim1(res1,a[i]);
                        if tam1+1>res1 then
                                begin
                                        inc(res1);
                                        b1[res1]:=a[i];
                                end else
                        if b1[tam1+1]>a[i] then b1[tam1+1]:=a[i];
                        f1[i]:=tam1+1;
                end;
        res2:=1;
        b2[0]:=-oo;
        f2[n]:=1;
        b2[1]:=a[n];
        for i:=n-1 downto 1 do
                begin
                        tam2:=tim2(res2,a[i]);
                        if tam2+1>res2 then
                                begin
                                        inc(res2);
                                        b2[res2]:=a[i];
                                end else
                                if b2[tam2+1]>a[i] then b2[tam2+1]:=a[i];
                        f2[i]:=tam2+1;
                end;
        res:=0;
        for i:=1 to n do
                res:=max( res, 2*min(f1[i],f2[i]) -1 );
end;
procedure print;
begin
        assign(output,fo);rewrite(Output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.
Chủ đề: SPOJ, Tìm kiếm nhị phân

QBROBOT – SPOJ

June 10, 2016 by Leave a Comment

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

Thuật toán:

  • Tìm đường đi ngắn nhất bằng Dijkstra
  • Chắt nhị phân giá trị w
  • Với mỗi giá trị w kiểm tra xem có thỏa mãn không

Code:

#include <iostream>
#include <cmath>
#include <fstream>
#include <bits/stdc++.h>
#define MAXN 502
#define MAXM 30002
#define VC 2000000000
int n, m, dau[MAXM], cuoi[MAXM], t[MAXM], c[MAXM], x[MAXN];
long tro[MAXN];
int ke[2*MAXM];
int qn, q[MAXN], vt[MAXN];
long kc[MAXN], nl[MAXN], ds;
int prev[MAXN];
int tt[MAXN], sl=0;
using namespace std;
int doc()
{
    int i;
    cin >> n;
    for (i=1; i<=n; i++) cin >> x[i];
    cin >> m;
    for (i=1; i<=m; i++) cin >> dau[i] >> cuoi[i] >> t[i] >> c[i];
}
 
// Ham dung do thi
int dungdt()
{
    long u,v;
    int i;
    for (i=1; i<=m; i++) {tro[dau[i]]++; tro[cuoi[i]]++;}
    for (v=0,i=1; i<=n; i++) {u=tro[i]; tro[i]=v+1; v+=u;}
    tro[n+1]=v+1;
    for (i=1; i<=m; i++) {ke[tro[dau[i]]++]=i; ke[tro[cuoi[i]]++]=i;}
    for (i=n; i>=2; i--) tro[i]=tro[i-1]; tro[1]=1;
}
 
// Cac ham quan ly hang doi uu tien
int up(int k)
{
    int v=q[k];
    while (kc[q[k/2]]>kc[v])
    {
        q[k]=q[k/2];
        vt[q[k]]=k;
        k/=2;
    }
    q[k]=v;
    vt[q[k]]=k;
}
int down(int k)
{
    int v=q[k];
    while (2*k<=qn)
    {
        int l=2*k;
        if ((l<qn) && (kc[q[l+1]]<kc[q[l]])) l++;
        if (kc[q[l]]>=kc[v]) break;
        q[k]=q[l];
        vt[q[k]]=k;
        k=l;
    }
    q[k]=v;
    vt[q[k]]=k;
}
int initq() {qn=0; vt[0]=0; kc[0]=-1;}
int put(int u) {q[++qn]=u; vt[u]=qn; up(qn);}
int get() {int kq=q[1]; q[1]=q[qn--]; vt[q[1]]=1; down(1); return kq;}
int update(int u) {int k=vt[u]; up(k);}
int qempty() {return (qn==0);}
 
// Ham dijstra tim khoang cach ngan nhat
int dijstra()
{
    initq();
    kc[1]=0; prev[1]=-(n+1);
    put(1);
    while (!qempty())
    {
        int u=get(); prev[u]=-prev[u];
        tt[++sl]=u;
        for (long i=tro[u]; i<tro[u+1]; i++)
        {
            int v;
            if (dau[ke[i]]!=u) v=dau[ke[i]]; else v=cuoi[ke[i]];
            if ((prev[v]<0) && (kc[v]>kc[u]+t[ke[i]]))
            {
                kc[v]=kc[u]+t[ke[i]];
                prev[v]=-u;
                update(v);
            }
            if (prev[v]==0)
            {
                kc[v]=kc[u]+t[ke[i]];
                prev[v]=-u;
                put(v);
            }
        }
    }
    return 0;
}
 
 
// Ham kiem tra co di duoc hay khong
int diduoc(long w)
{
    long i,k,u,v,tg,cp,cl;
    for (i=1; i<=n; i++) nl[i]=-VC;
    nl[1]=w;
    for (k=1; k<=sl; k++)
    {
        u=tt[k];
        if (nl[u]>=0)
        for (i=tro[u]; i<tro[u+1]; i++)
        {
            if (dau[ke[i]]!=u) v=dau[ke[i]]; else v=cuoi[ke[i]];
            tg=t[ke[i]]; cp=c[ke[i]];
            if ((kc[v]==kc[u]+tg) && (nl[u]>=cp))
            {
                cl=(x[v]==1) ? w : nl[u]-cp;
                if (cl>nl[v]) nl[v]=cl;
            }
        }
    }
    return (nl[n]>=0);
}
 
// Ham tim chi phi be nhat (dua vao theo tim kiem nhi phan)
int solve()
{
    long first=0, last=1, lim;
    while (!diduoc(last)) {first=last; last*=2;}
    while (last-first>1)
    {
        lim=(last+first)/2;
        if (diduoc(lim)) last=lim; else first=lim;
    }
    ds=last;
}
 
// Ham in ket qua
int viet()
{
    cout << ds;
    //<< // '\n';
    /*out << kc[n] << '\n';
    for (long i=tro[1]; i<tro[2]; i++)
    {
        int v;
        if (dau[ke[i]]!=1) v=dau[ke[i]]; else v=cuoi[ke[i]];
        if (v==n) out << t[ke[i]] << ' ' << c[ke[i]] << '\n';
    } */
    }
 
// CHUONG TRINH CHINH
int main()
{
    doc();
    dungdt();
    dijstra();
    solve();
    viet();
}
Chủ đề: Dijkstra, SPOJ, Tìm kiếm nhị phân Mức độ: ,

MINCUT – SPOJ

June 4, 2016 by Leave a Comment

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

Thuật toán:

  • Với mỗi cách cắt ngang, cắt dọc. Ta chặt nhị phân tìm nhát cắt sao cho độ chênh lệch 2 phần nhỏ nhất.
  • Chú ý với mỗi cách cắt ta phải chặt nhị phân 2 lần: value >= trunggian và value <= trunggian
  • Các bạn có thể đọc code để hiểu rõ hơn

Code:

uses    math;
const   fi='';
        fo='';
        maxn=trunc(1e3)+3;
        oo=trunc(1e15);
type    data=record
                x,y,u,v:longint;
                end;
var     m,n,i,j,k:longint;
        s:array[0..maxn,0..maxn] of int64;
        a:array[1..maxn,1..maxn] of longint;
        q:array[1..maxn*maxn] of data;
        res     :int64;
procedure nhap;
begin
    assign(input,fi);reset(input);
    readln(m,n,k);
    for i:=1 to m do
        for j:=1 to n do read(a[i,j]);
    for i:=1 to k do
        with q[i] do
                read(x,y,u,v);
    close(input);
end;
procedure init;
begin
    for i:=1 to m do
        for j:=1 to n do s[i,j]:=s[i-1,j]+s[i,j-1]-s[i-1,j-1]+a[i,j];
end;
function tinh(x,y,u,v:longint):int64;
begin
        exit(s[u,v]+s[x-1,y-1]-s[x-1,v]-s[u,y-1]);
end;
procedure solve;
var     tam,tam2        :int64;
        d,c,g   :longint;
begin
assign(output,fo);rewrite(output);
    for i:=1 to k do
      with q[i] do
        begin
            tam:=tinh(x,y,u,v);
            tam2 := tam div 2;
            res := oo;
            // cat hang
            d :=x; c:=u-1;
            g := (d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,g,v)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=c downto d do
                if tinh(x,y,g,v)<=tam2 then
                        begin
                                res := min(res,tam-2*tinh(x,y,g,v));
                        end;
            d:=x; c:=u-1;
            g:=(d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,g,v)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=d to c do
                if tinh(x,y,g,v)>=tam2 then
                        begin
                                res := min(res,2*tinh(x,y,g,v)-tam);
                        end;
            // cat cot;
            d:=y; c:=v-1;
            g:=(d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,u,g)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=c downto d do
                if tinh(x,y,u,g)<=tam2 then
                        begin
                                res := min(res,tam-2*tinh(x,y,u,g));
                        end;
            d:=y; c:=v-1;
            g:=(d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,u,g)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=d to c do
                if tinh(x,y,u,g)>=tam2 then
                        begin
                                res := min(res,2*tinh(x,y,u,g)-tam);
                        end;
            writeln(res);
        end;
end;
begin
    nhap;
    init;
    solve;
end.
Chủ đề: SPOJ, Tìm kiếm nhị phân Mức độ:

MDOLLS – SPOJ

May 23, 2016 by Leave a Comment

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

Thuật toán:

  • Sắp xếp tăng dần theo h[], nếu h[] bằng nhau thì xếp giảm dần theo w[]
  • Kết quả bài toán khi đó là độ dài dãy con tăng dài nhất của dãy w[n..1]

Code:

const   fi='';
        fo='';
        maxn=20003;
        oo=trunc(1e9);
var     w,h     :array[0..maxn] of longint;
        a,b     :array[0..maxn] of longint;
        i,j,n   :longint;
        res     :longint;
        t,tt    :longint;
procedure enter;
begin
        fillchar(a,sizeof(a),0);
        fillchar(b,sizeof(b),0);
        fillchar(w,sizeof(w),0);
        fillchar(h,sizeof(h),0);
        read(n);
        for i:=1 to n do read(w[i],h[i]);
end;
procedure swap(var x,y:longint);
var     tg      :longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint);
var     x,y,i,j :longint;
begin
        i:=l;j:=r;
        x:=h[(l+r) div 2];
        y:=w[(l+r) div 2];
        repeat
                while (x>h[i]) or ((x=h[i]) and (y<w[i])) do inc(i);
                while (x<h[j]) or ((x=h[j]) and (y>w[j])) do dec(j);
                if i<=j then
                        begin
                                swap(h[i],h[j]);
                                swap(w[i],w[j]);
                                inc(i);dec(j);
                        end;
        until i>j;
        if i<r then qs(i,r);
        if j>l then qs(l,j);
end;
function tim(r,x:longint):longint;
var     d,c,g   :longint;
begin
        d:=0;c:=r;
        g:=(d+c) div 2;
        while (g<>d) and (g<>c) do
                begin
                        if b[g]>x then c:=g else d:=g;
                        g:= (d+c) div 2;
                end;
        for g:=c downto d do
                if x>=b[g] then exit(g);
end;
procedure process;
var     tam     :longint;
begin
        qs(1,n);
        a:=w;
        b[0] := -oo;
        b[1] := a[n];
        res :=1;
        for i:=n-1 downto 1 do
                begin
                        tam := tim(res,a[i]);
                        if tam+1>res then
                                begin
                                        res := res+1;
                                        b[res] := a[i];
                                end
                                else
                                if b[tam+1]>a[i] then b[tam+1]:=a[i];
                end;
end;
procedure print;
begin
        writeln(res);
end;
begin
assign(input,fi);reset(input);
assign(output,fo);rewrite(output);
  read(t);
  for tt :=1 to t do
  begin
        enter;
        process;
        print;
  end;
close(input);close(output);
end.
Chủ đề: SPOJ, Tìm kiếm nhị phân Mức độ:

VOMOVREC – SPOJ

February 22, 2016 by Leave a Comment

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

Thuật toán: Ta sẽ tìm kiếm nhị phân kết quả của bài toán. Với mỗi giá trị chia nhị phân V, ta sẽ “nở” các hình chữ nhật ra về bốn phía một độ dài bằng V. Lúc này điều kiện cần và đủ để tất cả các hình chữ nhật ban đầu có thể di chuyển với khoảng cách không quá V thỏa mãn yêu cầu là tất cả các hình chữ nhật đã được nở có phần giao. Điều kiện N hình chữ nhật có phần giao chung hay không là max(X1) < min(X2) và max(Y1) < min(Y2).

Code:

uses math;
const
  fi='';//vomovrec.inp';
  fo='';//vomovrec.out';
  maxn=trunc(1e6);
  oo=trunc(1e9)*3;
type
  rect = record
    x1,y1,x2,y2 : int64;
    end;
var
  m,n,i,j : longint;
  a : array[1..maxn] of rect;
  d,c,g : int64;
function ok(k : int64) : boolean;
  var i : longint;
      x,y,u,v : int64;
  begin
    x := a[1].x1 - k;
    y := a[1].y1  - k;
    u := a[1].x2  +k;
    v := a[1].y2 + k;
    for i := 2 to n do
      with a[i] do
      begin
        x := max(x, x1-k);
        y := max(y, y1-k);
        u := min(u, x2+k);
        v := min(v, y2+k);
      end;
    if (x<u) and (y<v) then exit(true) else exit(false);
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  read(n);
  for i := 1 to n do
    with a[i] do
      begin
        read(x1,y1,x2,y2);
      end;
  d := 0; c := oo;
  g := (d+c) div 2;
  while (g<>c) and (g<>d) do
    begin
      if ok (g) then c := g else d := g;
      g := (d+c) div 2;
    end;if ok(d) then
      begin
        write(d);
        exit;
      end;
     writeln(c);
  close(input);
  close(output);
end.
Chủ đề: SPOJ, Thuật toán, Tìm kiếm nhị phân Mức độ: ,

MOVE12 – SPOJ

February 16, 2016 by Leave a Comment

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

Thuật toán:

  • Chặt nhị phân thời gian gặp nhau
  • Kiểm tra có thỏa mãn không (sử dụng heap). Bạn có thể đọc cdoe bên dưới sẽ hiểu hơn.

Code:

const
        tfi='';//move12.inp';
        tfo='';//move12.out';
 
var
        fi,fo:text;
        n,nh:longint;
        a,b,h,pos,c,t,v:array[0..10000]of longint;
 
procedure nhap;
        var i:longint;
        begin
                read(fi,n);
                for i:=1 to n do read(fi,c[i],t[i]);
        end;
 
 
procedure swap(var x,y:longint);
        var tg:longint;
        begin
                tg:=x;
                x:=y;
                y:=tg;
        end;
 
procedure upheap(i:longint);
        var j:longint;
        begin
                j:=i div 2;
                if (i>1) and (b[h[i]]<b[h[j]]) then
                        begin
                                swap(h[i],h[j]);
                                upheap(j);
                        end;
        end;
 
procedure downheap(i:longint);
        var j:longint;
        begin
                j:=i+i;
                if (j>nh) then exit;
                if (j<nh) and (b[h[j]]>b[h[j+1]]) then inc(j);
                if b[h[i]]>b[h[j]] then
                        begin
                                swap(h[i],h[j]);
                                downheap(j);
                        end;
        end;
 
procedure push(x:longint);
        begin
                inc(nh);
                h[nh]:=x;
                upheap(nh);
        end;
 
 
function pop:longint;
        begin
                pop:=h[1];
                h[1]:=h[nh];
                dec(nh);
                downheap(1);
        end;
 
procedure sort(l,r:longint);
        var i,j,key:longint;
        begin
                i:=l;
                j:=r;
                key:=a[l+random(r-l+1)];
                repeat
                        while a[i]<key do inc(i);
                        while a[j]>key do dec(j);
                        if i<=j then
                                begin
                                        swap(a[i],a[j]);
                                        swap(b[i],b[j]);
                                        inc(i);
                                        dec(j);
                                end;
                until i>j;
                if i<r then sort(i,r);
                if l<j then sort(l,j);
        end;
 
function check(x:longint):boolean;
        var i,j,u:longint;
        begin
                nh:=0;
                for i:=1 to  n do
                        begin
                                a[i]:=c[i]-(x div t[i]);
                                b[i]:=c[i]+(x div t[i]);
                        end;
                sort(1,n);
                i:=0;
                j:=1;
                for i:=1 to n do
                begin
                while (a[j]<=i)  and (j<=n) do
                        begin
                                push(j);
                                inc(j);
                        end;
                        if nh>0 then u:=pop else u:=0;
                        if b[u]<i then exit(false);
                end;
                exit(true);
        end;
 
 
procedure xuli;
        var l,r,mid,res:longint;
        begin
 
                l:=0;
                r:=10000*10000;
                while l<=r do
                        begin
                                mid:=(l+r) div 2;
                                if check(mid) then
                                        begin
                                                res:=mid;
                                                r:=mid-1;
                                        end
                                else l:=mid+1;
                        end;
                writeln(fo,res);
        end;
 
 
begin
        assign(fi,tfi);
        assign(fo,tfo);
        reset(fi);
        rewrite(fo);
        nhap;
        xuli;
        close(fo);
end.
Chủ đề: Heap, SPOJ, Tìm kiếm nhị phân Mức độ: , ,