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 độ:

BALLGMVN – SPOJ

May 21, 2016 by Leave a Comment

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

Thuật toán:

Với mỗi điểm[i] từ 1–>N:

  • Dời gốc tọa độ về điểm[i] nên xNew[j]=x[j]-x[i] và yNew[j]=y[j]-y[i] với mỗi 1<=j<=N.
  • Sắp xếp các điểm theo giá trị x/y.
  • Các điểm có cùng giá trị chính là các điểm trên cùng một đường thẳng. Xử lý và in kết quả.

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

Code:

const   fi='';
        fo='';
        maxn=1000;
type    point=record
                x,y:longint;
                end;
var     i,j,n:longint;
        p:array[1..2*maxn] of point;
        tmp:longint;
        hold:array[1..2*maxn] of real;
        cs:array[1..2*maxn] of integer;
procedure mo;
begin
    assign(input,fi); reset(input);
    assign(output,fo); rewrite(output);
end;
procedure doc;
begin
    read(n);
    for i:=1 to 2*n do read(p[i].x,p[i].y);
end;
procedure QS(l,r:longint);
Var     i,j:longint;
        x,w:real;
        tg:longint;
Begin
x:=hold[(l+r) div 2];
  i:=l;j:=r;
  Repeat
    While(hold[i]<x) do i:=i+1;
     While (x<hold[j]) do j:=j-1;
      If i<=j then
        Begin
          w:=hold[i];hold[i]:=hold[j];hold[j]:=w;
          tg:=cs[i];cs[i]:=cs[j];cs[j]:=tg;
          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 xuly;
var     a,b,k:longint;
begin
    for i:=1 to n do
    begin
        for j:=n+1 to 2*n do
                begin
                    a:=p[j].x-p[i].x;
                    b:=p[j].y-p[i].y;
                    if b=0 then hold[j]:=low(longint)
                        else hold[j]:=a/b;
                end;
        for j:=n+1 to 2*n do cs[j]:=j;
        qs(n+1,2*n);
         for j:=n+2 to 2*n do
                if hold[j]=hold[j-1] then
                        begin
                            write(i,' ');
                            for k:=j-1 to j do write(cs[k],' ');
                            halt;
                        end;
    end;
    for i:=n+1 to 2*n do
    begin
        for j:=1 to n do
                begin
                    a:=p[j].x-p[i].x;
                    b:=p[j].y-p[i].y;
                    if b=0 then hold[j]:=low(longint)
                        else hold[j]:=a/b;
                end;
        for j:=1 to n do cs[j]:=j;
        qs(1,n);
         for j:=2 to n do
                if hold[j]=hold[j-1] then
                begin
                    write(i,' ');
                    for k:=j-1 to j do write(cs[k],' ');
                    halt;
                end;
    end;
    writeln(-1);
    halt;
end;
begin
    mo;
    doc;
    xuly;
end.
Chủ đề: SPOJ

MATCH1 – SPOJ

May 11, 2016 by Leave a Comment

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

Thuật toán:

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, SPOJ, Thuật toán 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 độ: , , , ,

QBSEQ – SPOJ

May 4, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Gọi F[i][j] là độ dài dãy con dài nhất của dãy A[1..i] có tổng các phần tử chia k dư j.

Các bạn có thể tham khảo thuật toán chi tiết ở trang 162 quyển “Giải thuật và lập trình” của thầy Lê Minh Hoàng.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=1000;
  maxk=50;
var
  f : array[0..maxn,0..maxk] of longint;
  a : array[1..maxn] of longint;
  i,j,n,k : longint;
procedure enter;
  begin
    assign(input,fI);reset(input);
    readln(n,k);
    for i:=1 to n do read(a[i]);
    close(input);
  end;
function calc ( x,y : longint) : longint;
  var tg : longint;
  begin
    tg := (x-y) mod k ;
    if tg<0 then tg := tg+k;
    exit(tg);
  end;
procedure solve;
  begin
    for i:=0 to n do
      for j:=0 to k-1 do
        f[i,j] := -maxn*maxn;
    f[0,0] := 0;
    for i:=1 to n do
      for j:=0 to k-1 do
        f[i,j] := max(f[i-1,j],f[i-1,calc(j,a[i])] +1);
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(f[n,0]);
    close(output);
  end;
begin
  enter;
  solve;
  print;
end.
Chủ đề: Phương pháp, Quy hoạch động, SPOJ Mức độ: , , ,

LIQ và LIS sử dụng BIT – SPOJ

