BONUS13 – spoj

Đề bài:

Thuật toán:

Code:

uses    math;
const   fi='';
        fo='';
        maxn=80;
        n=8;
        hx:array[1..8] of integer=(-1,-2,-2,-1,1,2,2,1);
        hy:array[1..8] of integer=(-2,-1,1,2,2,1,-1,-2);
type    point=record
                x,y:byte;
                end;
var     cx,dx:array[1..maxn] of point;
        a:array[1..8,1..8] of boolean;
        c:array[1..maxn] of longint;
        i,j,k:longint;
        top1,top2:longint;
        hau,xe,ma,tuong:array[1..maxn,1..maxn] of boolean;
        m,t,x,h : longint;
        res:int64;
procedure nhap;
var     u,v:byte;
        w:longint;
begin
    assign(input,fi);reset(input);
    readln(k);
    for i:=1 to k do
        begin
            readln(u,v,w);
            a[u,v]:=true;
            inc(top1); dx[top1].x:=u; dx[top1].y:=v; c[top1]:=w;
        end;
    close(input);
end;
procedure init;
begin
    res:=0;
    for i:=1 to 8 do
        for j:=1 to 8 do
                if a[i,j]=false then
                        begin
                               inc(top2);
                               cx[top2].x:=i;
                               cx[top2].y:=j;
                        end;
end;
function chau(i,j:longint):boolean;
begin
    if cx[i].x=dx[j].x then exit(true);
    if cx[i].y=dx[j].y then exit(true);
    if (cx[i].x+cx[i].y)=(dx[j].x+dx[j].y) then exit(true);
    if (cx[i].x-cx[i].y)=(dx[j].x-dx[j].y) then exit(true);
    exit(false);
end;
function cxe(i,j:longint):boolean;
begin
    if cx[i].x=dx[j].x then exit(true);
    if cx[i].y=dx[j].y then exit(true);
    exit(false);
end;
function ctuong(i,j:longint):boolean;
begin
    if (cx[i].x+cx[i].y)=(dx[j].x+dx[j].y) then exit(true);
    if (cx[i].x-cx[i].y)=(dx[j].x-dx[j].y) then exit(true);
    exit(false);
end;
function cma(i,j:longint):boolean;
var     k,u,v:integer;
begin
    for k:=1 to 8 do
        begin
            u:=cx[i].x+hx[k];
            v:=cx[i].y+hy[k];
            if (u=dx[j].x) and (v=dx[j].y) then exit(true);
        end;
    exit(false);
end;
procedure xuly;
var     i,j:longint;
begin
    for i:=1 to top2 do
        for j:=1 to top1 do
         begin
          if chau(i,j) then hau[i,j]:=true;
          if cxe(i,j) then xe[i,j]:=true;
          if cma(i,j) then ma[i,j]:=true;
          if ctuong(i,j) then tuong[i,j]:=true;
         end;
end;
procedure main;
var     tam:int64;
begin
    for h:=1 to top2 do
        for x:=1 to top2 do
                if h<>x then
                        for m:=1 to top2 do
                                if (m<>h) and (m<>x) then
                                        for t:=1 to top2 do
                                                if (m<>t) and (t<>x) and (t<>h) then
                                                  begin
                                                        tam:=0;
                                                        for i:=1 to top1 do
                                                                if hau[h,i] or xe[x,i] or ma[m,i] or tuong[t,i] then tam := tam + c[i];
                                                        res:=max(res,tam);
                                                  end;
 
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(res);
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    main;
    inkq;
end.
#include <iostream>
#include <vector>
using namespace std;
#define LL long long
#define rep(i, a, b) for (int i=a; i<b; i++)
 
struct pack {int x, y; LL w;};
 
