Archives for Tháng Mười 2016

MPILOT – SPOJ

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

Thuật toán:

  • Đây là bài tập về thuật toán Heap cơ bản
  • Ta đưa yêu cầu bài toán thành chọn các lái phụ có chênh lệch giữa lương lái chính và lương lái phụ là lớn nhất mà vẫn đảm bảo yêu cầu có thể ghép được n/2 cặp mà tuổi lái phụ < lái chính
  • Heap sẽ lưu độ chênh lệch giữa lương lái phục và chính của mọi người
  • Duyệt i=1..n, đẩy i vào, nếu i lẻ thì lấy ở heap ra 1 thằng làm lại phụ
  • Các bạn hãy đọc code để rõ hơn

Code: [xem code]

const   fi='';
        fo='';
        maxn=10000+3;
var     p,h:array[1..maxn] of longint;
        i,j,n,res,sum:longint;
        a,c:array[1..maxn] of longint;
        nh:longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        for i:=1 to n do read(a[i],c[i]);
        close(input);
end;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
function tinh(x:longint):longint;
begin
        exit(a[x]-c[x]);
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:=i + i;
        if j>nh then exit;
        if (j<nh) and ( tinh(h[j+1]) > tinh(h[j]) ) then inc(j);
        if tinh(h[i]) < tinh(h[j]) then
                begin
                        swap(h[i],h[j]);
                        downheap(j);
                end;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:= i div 2;
        if i>1 then
        if tinh(h[i]) > tinh(h[j]) then
                begin
                        swap(h[i],h[j]);
                        upheap(j);
                end;
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        dec(nh);
        downheap(1);
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        upheap(nh);
end;
procedure process;
begin
        for i:=1 to n do
                begin
                        inc(sum,a[i]);
                        push(i);
                        if i mod 2 = 1 then inc(res,tinh(pop) );
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(sum-res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

VOSMAXK – spoj

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

Thuật toán:

  • Code mình viết bên dưới rất dễ hiểu các bạn có thể tham khảo

Code:

const   inp='';
        out='';
        maxn=1000000;
var     a:array[1..maxn] of longint;
        n,k,i:longint;
        res,tmp,hold:int64;
begin
    assign(input,inp); reset(input);
    assign(output,out); rewrite(output);
    readln(n,k);
    for i:=1 to n do read(a[i]);
 
    res:=0; hold:=0;
    for i:=1 to n do
    begin
        if a[i]=k then
                begin
                        res:=res+(i-hold);
                        tmp:=i-hold;
                end
                else
        if a[i]>k then begin hold:=i; tmp:=0; end
        else res:=res+tmp;
    end;
 
    writeln(res);
    close(input); close(output);
end.

VPBINDEG – spoj

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

Thuật toán:

  • (đang cập nhập)

Code:

{$H+}
program Revolutions_VPbindeg;
const
  fi = '';//Revolutions.inp';
  fo = '';//Revolutions.out';
  maxn = 10001;
var
  n : longint;
  s : string;
  T,k : longint;
 
procedure open;
begin
  assign(input,fi); reset(input);
  assign(output,fo); rewrite(output);
end;
 
procedure clo;
begin
  close(input);
  close(output);
end;
 
function calc(k : longint) : longint;
var
  i,s1,s0,kq : longint;
begin
  s1:=0; s0:=0; kq:=0;
  for i:=1 to n do if s[i]='1' then inc(s1);
  for i:=1 to n do
    if s[i]='0' then
      begin
        inc(s0);
        if (s0>=k) and (s1>=k) then inc(kq,s1-k+1);
      end
    else dec(s1);
  calc:=kq;
end;
 
procedure main;
var
  test : longint;
begin
  readln(T);
  for test:=1 to T do
    begin
      readln(n,k);
      readln(S);
      writeln(calc(k)-calc(k+1));
    end;
end;
 
BEGIN
  open;
  main;
  clo;
END.

PETROLM – spoj

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

Thuật toán:

  • Đây là một bài QHĐ cơ bản suy nghĩ một chút sẽ ra
  • Các bạn hãy đọc code của mình sẽ hiểu ngay

Code:

uses math;
const
  fi='';//petrolm.inp';
  fo='';//petrolm.out';
  maxn=4000;
  oo=trunc(1e18);
type
  arr1 = array[1..maxn] of longint;
var
  tram,xe,csxe,cstram,kq : array[1..maxn] of longint;
  f : array[0..maxn,0..maxn] of int64;
  i,j,n,m : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to n do read(xe[i]);
    read(m);
    for i:=1 to m do read(tram[i]);
    close(input);
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint; var a,b : arr1);
  var i,j,x : longint;
  begin
    i:=l;j:=r;
    x:=a[(l+r) div 2];
    repeat
      while x>a[i] do inc(i);
      while x<a[j] do dec(j);
      if i<=j then
        begin
          swaP(a[i],a[j]);
          swap(b[i],b[j]);
          inc(i);dec(j);
        end;
    until i>j;
    if i<r then qs(i,r,a,b);
    if j>l then qs(l,j,a,b);
  end;
