Giải thuật tìm kiếm Fibonacci

Mình không tìm được từ nào tiếng Việt có thể dịch được từ “Fibonaccian Searching”,
nếu “binary searching” có thể dịch là “tìm kiếm nhị phân”, thì “Fibonaccian Searching”
không có ngữ nghĩa gì nhiều.

Nguồn gốc thuật toán này xuất phát từ bài tập 1.4.22 (Algorithms, Fourth Edition, Sedgewick). Ngoài
ra đây cũng là một nội dung được đề cập trong TAoCP – Vol 3.

Lịch sử

Thuật toán được để xuất bởi Devid E. Ferguson (CACM-1960, link).
Một số phát hiện liên quan, chủ yếu về nguồn gốc cây Fibonacci có thể tham khảo tại TAoCP – Vol 3 (Mục 6.2.1).

Thuật toán

Điểm thú vị của thuật toán này nằm ở chỗ thuật toán không sử dụng phép chia, nhưng vẫn đạt được
độ hiệu quả của binary search. Tuy nhiên, ưu điểm này thực sự có tác dụng
vào thời điểm thuật toán này được đề xuất (1960) khi mà các chép chia, hay
shift bit tốn nhiều chi phí hơn so với phép cộng trừ. Tuy nhiên, fibsearch còn được sử dụng khi tốn ưu thời gian tìm kiếm khi mà dữ liệu quá lớn không
thể đọc lên được toàn bộ lên RAM hoặc cache, khi đó thời gian đọc trên bộ
lưu trữ ngoại vi trở nên tốn kém ( link ).
Tuy nhiên mình nghĩ fibsearch sẽ là một câu hỏi phỏng vấn cực kì thú vị.

Thiết kế một thuật toán tìm kiếm nhị phân không sử dụng phép nhân, chia hoặc
dịch bit với độ phức tạp $\mathcal{O}(\lg N)$

Cài đặt

Phần dưới đây là giải thuật lấy từ TAoCP, mình nghĩ là cực kì dễ hiểu, tạm thời
mình chỉ trình bày mã giả. Có thể tham khảo phần cài đặt bằng C, trong phần
References. Một phiên bản cải tiến với kích thức mảng $N$ bất
kì sẽ được update sau.

[[code]]czo2MDQ6XCJJbnB1dDogbeG6o25nICRLXzEsIEtfMiwgLi4uLCBLX04kIMSRxrDhu6NjIHPhuq9wIHjhur9wIHbDoCBwaOG6p24gdOF7WyYqJl19u60gJEskIGPhuqduIHTDrG0uIEdp4bqjIHPhu60NCiROKzEgPSBGX3trKzF9LiBMxrB1IMO9IGluZGV4IGPhu6dhIG3huqNuZyBi4XtbJiomXX26r3QgxJHhuqd1IDEkDQoNClAxLiBbS2jhu59pIHThuqFvXSBpID0gRltrXSwgcCA9IEZbay0xXSwgcSA9IEZbay0yXQ0KUDIuIFtTe1smKiZdfW8gc8OhbmhdLg0KICAgIGlmIEtbaV0gJmx0OyBLOiBnbyB0byBQMy4NCiAgICBlbHNlIGlmIEtbaV0gJmd0OyBLOiBnbyB0byBQNC57WyYqJl19DQogICAgZWxzZTogcmV0dXJuIGk7DQpQMy4gW1jDqXQgY8OieSBjb24gRmlib25hY2NpIGLDqm4gdHLDoWldDQogICAgaWYgcSA9IHtbJiomXX0wOiByZXR1cm4gLTENCiAgICBlbHNlOg0KICAgICAgICBpIC09IHENCiAgICAgICAgKHAsIHEpID0gKHEsIHAtcSkNCiAgICAgICAge1smKiZdfWdvIHRvIFAyDQpQNC4gW1jDqXQgY8OieSBjb24gRmlib25hY2NpIGLDqm4gcGjhuqNpXQ0KICAgIGlmIHAgPSAxOiByZXR1cm4gLTF7WyYqJl19DQogICAgZWxzZToNCiAgICAgICAgaSArPSBxDQogICAgICAgIHAgLT0gcQ0KICAgICAgICBxIC09IHANCiAgICAgICAgZ28gdG8gUHtbJiomXX0yDQpcIjt7WyYqJl19[[/code]]