inline LL calc(LL state, vector<pack>& a) {
    LL res = 0;
    for (auto &x: a) {
        if (state & 1) res += x.w;
        state >>= 1;
    }
    return res;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int m; cin >> m;
    vector<pack> a(m);
    vector<bool> frei(64, true);
    for (auto &a: a) {
        cin >> a.x >> a.y >> a.w;
        a.x--, a.y--;
        frei[a.x*8+a.y] = false;
    }
    vector<LL> xe(64, 0), tuong(64, 0), ma(64, 0), hau(64, 0);
    int c = 0;
    rep(i, 0, 8) rep(j, 0, 8) if (frei[c]) {
        rep(k, 0, m) {
            int x = a[k].x, y = a[k].y;
            if (x==i || y==j) xe[c] |= 1ll<<k;
            if (x-y==i-j || x+y==i+j) tuong[c] |= 1ll<<k;
            if ((abs(i-x)==2&&abs(j-y)==1) || (abs(i-x)==1&&abs(j-y)==2)) {
                ma[c] |= 1ll<<k;
            }
        }
        hau[c] = xe[c] | tuong[c];
        c++;
    } else c++;
 
    LL kq = 0;
    rep(h, 0, 64) if (frei[h]) {
        LL s = hau[h];
        frei[h] = false;
        rep(x, 0, 64) if (frei[x]) {
            LL bk = s;
            s |= xe[x];
            frei[x] = false;
            rep(t, 0, 64) if (frei[t]) {
                LL bk = s;
                frei[t] = false;
                s |= tuong[t];
                rep(m, 0, 64) if (frei[m]) {
                    kq = max(kq, calc(s | ma[m], a));
                }
                frei[t] = true;
                s = bk;
            }
            frei[x] = true;
            s = bk;
        }
        frei[h] = true;
    }
    cout << kq << endl;
    return 0;
}

C11CAVE – spoj

Đề bài:

Thuật toán:

  • Chỉ cần duyệt từ 1 đến h rồi kiểm tra, bạn đọc code bên dưới sẽ hiểu.

Code:

    const           fi      = '';
                    fo      = '';
                    maxn    = 1000000;
 
    var
                    n , h   : longint;
                    m       : longint;
                    d , c   : array[ 0..maxn ] of longint;
 
    procedure   enter;
        var
                i           : longint;
                u , v       : longint;
        begin
                read( n , h );
                m := n div 2;
                for i := 1 to m do
                  begin
                    read( u , v );
                    inc( d[ u ] );
                    inc( c[ v ] );
                  end;
        end;
 
    procedure   prepair;
        var
                i           : longint;
        begin
                for i := 1 to h do
                  begin
                    d[ i ] := d[ i-1 ] + d[ i ];
                    c[ i ] := c[ i-1 ] + c[ i ];
                  end;
        end;
 
 
    procedure   solve;
        var
                res , num   : longint;
                i , tmp     : longint;
        begin
                res := n+1;
                num := 0;
                for i := 1 to h do
                  begin
                    tmp := d[ h ] - d[ i-1 ] + c[ h ] - c[ h-i ];
                    if res > tmp then
                      begin
                        res := tmp;
                        num := 1;
                      end
                    else
                      if res = tmp then inc( num );
                  end;
                writeln( res , ' ' , num );
        end;
 
 
 
    BEGIN
 
                assign( input , fi ); reset( input );
                assign( output , fo ); rewrite( output );
 
                enter;
                prepair;
                solve;
 
                close( input ); close( output );
 
    END.

NKNUMFRE – spoj

Đề bài:

Thuật toán:

  • Vét cạn.

Code:

const
  fi='';
  fo='';
var
  a,b,i,j,dem,num : longint;
procedure swap(var x,y : char);
  var tg :char;
  begin
    tg:=x;x:=y;y:=tg;
  end;
function gcd(a,b : longint) : longint;
  var r : longint;
  begin
    while b>0 do
      begin
        r := a mod b;
        a:=b;
        b:=r;
      end;
    exit(a);
  end;
function dao(x : longint) : longint;
  var s : string;
      y : longint;
  begin
    str(x,s);
    i:=1;j:=length(s);
    while i<j do
      begin
        swap(s[i],s[j]);
        inc(i);dec(j);
      end;
    val(s,y);
    exit(y);
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(a,b);
  for num := a to b do
    if gcd(dao(num),num)=1 then inc(dem);
  writeln(dem);
  close(input);close(output);
end.

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.