procedure process;
  begin
    for i:=1 to n do csxe[i] := i;
    for i:=1 to m do cstram[i] := i;
    qs(1,n,xe,csxe);
    qs(1,m,tram,cstram);
    for i:=0 to n do
      for j:=0 to n do
        f[i,j] := oo;
    f[0,0] := 0;
    for i:=1 to n do f[i,i] := f[i-1,i-1] + abs(xe[i]-tram[i]);
    for j:=1 to m do
      for i:=j+1 to n do
        begin
          f[i,j] := min(f[i-1,j-1] + abs(xe[i]-tram[j]), f[i-1,j] + abs(xe[i]-tram[j]) );
          f[i,j] := f[i,j];
        end;
  end;
procedure print;
  begin
    assigN(output,fo);rewrite(output);
    writeln(f[n,m]);
    i:=n; j:= m;
    while (i>0) and (j>0) do
      begin
        if f[i,j]=f[i-1,j-1] + abs(xe[i]-tram[j]) then
          begin
            kq[csxe[i]] := cstram[j];
            dec(i);dec(j);
            continue;
          end;
        if f[i,j]=f[i-1,j] + abs(xe[i]-tram[j]) then
          begin
            kq[csxe[i]] := cstram[j];
            dec(i);
            continue;
          end;
      end;
    for i:=1 to n do write(kq[i],' ');
    close(output);
  end;
begin
  enter;
  process;
  print;
end.

QBPOINT – SPOJ

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

Thuật toán:

  • Duyệt n điểm, với mỗi điểm i ta:
    • Duyệt các điểm j <> i rồi tính vector ij lưu lại vào 1 mảng ss[]
    • Sort lại mảng ss[]
    • 3 điểm i,j,k thẳng hàng nếu vector ij = vector ik

Code:

#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;
int n,x[2001],y[2001];
long long res;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("tripoint.inp", "r", stdin);
    freopen("tripoint.out", "w", stdout);
    #endif //
    cin>>n;
    FORE(i,1,n) cin>>x[i]>>y[i];
    FORE(i,1,n)
    {
        vector <double> ss; int cc=0;
        FORE(j,1,n)
        if (x[j]!=x[i])
            ss.push_back((double) (y[j]-y[i])/(x[j]-x[i]));
        else ++cc;
        sort(ss.begin(),ss.end());
        int sl=(cc-2)*(cc-1);
        if (ss.size())
        {
            int dem=1;
            FORE(j,1,ss.size()-1)
            if (ss[j]==ss[j-1]) ++dem;
            else
            {
                sl+=dem*(dem-1);
                dem=1;
            }
            sl+=dem*(dem-1);
        }
        res+=sl;
    }
    cout<<res/6;
    return 0;
}

BLGEN – spoj

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

Thuật toán:

  • (đang cập nhập)

Code:

uses math;
const   fi      ='';
        fo      ='';
        oo      =1000;
        maxc    =trunc(3e6);
var     n       :array[1..2] of longint;
        a       :array[1..2,1..1000] of qword;
        f       :array[0..oo,0..oo] of longint;
        mp      :longint;
        g       :array[1..maxc] of longint;
        nto     :Array[1..300000] of qword;
procedure nhap;
var     i :longint;
        k :longint;
        p :qword;
begin
        assign(input,fi);
        reset(input);
                k:=0;
                while not seekeof() do
                begin
                        inc(k);
                        while not seekeoln() do
                        begin
                                inc(n[k]);
                                read(p);
                                a[k,n[k]]:=p;
                        end;
                        readln;
                end;
        close(input);
end;
procedure sang;
var     i,j     :longint;
begin
        for i:=2 to trunc(sqrt(maxc)) do
        if g[i]=0 then
        begin
                j:=i*I;
                while j<=maxc do
                begin
                        g[j]:=i;
                        inc(j,i);
                end;
        end;
        for i:=2 to maxc do
        if g[i]=0 then
        begin
                inc(mp);
                nto[mp]:=i;
        end;
end;
function find(x:qword):boolean;
var     d,c,mid   :longint;
        t1,t2,t3      :qword;
begin
        d:=1; c:=mp;
        while d<=c do
        begin
                mid:=(d+c) div 2;
                t1:=x mod nto[mid];
                t2:=x div nto[mid];
                t3:=nto[mid]*nto[mid];
                if (t1=0) and (t2=t3) then exit(true);
                if (t3>t2) then c:=mid-1
                else d:=mid+1;
        end;
        exit(false);
end;
function kt(x:qword):boolean;
var     x1      :qword;
begin
        x1:=trunc(sqrt(x));
        if x1*x1=x then exit(true);
        if find(x) then exit(true);
        exit(false);
end;
procedure xuli;
var     i,j     :longint;
begin
        for i:=1 to n[1] do
        for j:=1 to n[2] do
        if (a[1,i]=a[2,j]) and kt(a[1,i]) then f[i,j]:=f[i-1,j-1]+1
        else f[i,j]:=max(f[i-1,j],f[i,j-1]);
end;
procedure xuat;
begin
        assign(output,fo);
        rewrite(output);
                writeln(f[n[1],n[2]]);
        close(Output);
end;
begin
        nhap;
        sang;
        xuli;
        xuat;
end.