Bài tập

  • Thiết kế thuật toán cho trường hợp $N \geq 0$.
  • Thiết kế thuật toán với index bắt đầu bằng 0. Về mặt kĩ thuật chỉ có 1 thay đổi
    nhỏ trong code, nhưng cây Fibonacci sẽ tương đối khác.

Phân tích

Cây tìm kiếm Fibonacci với k=6. Source: TAoCP, Vol 3, P417.

Phần dưới đây là mô tả ngắn gọn cách mà thuật toán này thực thi. Khác với tìm
kiếm nhị phân chia các nhánh tìm kiếm thành các cây nhị phân, fibsearch thay
vào đó xây dựng cây Fibonacci. Cây Fibonacci bậc $k$ được định nghĩa là “cây” với
$F_{k+1}-1$ internal nodes (vòng tròn) và $F_{k+1}$ external nodes (hình vuông),1
cây Fibonacci được xây dựng như sau:

  1. $k=0$ hoặc $k=1$, cây chỉ có 1 external node là 0.
  2. $k \geq 2$, root là có giá trị $F_k$, cây con bên trái là cây fibonacci
    bậc $k-1$ và cây con bên phải là cây fibonacci bậc $k-2$ với tất cả các nodes
    tăng $F_k$ đơn vị.

Thuật toán fibsearch chính là việc xây dựng cây fibonacci bậc $k$ với $N=F_{k+1}$.

Trong Figure 1, cây có bậc $k=6$ (tương đương với tìm mảng có $N=12$ phần tử
($N+1=F_{k+1} = F_7 = 13$)), số internal nodes
$F_{k+1}-1=12$ và $F_{k+1}=13$ external nodes. Ngoài ra,
ta có thể thấy root = $F_6 = 8$, phần nhánh bên trái của 8 có
$F_6-1=7$ internal nodes, và bên phải gồm $F_5-1 = 4$ internal
nodes. Tiếp tục xuống các level thấp hơn là các giá trị $F$ nhỏ hơn và theo
đúng quy luật đã nêu. Nhìn hình ta có thể hình dung phần nào, với cách tiếp cận
chia để trị tương đồng với tìm kiếm nhị phân, tìm kiếm fibonaci “có thể”
có độ phức tạp tương tự.

Một chứng minh cụ thể và chi tiết hơn sẽ được cập nhật sau, kèm theo đó là mã
nguồn C++ của thuật toán.

Dạng tổng quát

Cả tìm kiếm nhị phân lẫn Fibonacci search thực ra cũng thuộc một dạng tổng quát
của một chiến lược chia để trị trong tìm kiếm chuỗi đã được sắp xếp.

Gọi $p$ và $q$ thỏa $p+q=1$, gọi $C(N)$ là số phép so sánh cần thực hiện của
giải thuật. Chiến lược ở đây đó là chia mảng thành 2 phần với số lượng phần
tử lần lượt là $pN$ và $qN$. Ta có dãy truy hồi số phép so sánh trong thuật toán:

$$ C(N) = 1 + pC(pN) + qC(qN) $$

Công thức này có dạng close form là $C(N) = \log_bN$ trong đó $b$ là hằng số
cần tìm. Dễ dàng thấy được với tìm kiếm nhị phần $p=q={1 \over 2}$, còn với
fibsearch thì $p={1 \over \phi}$ và $q= {1 \over \phi^2}$. Cụm $pC(pN)$ ở
đây có nghĩa là xác suất $p$ phần tử cần tìm nằm trong khoảng $pN$ phần tử
đã được chia, tương tự với $qC(qN)$.

[$b = p^{-p}q^{-q}$
nhưng hiện giờ vẫn chưa biết giải như thế nào. Đây là dạng divide-and-conquer
recurrence. Nếu sử dụng Akra-Bazzi method
thì ta chỉ mới tìm được $\Theta(1 + \ln N)$ của nó nhưng vẫn chưa xác định được $b$].