May 2, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Rời rạc hóa lại dãy
  • Gọi F[i] là độ dài dãy con tăng dài nhất kết thúc là số <= i
  • F[i] = max(F[1..a[i]-1] + 1)
  • Sử dụng cấu trúc dữ liệu BIT để tính mảng F trong O(logn)
  • ĐPT: O(nlogn)

Code:

using namespace std;
//#include<bits/stdc++.h>
#include <algorithm>
#include <stdio.h>
#define FOR(i,a,b) for (long long i=a;i<b;i++)
#define FORE(i,a,b) for (long long i=a;i<=b;i++)
#define FORD(i,a,b) for (long long i=a;i>=b; i--)
 
int n, a[300010], T[300010], c[300010], f[300010], dem;
pair<int, int> b[300010];
 
int Get(int x)
{
    int ans = 0;
    if (x == 0) return 0;
    while (x > 0) {
        ans = max(ans, T[x]);
        x -= x & (-x);
    }
    return ans;
}
 
void Update(int x, int v)
{
    while (x <= n){
        T[x] = max(T[x], v);
        x += x & (-x);
    }
}
 
int main()
{
    //freopen("LIS.inp", "r", stdin);
    //freopen("LIS.out", "w", stdout);
    //cin>>n;
    scanf("%d", &n);
    FORE(i, 1, n) {
        //cin>>a[i];
        scanf("%d", &a[i]);
        b[i].first = a[i];
        b[i].second = i;
    }
 
    sort(b + 1, b + n + 1);
 
    int dem = 1; c[ b[1].second ] = dem;
    FORE(i, 2, n) {
        if (b[i].first > b[i - 1].first) dem++;
        c[ b[i].second ] = dem;
    }
    int ans = 0;
 
    FORE(i, 1, n) a[i] = c[i];
    //FORE(i, 1, n) cout<<a[i]<<" ";cout<<"=="<<endl;
    //cout<<"????"<<endl;
    FORE(i, 1, n) {
        f[i] = Get(a[i] - 1) + 1;
        Update(a[i], f[i]);
        ans = max(ans, f[i]);
    }
 
    //cout<<ans<<endl;
    printf("%d", ans);
    return 0;
}
Chủ đề: BIT, Cấu trúc dữ liệu, SPOJ, Thuật toán Mức độ: , , , ,

NKGOLF – SPOJ

April 29, 2016 by Leave a Comment

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

Thuật toán:

  • (đang cập nhập)

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <utility>
#include <sstream>
using namespace std;
 
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define DOW(i,a,b) for(int i = (a); i >= (b); i--)
#define RESET(c,val) memset(c,val,sizeof(c))
#define sz(a) int(a.size())
#define pb push_back
 
typedef long long ll;
typedef unsigned long long ull;
 
/*---------------------------*/
 
const int maxn = 1e3 + 2;
int m, n, res, tt;
ll a[maxn][maxn];
bool b[maxn][maxn];
 
void input() {
    scanf("%d %d", &m, &n);
    RESET(a,0);
    FOR(i,1,m)
    FOR(j,1,n)
    scanf("%lld", &a[i][j]);
}
 
void solve() {
    FOR(i,1,m-1)
    FOR(j,1,n-1)
    b[i][j]=((a[i][j]<=a[i+1][j]) && (a[i][j]<=a[i][j+1])
             && (a[i+1][j]<=a[i+1][j+1]) && (a[i][j+1]<=a[i+1][j+1]));
 
    res=1;
    // search row
    FOR(i,1,m) {
        tt=1;
        FOR(j,2,n)
        if ( a[i][j]>=a[i][j-1] ) {
            tt++;
            res=max(res,tt);
        } else tt=1;
    }
 
    // search col
    FOR(j,1,n) {
        tt=1;
        FOR(i,2,m)
        if ( a[i][j]>=a[i-1][j] ) {
            tt++;
            res=max(res,tt);
        } else tt=1;
    }
 
    int h[maxn], l[maxn], r[maxn];
    RESET(h,0);
    RESET(l,0);
    RESET(r,0);
    FOR(i,1,m-1) {
        FOR(j,1,n-1)
        if ( b[i][j] ) h[j]++;
        else h[j]=0;
 
        //deque
        int d[maxn];
        int top=0;
        d[0]=0;
        FOR(j,1,n-1) {
            while(top && h[j]<=h[d[top]])
                r[d[top--]]=j-1;
            l[j]=d[top]+1;
            d[++top]=j;
        }
        while(top) r[d[top--]]=n-1;
 
        FOR(j,1,n-1)
        if ( h[j]>0 ) {
            res=max(res,(h[j]+1)*(r[j]-l[j]+2));
        }
    }
}
 
