SPOJ – DHLOCK

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

NKSTEP – SPOJ

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

Thuật toán:

  • (đang cập nhập)

Code:

const   fi='';
        fo='';
        maxn=100000;
var     t:longint;
        a,l,c:array[1..maxn] of int64;
        x,y,hold,tmp,max,k,w:int64;
        i,j:longint;
        res:int64;
        f:text;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,t);
    max:=-1;
    for i:=1 to t do
        begin
            readln(f,x,y);
            a[i]:=abs(x-y);
            if a[i]>max then max:=a[i];
        end;
    close(f);
end;
procedure xuly;
begin
        l[1]:=1; l[2]:=2;
        c[1]:=1;
        tmp:=1;
        hold:=2;
        w:=2;
        while w<max do
        begin
            inc(tmp);
            c[tmp]:=c[tmp-1]+tmp;
            w:=c[tmp]*2;
            inc(hold);
            l[hold]:=w-tmp;
            inc(hold);
            l[hold]:=w;
        end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    for i:=1 to t do
        for j:=1 to hold do
        if l[j]>=a[i] then begin writeln(f,j); break; end;
    close(f);
end;
begin
    nhap;
    xuly;
    xuat;
end.