MIXUP2 - Đàn bò hỗn loạn

Tác giả: ladpro98

Ngôn ngữ: Pascal

program mixup2;
uses    math;
const   maxN=16;
        maxS=1 shl maxN;
        fi='';
var     f:array[0..maxS,0..maxN] of int64;
        a,power:array[0..maxN] of longint;
        n,m,k:longint;
function getbit(a,i:longint):longint;
begin
        exit(a shr (i-1) and 1);
end;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,k);
        for i:=1 to n do
        readln(inp,a[i]);
        close(inp);
end;

procedure init;
var     i:longint;
begin
        power[0]:=1;
        for i:=1 to n do
        power[i]:=power[i-1] shl 1;
        m:=power[n]-1;
end;

procedure dp;
var     i,j,t:longint;
begin
        for i:=1 to n do
        f[0,i]:=1;
        for i:=1 to m do
        for t:=1 to n do
        if getbit(i,t)=0 then
        begin
                for j:=1 to n do
                if (getbit(i,j)=1) and (abs(a[n-t+1]-a[n-j+1])>k) then
                inc(f[i,t],f[i-power[j-1],j]);
        end;
end;

procedure output;
var     i:longint;
        res:int64;
begin
        res:=0;
        for i:=0 to n-1 do
        inc(res,f[m-power[i],i+1]);
        write(res);
end;

begin
        input;
        init;
        dp;
        output;
end.

Download