void output() {
    printf("%d", res);
}
 
int main() {
    input();
    solve();
    output();
 
    return 0;
}
Chủ đề: SPOJ, Thuật toán Mức độ: ,

CTNOWN – SPOJ

April 29, 2016 by Leave a Comment

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

Thuật toán:

  • (đang cập nhập)

Code:

uses    math;
const   fi='';
        fo='';
        maxn=350;
var     n,i,j   :longint;
        dem     :longint;
        nto     :array[1..maxn] of longint;
        cx      :array[1..maxn] of boolean;
        f       :array[0..maxn,0..maxn] of qword;
        t,tt,k    :longint;
        res,tam     :qword;
procedure sangnto;
var     i,j     :longint;
begin
        for i:=2 to trunc(sqrt(maxn)) do
                if cx[i]=false then
                        begin
                                j := i*i;
                                while (j<=maxn) do
                                        begin
                                                cx[j]:=true;
                                                j := j+i;
                                        end;
                        end;
        for i:=2 to maxn do
                if cx[i]=false then
                        begin
                                inc(dem);
                                nto[dem] := i;
                        end;
end;
function max(x,y : qword) : qword;
  var tg : qword;
  begin
    if x>y then exit(x) else exit(y);
  end;
procedure main;
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
        sangnto;
        read(t);
                for i:=0 to dem do
                  for j:=0 to maxn do f[i,j] := 1;
                        for i:=1 to dem do
                                begin
                                        for j:=1 to maxn do
                                        begin
                                        f[i,j] := f[i-1,j];
                                        tam:=1;
                                        while tam*nto[i]<=j do
                                                begin
                                                        tam := tam * nto[i];
                                                        f[i,j] := max(f[i,j], f[i-1,j-tam]*tam );
                                                end;
                                        end;
                                end;
        for tt := 1 to t do
                begin
                        read(n);
                        writeln(f[dem,n]);
                end;
        close(input);close(output);
end;
procedure __;
begin
end;
begin
  __ ;
  main;
  __ ;
end.
Chủ đề: Quy hoạch động, SPOJ, Thuật toán Mức độ:

DHFRBUS – SPOJ

April 18, 2016 by Leave a Comment

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

Thuật toán:

  • Sử dụng thuật toán tìm đường đi ngắn nhất dijkstra.
  • Gọi d[u,x] là quãng đường ngắn nhất đi từ s đến u khi dùng x vé xe miến phí
  • Kết quả là d[t,k].

Code:

{$inline on}
 
const   fi      ='';
        fo      ='';
        maxN    =trunc(1e5)*2;
        maxM    =trunc(1e5)*10;
        maxK    =5;
        oo       =2*trunc(1e12);
type    Tadj    =record
                v,w,link:int64;
        end;
 
        THeap   =record
                v1,v2:int64;
        end;
 
        Arr1    =array[0..maxN] of int64;
        Arr2    =array[0..maxM] of Tadj;
        Arr4    =array[0..maxN*maxK] of THeap;
        Arr5    =array[0..maxN,0..maxK] of int64;
 
var     n, m, k :longint;
        Adj     :arr2;
        Head    :arr1;
        s, t    :longint;
        d       :arr5;
        Pos     :arr5;
        H       :arr4;
        nHeap   :longint;
        c       :longint;
//heapmin;
procedure hv(var a, b:int64);
var     tg      :int64;
begin
        tg:=a;a:=b;b:=tg;
end;
 
procedure UpHeap(i:longint);
begin
 
        if (i<=1) or (d[H[i div 2].v1,H[i div 2].v2]<=d[H[i].v1,H[i].v2]) then exit;
        hv(Pos[H[i div 2].v1,H[i div 2].v2],Pos[H[i].v1,H[i].v2]);
        hv(H[i div 2].v1,H[i].v1);
        hv(H[i div 2].v2,H[i].v2);
        UpHeap(i div 2);
end;
 
procedure DownHeap(i:longint);
var     j :longint;
begin
        j:=i*2;
        if j>nHeap then exit;
        if (j<nheap) and (d[H[j+1].v1,H[j+1].v2]<d[H[j].v1,H[j].v2]) then inc(j);
        if d[H[i].v1,H[i].v2]<=d[H[j].v1,H[j].v2] then exit;
        hv(Pos[H[i].v1,H[i].v2],Pos[H[j].v1,H[j].v2]);
        hv(H[i].v1,H[j].v1);
        hv(H[i].v2,H[j].v2);
        DownHeap(j);
