WEATHER – SPOJ

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

Thuật toán:

  • Bài này sử dụng thuật toán duyệt đồ thị DFS. Bạn có thể đọc code để hiểu rõ hơn.

Code:

{$inline on}
var
               n, m        :     longint;
               a           :     array[0..100, 0..100] of boolean;
               trace       :     array[0..100] of boolean;
               count       :     longint;
 
procedure      enter;
   var i, j, u, v: longint;
   begin
      readln(n);
      for i:= 1 to n do
         for j:= 1 to n do a[i, j]:= false;
      readln(m);
 
      for i:= 1 to m do
         begin
            readln(u, v);
            a[u, v]:= true;
            a[v, u]:= true;
         end;
   end;
 
procedure      dfs(u: longint);
   var i: longint;
   begin
      inc(count);
      trace[u]:= true;
 
      for i:= 1 to n do
         if a[u, i] and (not trace[i]) then dfs(i);
   end;
 
procedure      solve;
   var i, j, res, k: longint;
   begin
      res:= 0;
 
      for i:= 1 to n do
         for j:= i + 1 to n do
            if a[i, j] then
               begin
                  a[i, j]:= false;
                  a[j, i]:= false;
 
                  for k:= 1 to n do trace[k]:= false;
                  count:= 0;
                  dfs(1);
 
                  res:= res + count*(n - count);
 
                  a[i, j]:= true;
                  a[j, i]:= true;
               end;
      writeln(res);
   end;
 
begin
   enter;
   solve;
end.

CENTRE28 – SPOJ

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

Thuật toán:

  • Tìm đường đi ngắn nhất giữa đỉnh 1 đến mọi đỉnh và giữa đỉnh n đến mọi đỉnh sử dụng thuật toán Dijkstra. Đồng thời ta tính số đường đi ngắn nhất.
  • Gọi d1[i] là đường đi ngắn nhất từ đỉnh 1 đến i
  • Gọi d2[i] là đường đi ngắn nhất từ đỉnh n đến i
  • Gọi f1[i] là số đường đi ngắn nhất từ đỉnh 1 đến i
  • Gọi f2[i] là số đường đi ngắn nhất từ đỉnh n đến i
  • Điều kiện để đỉnh i có thể làm trung tâm kinh tế thứ 3 là: (d1[i]+dn[i]<>d1[n]) hoặc (f1[i]*fn[i]<>f1[n])

Code:

Pascal

const   fi      ='';
        fo      ='';
        maxn    =30000+3;
        maxc    =trunc(1e9)+3;
        maxm    =trunc(1e5);
type    arrd    =array[1..maxn] of longint;
        arrf    =array[1..maxn] of int64;
        arrk    =array[-maxm..maxm] of longint;
        arrh    =array[1..maxn] of longint;
