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.