end;
 
procedure Update(u,x:longint);
var     p :longint;
begin
        p:=pos[u,x];
        if p=0 then
                begin
                        inc(nHeap);
                        H[nheap].v1:=u;
                        H[nheap].v2:=x;
                        Pos[u,x]:=nHeap;
                        p:=nHeap;
                end;
        UpHeap(p);
end;
 
procedure GetMin(var u, x:longint);
begin
        if nheap=0 then
                begin
                        u:=0;x:=0;
                        exit;
                end;
        u:=H[1].v1;x:=H[1].v2;
        H[1].v1:=H[nHeap].v1;
        H[1].v2:=H[nheap].v2;
        Pos[H[1].v1,H[1].v2]:=1;
        dec(nHeap);
        downHeap(1);
end;
 
procedure Dijkstra;
var      i, v, w      :int64;
        ans     :int64;
        u     ,x  :longint;
begin
        fillchar(pos,n,0);
        for u:=1 to n do
                for x:=0 to k do d[u,x]:=oo;
        nHeap:=0;
        d[s,0]:=0;
        Update(s,0);
        repeat
                GetMin(u,x);
                i:=head[u];
                if u=0 then exit;
                while i<>0 do
                begin
                        v:=adj[i].v;
                        w:=adj[i].w;
                        if d[v,x]>d[u,x]+w then
                        begin
                                d[v,x]:=d[u,x]+w;
                                Update(v,x);
                        end;
                        if (x<k) and (d[v,x+1]>d[u,x]) then
                        begin
                                d[v,x+1]:=d[u,x];
                                Update(v,x+1);
                        end;
                        i:=adj[i].link;
                end;
        until nHeap=0;
        ans:=oo;
        ans:=d[t,k];
        {for x:=0 to k do
                if d[t,x]<ans then
                                ans:=d[t,x];}
        writeln(ans);
end;
 
procedure Tadd(u,v,w:longint);
begin
        inc(c);
        Adj[c].v:=v;
        Adj[c].w:=w;
        Adj[c].link:=head[u];
        head[u]:=c;
end;
 
procedure xuly;
var     i, u, v, w      :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n, m, k, s, t);
        c:=0;
        fillchar(head,sizeof(head),0);
        for i:=1 to m do
                begin
                        readln(u,v,w);
                        Tadd(u,v,w);
                        Tadd(v,u,w);
                end;
        Dijkstra;
        close(input);close(output);
end;
 
begin
        xuly;
end.
Chủ đề: Dijkstra, SPOJ, Thuật toán Mức độ: , , , ,

SPOJ – DHLOCK

April 18, 2016 by Leave a Comment

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

Thuật toán:

  • Bài này không quá khó. Ta chỉ cần duyệt số lần sử dụng cách biến đổi khóa thứ 2 là kk (kk=0..n-1,) với mỗi giá trị kk ta tính số lần ít nhất sử dụng phép biến đổi 1,3 để thỏa.

Code:

const   fi='';
        fo='';
        maxn=300;
var     i,j,n,k:longint;
        kiluc,kq,tam:longint;
        a,b,c:array[1..maxn] of longint;
procedure xuly;
var     kk:longint;
        tmp:longint;
begin
        for kk:=0 to n-1 do
        begin
            for i:=1 to n do
            begin
                if i+kk>n then tam:=(i+kk) mod n else tam:=i+kk;
                if b[tam]>=a[i] then c[i]:=b[tam]-a[i]
                        else c[i]:=b[tam]+k-a[i]+1;
            end;
            for i:=1 to n do
                begin
                    kq:=0;
                    tam:=c[i];
                    for j:=1 to n do
                        if c[j]>=tam then inc(kq,c[j]-tam)
                                else inc(kq,c[j]+k-tam+1);
                    if kq+kk+tam<kiluc then kiluc:=kq+kk+tam;
                end;
        end;
end;
procedure init;
begin
    for i:=1 to n do
        if b[i]>=a[i] then inc(kiluc,b[i]-a[i])
                else inc(kiluc,b[i]+k-a[i]+1);
end;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
 
    readln(n,k);
    for i:=1 to n do read(a[i]);
    for j:=1 to n do read(b[j]);
 
    init;
    xuly;
 
    writeln(kiluc);
 
    close(input);close(output);
end.
Chủ đề: SPOJ, Thuật toán, Vét cạn Mức độ: , ,