References

TODO

Mình cũng không biết nên dịch internal nodes với external nodes thế nào cho hợp (node trong và node ngoài?). ^

COMNET – spoj

Đề bài:

Tóm tắt đề:

Cho M đường truyền có các chi phí wi, các truy vấn người ta thay đổi trọng số một số cạnh và hỏi xem cạnh thứ k có thể loại bỏ vì nó không thuộc vào cây khung nhỏ nhất của đồ thị hay không.

Thuật toán:

-Sau khi thay đổi trọng số các cạnh theo đề bài (nếu các cạnh có trọng số bằng nhau thì ưu tiên xét cạnh k đứng đầu), tìm cây khung nhỏ nhất của đồ thị và in ra ‘YES’ hay ‘NO’ tương ứng là cây trả lời. ĐPT O(test*nlogn)
-Thuật toán trên sẽ giúp bạn có được 60->70 điểm, đề ăn full bạn cần thay đổi một chút trước khi tìm cây khung: Vẫn thay đổi trọng số các cạnh theo đề bài, nhưng không sort lại các cạnh mà tìm các cạnh có trọng số nhỏ hơn trọng số của cạnh thứ k, hợp nhất các gốc lại.

Kiểm tra xem hai đỉnh của cạnh thứ k đã thuộc vào cây khung hay chưa rồi in ra ‘YES’ hay ‘NO’ tương ứng. ĐPT O(test*n).

Code:

#include <iostream>
#include <vector>
using namespace std;
 
#define LL long long
 
struct universe {
    vector<int> cha, rank;
    universe(int n): cha(n + 1), rank(n + 1, 0) {
        for (int i=1; i<=n; i++) cha[i] = i;
    }
    int find(int u) {
        if (cha[u] != u) cha[u] = find(cha[u]);
        return cha[u];
    }
    bool join(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        if (rank[u] == rank[v]) rank[u]++;
        if (rank[u] > rank[v]) cha[v] = u;
        else cha[u] = v;
        return true;
    }
};
 
struct pack { int u, v; };
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m, Q; cin >> n >> m >> Q;
        vector<pack> e(m);
        vector<int> w(m);
        for (int i=0; i<m; i++) cin >> e[i].u >> e[i].v >> w[i];
        while (Q--) {
            int id; cin >> id; id--;
            int s; cin >> s;
            vector<int> ww(w);
            while (s--) {
                int t, w; cin >> t >> w;
                ww[t-1] = w;
            }
            universe a(n);
            for (int i=0; i<m; i++) if (ww[i] < ww[id]) {
                a.join(e[i].u, e[i].v);
            }
            if (a.join(e[id].u, e[id].v)) cout << "NO\n";
            else cout << "YES\n";
        }
    }
    return 0;
}

LUBENICA – spoj

Đề bài:

Thuật toán:

  • LCA

Code:

uses    math;
const   fi='';
        fo='';
        maxk=20;
        maxn=trunc(1e5)+3;
        oo=2*trunc(1e9);
 
type    arr1    =array[1..maxn] of longint;
        arr2    =array[1..maxn,0..maxk] of longint;
 
var     mi,ma,p         :arr2;
        depth,dad       :arr1;
        i,j,n,m,q       :longint;
        link,head,ke,ts :array[-maxn..maxn] of longint;
        resma,resmi     :longint;
        cx      :array[1..maxn] of boolean;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
 
procedure enter;
var     u,v,w   :longint;
begin
        readln(n);
        for i:=1 to n-1 do
        begin
                read(u,v,w);
                add(i,u,v,w);
                add(-i,v,u,w);
        end;
end;
 
procedure dfs(u:longint);
var     i,v     :longint;
begin
        cx[u]:=false;
        i := head[u];
        while i<>0 do
                begin
                        v:=ke[i];
                        if cx[v] then
                                begin
                                        depth[v]:=depth[u]+1;
                                        dad[v]:=u; ma[v,0] := ts[i]; mi[v,0] := ts[i];
                                        dfs(v);
                                end;
                        i:=link[i];
                end;
