MCARDS - Card Sorting

Tác giả: ladpro98

Ngôn ngữ: Pascal

program mcards;
uses    math;
const   maxN=444;
        base=1234;
        fi='';
type    e=record
        c,v:longint;
        end;
var     list:array[1..maxN] of e;
        a,f:array[1..maxN] of longint;
        check:array[1..4] of boolean;
        p:array[1..4] of longint;
        n,c,d,res:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,c,n);
        d:=c*n;
        for i:=1 to d do
        readln(inp,list[i].c,list[i].v);
        close(inp);
        res:=maxN;
end;

function find(r,key:longint):longint;
var     m,k,l:longint;
begin
        l:=1;
        k:=0;
        while l<=r do
        begin
                m:=(l+r) shr 1;
                if a[f[m]]<key then
                begin
                        k:=m;
                        l:=m+1
                end
                else
                r:=m-1;
        end;
        exit(k);
end;

procedure solve;
var     i,j,t:longint;
begin
        for i:=1 to d do
        begin
                for j:=1 to c do
                if list[i].c=p[j] then
                a[i]:=j*base+list[i].v;

        end;
        //lis
        t:=1;f[1]:=1;
        for i:=2 to d do
        begin
                if a[i]<a[f[1]] then
                        f[1]:=i
                else
                if a[i]>a[f[t]] then
                begin
                        inc(t);
                        f[t]:=i;
                end
                else
                f[find(t,a[i])+1]:=i;
        end;
        res:=min(res,d-t);
end;

procedure back(i:longint);
var     j:longint;
begin
        if i>c then
                solve
        else
        begin
                for j:=1 to c do
                if not check[j] then
                begin
                        check[j]:=true;
                        p[i]:=j;
                        back(i+1);
                        check[j]:=false;
                end;
        end;
end;

begin
        input;
        back(1);
        write(res);
end.

Download