var     d1,dn,d   :arrd;
        f1,fn,f   :arrf;
        n,i,j,m   :longint;
        res     :longint;
        ans     :arrd;
        head :array[1..maxn] of longint;
        link,ts,ke    :arrk;
        // dijkstra heap;
        h,p     :array[1..maxn] of longint;
        nh      :longint;
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
        assign(input,fi);reset(input);
        readln(n,m);
        for i:=1 to m do
                begin
                        read(u,v,w);
                        add(i,u,v,w);
                        add(-i,v,u,w);
                end;
        close(input);
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 then
        if d[h[i]] < d[h[j]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[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 (d[h[j]] > d[h[j+1]]) then inc(j);
        if d[h[j]] < d[h[i]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        downheap(j);
                end;
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        p[i]:=nh;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        p[h[1]]:=1;
        dec(nh);
        downheap(1);
end;
procedure update(i:longint);
begin
        if p[i]=0 then push(i) else upheap(p[i]);
end;
procedure dijkstra(s:longint);
var     u,v,i:longint;
begin
        fillchar(h,sizeof(f),0);
        fillchar(p,sizeof(p),0);
        nh:=0;
        fillchar(f,sizeof(f),0);
        for i:=1 to n do d[i]:=maxc;
        d[s]:=0;
        f[s]:=1;
        push(s);
        repeat
                u:=pop;
                i:=head[u];
                while i<>0 do
                        begin
                                v:=ke[i];
                                if d[v]>d[u]+ts[i] then
                                        begin
                                                d[v]:=d[u]+ts[i];
                                                f[v]:=f[u];
                                                update(v);
                                        end
                                        else
                                if d[v]=d[u]+ts[i] then
                                        begin
                                                f[v]:=f[u]+f[v];
                                        end;
                                i:=link[i];
                        end;
        until nh=0;
end;
procedure process;
begin
        dijkstra(1);
        f1:=f;
        d1:=d;
        dijkstra(n);
        fn:=f;
        dn:=d;
        for i:=1 to n do
                if (d1[i]+dn[i]<>d1[n])
                or (f1[i]*fn[i]<>f1[n]) then
                        begin
                                inc(res);
                                ans[res]:=i;
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        {for i:=1 to n do writeln(d1[i]);}
        writeln(res);
        for i:=1 to res do writeln(ans[i]);
        close(output);
end;
begin
        enter;
        process;
        print;
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;
int n, m;
struct data{
    int u, w;
    bool operator <(const data &op) const
    {
        return w > op.w;
    }
};
vector< data > adj[MAXN];
priority_queue<data, vector<data> > q;
int d[3][MAXN];
long long f[3][MAXN];
void min_path(int cs, int s)
{
    FORE(u, 1, n) d[cs][u] = INF;
    d[cs][s] = 0; f[cs][s] = 1;
    q.push((data){s, 0});
    while (q.size()){
        int u = q.top().u;
        int cost_to_u = q.top().w;
        q.pop();
        if (cost_to_u != d[cs][u]) continue;
        FOR(i, 0, adj[u].size()){
            int v = adj[u][i].u;
            int w = adj[u][i].w;
            if (d[cs][v] > d[cs][u] + w){
                d[cs][v] = d[cs][u] + w;
                f[cs][v] = f[cs][u];
                q.push((data){v, d[cs][v]});
            }
            else
            if (d[cs][v] == d[cs][u] + w) f[cs][v] += f[cs][u];
        }
    }
}
vector< int > ans;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("CENTRE.inp", "r", stdin);
    freopen("CENTRE.out", "w", stdout);
    #endif //MIKELHPDATKE
    cin >> n >> m;
    int u, v, w;
    FORE(i, 1, m){
        cin >> u >> v >> w;
        adj[u].push_back((data){v, w});
        adj[v].push_back((data){u, w});
    }
    min_path(1, 1);
    min_path(2, n);
    FORE(u, 1, n) if (d[1][u] + d[2][u] > d[1][n] || (d[1][u] + d[2][u] == d[1][n] && 1ll * f[1][u] * f[2][u] < f[1][n])) ans.push_back(u);
    cout << ans.size() << endl;
    FOR(i, 0, ans.size()) cout << ans[i]<<endl;
    return 0;
}

QBROBOT – SPOJ

Đề 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();
}

CATALAN – SPOJ

Đề 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.

Thay đổi kích thước và kiểu chữ trong Free Pascal

Như các bạn đã biết, việc phóng to toàn màn hình Free Pascal là không thể ngoại trừ trên Win XP. Ở bài viết này mình sẽ hướng dẫn các bạn cách thay đổi kích thước và kiểu chữ trong Free Pascal để ta quan sát dễ hơn.

Đây là màn hình làm việc của Free Pascal của mình ban đầu, rất khó coi phải không:

free-pascal-yeulaptrinh.pw

Nháy phải vào biểu tượng Free Pascal chọn Properties xuất hiện bảng tùy chọn:

free-pascal-2-yeulaptrinh.pw

Chọn tab Layout. Ở đó bạn có thể tùy chỉnh theo ý thích của mình. Mình để kích thước toàn màn hình nên mình thường để thông số như ở dưới:

free-pascal-3-yeulaptrinh.pw

Đây là giao diện Free Pascal khi mình đã thay đổi thông số như ở hình trên:

free-pascal-4-yeulaptrinh.pw

Để thay đổi cỡ chữ và font chữ bạn chọn tab Font:

free-pascal-4-yeulaptrinh.pw

MINCUT – SPOJ

Đề 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.

VMKEY – SPOJ

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

Thuật toán:

  • (đang cập nhập)

Code:

#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;
int d[100][100];
int w[100][100];
string s;
typedef pair<int, int> ii;
int x[101];
ii p[110];
vector< ii > v;
int pos[11];
int dist[100][100];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("vao.inp", "r", stdin);
    freopen("ra.out", "w", stdout);
    #endif //MIKELHPDATKE
   // cout<<"wtf"<<endl;
    FORE(i, 1, 9) x[i] = i;
    x[10] = 0;
    cin >> s;
    //cout<<s<<endl;
    FOR(i, 0, s.size() - 1){
        d[s[i] - '0'][s[i + 1] - '0']++;
        if (d[s[i] - '0'][s[i + 1] - '0'] == 1) v.push_back(ii(s[i] - '0', s[i + 1] - '0'));
    }
 
    p[1].first = 1; p[1].second = 1;
    p[2].first = 1; p[2].second = 2;
    p[3].first = 1; p[3].second = 3;
    p[4].first = 2; p[4].second = 1;
    p[5].first = 2; p[5].second = 2;
    p[6].first = 2; p[6].second = 3;
    p[7].first = 3; p[7].second = 1;
    p[8].first = 3; p[8].second = 2;
    p[9].first = 3; p[9].second = 3;
    p[10].first = 4; p[10].second = 1;
    FORE(u, 1, 10) FORE(v, 1, 10) dist[u][v] = abs(p[u].first - p[v].first) + abs(p[u].second - p[v].second);
    int ans = INF;
    //FOR(i, 0, s.size() - 1) ans += dist[s[i] - '0'][s[i + 1] - '0'] * d[s[i] - '0'][s[i + 1] - '0'];
    while (next_permutation(x + 1, x + 11)){
        int sum = 0;
        FORE(i, 1, 10) pos[x[i]] = i;
        FOR(i, 0, v.size()){
            int u = v[i].first, vv = v[i].second;
            sum += dist[pos[u]][pos[vv]] * d[u][vv];
        }
        ans = min(ans, sum);
    }
    cout << ans;
    return 0;
}