end;
 
procedure init;
var     i,j     :longint;
begin
        fillchar(cx,sizeof(cx),true);
        dad[1] := 1; depth[1] :=1;
        dfs(1);
        for i:=1 to n do
                begin
                        p[i,0] := dad[i];
                end;
        for j:=1 to maxk do mi[1,0] := oo;
        for j:=1 to maxk do ma[1,0] := -oo;
        for j:=1 to maxk do
                for i:=1 to n do
                        begin
                                p[i,j] := p[p[i,j-1],j-1];
                                ma[i,j] := max(ma[i,j-1],ma[p[i,j-1],j-1]);
                                mi[i,j] := min(mi[i,j-1],mi[p[i,j-1],j-1]);
                        end;
end;
procedure lca(u,v:longint);
var     i,j     :longint;
begin
        for i:=maxk downto 0 do
                if depth[p[u,i]]>=depth[v] then
                        begin
                                resma := max(resma,ma[u,i]);
                                resmi := min(resmi,mi[u,i]);
                                u := p[u,i];
                        end;
        for i:=maxk downto 0 do
                if depth[p[v,i]]>=depth[u] then
                        begin
                                resma := max(resma,ma[v,i]);
                                resmi := min(resmi,mi[v,i]);
                                v := p[v,i];
                        end;
        if u=v then exit;
        for i:=maxk downto 0 do
                if p[u,i]<>p[v,i] then
                        begin
                                resma := max(resma,ma[v,i]);
                                resmi := min(resmi,mi[v,i]);
                                resma := max(resma,ma[u,i]);
                                resmi := min(resmi,mi[u,i]);
                                v := p[v,i];
                                u := p[u,i];
                        end;
        resma := max(resma,ma[v,0]);
        resmi := min(resmi,mi[v,0]);
        resma := max(resma,ma[u,0]);
        resmi := min(resmi,mi[u,0]);
end;
procedure process;
var     u,v,qq  :longint;
begin
        read(q);
        for qq:=1 to q do
                begin
                        read(u,v);
                        if u=v then begin writeln(0,' ',0); continue; end;
                                resmi := oo;
                                resma := -oo;
                                lca(u,v);
                        writeln(resmi,' ',resma);
                end;
end;
procedure print;
begin
 
end;
 
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
                enter;
                init;
                process;
                print;
        close(input);close(output);
end

LABUDOVI – spoj

Đề bài:

Thuật toán:

  • BFS
  • Bài này chú ý dùng phương pháp loang đồ thị để làm; chúng ta sẽ dùng 2 mảng nextx, nexty để loang ra 4 ô xung quanh của 1 ô.
  • Đầu tiên đánh dấu vị trí của 2 con thiên nga và đánh dấu tất cả các ô là nước.
  • Sau đó tiến hành loang từ con thiên nga thứ nhất. Nếu gặp con thiên nga thứ hai thì return.
    Nếu không thì tiến hành loang các ô bên cạnh là ô băng; nếu gặp ô băng thì chuyển thành ô nước, đánh dấu lại và tăng biến đếm lên 1. Tiếp tục như vậy cho tới khi gặp được con thiên nga thứ hai.

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
 
#define task ""
#define fi first
#define se second
#define maxinp (int)(1500)
#define MODUL (int)(1e9+57)
#define siz(x) (int)(x.size())
#define len(x) (int)(x.length())
#define whole(x) x.begin(), x.end()
#define FOR(i, x, y) for(int i=x; i<=y; ++i)
#define FORl(i, x, y) for(int i=x; i<y; ++i)
#define FORb(i, x, y) for(int i=x; i>=y; --i)
#define FORlb(i, x, y) for(int i=x; i>y; --i)
#define MEMS(x, val) memset(x, val, sizeof(x))
#define FILEOP(x) freopen(x".inp", "r", stdin); freopen(x".out", "w", stdout);
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef queue<ii> qii;
typedef long long ll;
int nextx[4] = {-1, 0, 0, 1};
int nexty[4] = {0, -1, 1, 0};
bool Free[maxinp][maxinp];
int Time[maxinp][maxinp];
char a[maxinp][maxinp];
int m, n, res, nTime;
qii mainq, subq;
ii start[3];
int nInstruction = 0;
void Debug()
{
 
    cout << endl;
    FOR(i, 1, m)
    {
        FOR(j, 1, n)
        {
            cout << Time[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
 
 
}
 
 
void Enter()
{
	int cnt = 1;
	MEMS(Free, true);
 
 
	scanf("%d%d", &m, &n);
 
 
 
 
	FOR(i, 1, m)
	{
	    FOR(j, 1, n)
	    {
 
	        cin >> a[i][j];
 
 
            if(a[i][j] != 'X')
            {
                Time[i][j] = 0;
 
                mainq.push(ii(i, j));
 
                if(a[i][j] == 'L')
                {
                    start[cnt] = ii(i, j);
                    ++cnt;
                }
 
                Free[i][j] = false;
            }
            else Time[i][j] = 1234567890;
 
            ++nInstruction;
 
 
	    }
	}
 
}
 
//Check
bool IsValid(int _x, int _y)
{
    return(_x >= 1 && _y >= 1 && _x <= m && _y <= n && Free[_x][_y]);
}
 
void PreProcess()
{
    while(!mainq.empty())
    {
        int curx = mainq.front().first;
        int cury = mainq.front().second;
 
        ++nInstruction;
        mainq.pop();
 
        FOR(i, 0, 3)
        {
            int x = curx + nextx[i];
            int y = cury + nexty[i];
 
            if(IsValid(x, y))
            {
                if(a[x][y] == 'X')
                {
                    Free[x][y] = false;
                    mainq.push(ii(x, y));
                    Time[x][y] = min(Time[x][y], Time[curx][cury] + 1);
                }
            }
        }
 
    }
 
    //Debug();
 
 
 
}
void FloodFill1(ii st1, ii st2)
{
    mainq.push(st1);
    Free[st1.first][st1.second] = false;
    while(!mainq.empty())
    {
        int curx = mainq.front().first;
        int cury = mainq.front().second;
 
        //Time[curx][cury] = nTime;
        ++nInstruction;
 
        mainq.pop();
 
        FOR(i, 0, 3)
        {
            int x = curx + nextx[i];
            int y = cury + nexty[i];
            ii dir = ii(x, y);
 
            if(IsValid(x, y))
            {
                Free[x][y] = false;
                if(dir == st2) return;
                if(Time[x][y] <= res) mainq.push(dir);
                else subq.push(dir);
            }
        }
 
        if(mainq.empty())
        {
            ++res;
            swap(mainq, subq);
        }
 
    }
}
 
//Process
void Solve()
{
    res = 0;
    PreProcess();
    MEMS(Free, true);
    FloodFill1(start[1], start[2]);
    printf("%d", res);
 
 
    cerr << endl;
    cerr << nInstruction << endl;
 
}
 
//Main Procedure
int main()
{
    Enter();
    Solve();
    return 0;
}

VOTREE – spoj

Đề bài:

Giải thích ví dụ

votree-yeulaptrinh
Truy vấn 1: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 2 đến 5, ở đây có thể thấy 2 là tổ tiên chung gần nhất của các đỉnh 2,3,4,5.
Truy vấn 2: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 1 đến 3, ở đây có thể thấy 1 là tổ tiên chung gần nhất của các đỉnh 1,2,3.
Truy vấn 3: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 4 đến 5, ở đây có thể thấy 3 là tổ tiên chung gần nhất của các đỉnh 4,5.

Thuật toán:

    Có thể nhận thấy rằng tổ tiên chung gần nhất ( LCA ) của 3 đỉnh a,b,c sẽ bằng với LCA(a,LCA(c,b)). Dựa trên tính chất nãy ta có thể sử dụng Interval Tree để tìm LCA của 1 đoạn liên tiếp bằng cách tổ chức cây IT sẽ lưu LCA của các phần tử trong đoạn quản lý.

    Các phần cơ bản của cây IT:

    IT[id] = phần tử đang được quản lý khi đoạn quản lý gồm 1 phần tử.

    IT[id] = LCA(IT[id*2],IT[id*2+1] ).

    P/s : Có rất nhiều cách để tìm LCA ví dụ như : Sparse Table, Heavy Light Decomposition, Interval Tree, …

Code:

const
        tfi='';
        tfo='';
 
var
        fi,fo:Text;
        ke,nx:array[-70000..70000] of longint;
        num,thoat,hd:array[0..70000] of longint;
        f:array[0..70000,0..20] of longint;
        n,q,jmax,dem,dem1:longint;
        t:array[0..3000000] of longint;
 
procedure nhap;
        var i,j,u,v:longint;
        begin
                read(fi,n,q);
                for i:=1 to n-1 do
                        begin
                                read(fi,u,v);
                                ke[i]:=v;
                                nx[i]:=hd[u];
                                hd[u]:=i;
                                ke[-i]:=u;
                                nx[-i]:=hd[v];
                                hd[v]:=-i;
                        end;
                for j:=1 to 20 do if 1 shl j<=n then jmax:=j+1;
        end;
 
procedure DFS(u:longint);
        var j,v:longint;
        begin
                inc(dem);
                num[u]:=dem;
                for j:=1 to jmax do f[u,j]:=f[f[u,j-1],j-1];
                j:=hd[u];
                while j<>0 do
                        begin
                                v:=ke[j];
                                if f[v,0]=0 then
                                        begin
                                                f[v,0]:=u;
                                                DFS(v);
                                        end;
                                j:=nx[j];
                        end;
                inc(dem1);
                thoat[u]:=dem1;
        end;
 
function cha(x,y:longint):boolean;
        begin
            cha:=(num[x]<=num[y]) and (thoat[y]<=thoat[x]);
        end;
 
function lca(x,y:longint):longint;
        var j:longint;
        begin
                if cha(x,y) then exit(x);
                if cha(y,x) then exit(y);
                for j:=jmax downto 0 do
                        if not cha(f[x,j],y) then x:=f[x,j];
                exit(f[x,0]);
        end;
 
procedure init(i,l,r:longint);
        var mid:longint;
        begin
            if l=r then
                begin
                        t[i]:=l;
                        exit;
                end;
            mid:=(l+r) div 2;
            init(i*2,l,mid);
            init(i*2+1,mid+1,r);
            t[i]:=lca(t[i*2],t[i*2+1]);
        end;
 
function get(i,l,r,u,v:longint):longint;
        var mid:longint;
        begin
                if (l>v) or (r<u) then exit(u);
                if (u<=l) and (r<=v) then exit(t[i]);
                mid:=(l+r) div 2;
                get:=lca(get(i*2,l,mid,u,v),get(i*2+1,mid+1,r,u,v));
        end;
 
procedure xuli;
        var i,u,v,pa,j:longint;
        begin
                f[1,0]:=1;
                DFS(1);
                init(1,1,n);
                for i:=1 to q do
                        begin
                                read(fi,u,v);
                                writeln(fo,get(1,1,n,u,v));
                        end;
 
        end;
 
begin
        assign(fi,tfi);
        assign(fo,tfo);
        reset(fi);
        rewrite(fo);
        nhap;
        xuli;
        close(fo);
end.

MINROAD – spoj

Đề bài

Thuật toán

Ta lưu 2*n điểm vào mảng T:

  • T[i].d là khoảng cách đến vị trí bắt đầu của con đường
  • T[i].k là 1 nếu là cây tùng, là 2 nếu là cây trúc

Sắp xếp mảng T theo thứ tự tăng dần T[i].d

Với mỗi T[i], ta phải tìm vị trí X sao cho từ T[i] đến T[x] có ít nhất a cây tùng và b cây trúc. Đặt F[i]=X.

Dễ dàng nhận thấy: F[i] <= F[i+1] nên ta có thể sử dụng 2 vòng For để tính toán kết quả như sau:

For i=1 to 2*N do 
 For j=F[i-1] to 2*N do ……..
Thay vì dùng mảng F, bạn hoàn toàn có thể sử dụng biến chạy mà thôi

Độ phức tạp: O(N log N).

Code

uses    math;
const   fi='';
        fo='';
        maxn=300000;
type    arra=array[0..maxn] of longint;
var     tung,cuc,d,tu,cu:arra;
        kieu:array[0..maxn] of byte;
        i,j,n,a,b:longint;
        f:text;
        res,tmp:longint;
procedure QS(l,r:longint);
Var i,j,x,w:longint;
Begin
x:=d[(l+r) div 2];
  i:=l;j:=r;
  Repeat
    While(d[i]<x) do i:=i+1;
     While (x<d[j]) do j:=j-1;
      If i<=j then
        Begin
          w:=kieu[i];kieu[i]:=kieu[j];kieu[j]:=w;
          w:=d[i];d[i]:=d[j];d[j]:=w;
          i:=i+1;j:=j-1;
        End;
 until i>j;
 If l<j then QS(l,j);
 If i<r then QS(i,r);
End;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n,a,b);
    for i:=1 to n do
        readln(f,d[i],kieu[i]);
    close(f);
end;
procedure xuly;
var     t,c,k:longint;
begin
    t:=0; c:=0;
    qs(1,n);
    for i:=1 to n do
        if kieu[i]=1 then begin inc(t); tung[t]:=i; end
        else begin inc(c); cuc[c]:=i; end;
    for i:=1 to n do
    begin
        tu[i]:=tu[i-1];
        cu[i]:=cu[i-1];
        if kieu[i]=1 then inc(tu[i]);
        if kieu[i]=2  then inc(cu[i]);
    end;
if (tu[n]<a) or(cu[n]<b) then exit;
    i:=max(tung[a],cuc[b]);
    k:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
    res:=d[i]-d[k];
    inc(i);
    while i<=n do
    begin
        tmp:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
        if d[i]-d[tmp]<res then res:=d[i]-d[tmp];
        inc(i);
    end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    if res=0 then writeln(f,-1) else
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    xuly;
    xuat;
end.

INFORMAC – spoj

Đề bài:

Thuật toán:

Code:

uses math;
const
  fi='';//informac.inp';
  fo='';//informac.out';
  maxm=40000;
  maxn=200;
var
  match : array[1..maxn] of longint;
  l,r : array[1..maxn] of longint;
  left,right  :  array[1..maxn] of longint;
  link,head,ke : array[1..maxm] of longint;
  i,j,n,m,x,y,u,v : longint;
  kt : boolean;
procedure enter;
  var i,j,k : longint;
  begin
    assign(input,fi);reset(input);
    read(n,m);
    for i:=1 to n do
      begin
        r[i] := n;
        right[i] := n;
      end;
    for i:=1 to n do
      begin
        l[i] := 1;
        left[i] := 1;
      end;
    for i:=1 to m do
      begin
        read(j,x,y,v);
        left[v] := max(left[v], x);
        right[v] := min(right[v], y);
        if j = 1 then
          begin
            for k := x to y do r[k] := min(r[k],v);
          end;
        if j = 2 then
          begin
            for k := x to y do l[k] := max(l[k],v);
          end;
      end;
    close(input);
  end;
Procedure Ghepcap;
  var old,i,j,nlist : longint;
      cx : array[1..maxn] of boolean;
      found : boolean;
      list : array[1..maxn] of longint;
  procedure dfs( u : longint);
    var v,i : longint;
    begin
      i := head[u];
      while i <> 0 do
        begin
          v := ke[i];
          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;
          i := link[i];
        end;
    end;
  begin
    for i:=1 to n do list[i] := i;
    nlist := n;
    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 nlist = old;
  end;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure process;
  begin
    kt := false;
    for i:=1 to n do
      if r[i] < l[i] then exit;
    for i:=1 to n do
      for j:=left[i] to right[i] do
        if (i>=l[j]) and (i<=r[j]) then
        begin
          inc(m);
          add(m,i,j);
        end;
    ghepcap;
    for i:=1 to n do
      if match[i] = 0 then exit;
    kt := true;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    if not kt then writeln(-1) else for i:=1 to n do write(match[i],' ');
  end;
begin
  enter;
  process;
  print;
end.