VOMOVREC – SPOJ

February 22, 2016 by Leave a Comment

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

Thuật toán: Ta sẽ tìm kiếm nhị phân kết quả của bài toán. Với mỗi giá trị chia nhị phân V, ta sẽ “nở” các hình chữ nhật ra về bốn phía một độ dài bằng V. Lúc này điều kiện cần và đủ để tất cả các hình chữ nhật ban đầu có thể di chuyển với khoảng cách không quá V thỏa mãn yêu cầu là tất cả các hình chữ nhật đã được nở có phần giao. Điều kiện N hình chữ nhật có phần giao chung hay không là max(X1) < min(X2) và max(Y1) < min(Y2).

Code:

uses math;
const
  fi='';//vomovrec.inp';
  fo='';//vomovrec.out';
  maxn=trunc(1e6);
  oo=trunc(1e9)*3;
type
  rect = record
    x1,y1,x2,y2 : int64;
    end;
var
  m,n,i,j : longint;
  a : array[1..maxn] of rect;
  d,c,g : int64;
function ok(k : int64) : boolean;
  var i : longint;
      x,y,u,v : int64;
  begin
    x := a[1].x1 - k;
    y := a[1].y1  - k;
    u := a[1].x2  +k;
    v := a[1].y2 + k;
    for i := 2 to n do
      with a[i] do
      begin
        x := max(x, x1-k);
        y := max(y, y1-k);
        u := min(u, x2+k);
        v := min(v, y2+k);
      end;
    if (xc) and (g<>d) do
    begin
      if ok (g) then c := g else d := g;
      g := (d+c) div 2;
    end;if ok(d) then
      begin
        write(d);
        exit;
      end;
     writeln(c);
  close(input);
  close(output);
end.
Chủ đề: SPOJ, Thuật toán, Tìm kiếm nhị phân Mức độ: ,

NKMINES – SPOJ

February 12, 2016 by 1 Comment

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

Thuật toán:

  • Duyệt trạng thái hàng 1 và cột 1 từ đó lần ra được các ô khác.
  • Nếu trạng thái mìn thỏa mãn thì xuất ra và dừng chương trình luôn.

Code:

const h1: array[1..8] of integer = (1, -1, 0, 0, 1, -1, 1, -1);
      h2: array[1..8] of integer = (0, 0, 1, -1, 1, -1, -1, 1);

var a, res: array[0..201, 0..201] of byte;
    m, n: byte;

procedure init;
  var i, j: integer;
  begin
       fillchar(res, sizeof(res), 0);
       readln(m, n);
       for i:= 1 to m do
          begin
               for j:= 1 to n do read(a[i, j]);
               readln;
          end;
  end;

function count(i, j: byte): byte;
  var tmp, k: byte;
  begin
       tmp:= 0;
       for k:= 1 to 8 do
          if res[i + h1[k], j + h2[k]] = 1 then inc(tmp);
       exit(tmp);
  end;

function fill(i, j: byte): boolean;
  var t1, t2: integer;
  begin
       if (i = 1) or (j = 1) then exit(true);
       if (i > m) or (j > n) then exit(true);
       res[i, j]:= 0;

       t1:= a[i - 1, j - 1] - count(i - 1, j - 1);
       if t1 < 0 then exit(false);
       if t1 > 1 then exit(false);

       {if j = n then
         begin
              t2:= a[i - 1, j] - count(i - 1, j);
              if t2 <> t1 then exit(false);
         end;

       if i = m then
         begin
              t2:= a[i, j - 1] - count(i, j - 1);
              if t2 <> t1 then exit(false);
         end;}

       res[i, j]:= t1;
       exit(true);
  end;

procedure printres;
  var i, j: byte;
  begin
       for i:= 1 to m do
          begin
               for j:= 1 to n do write(res[i, j],' ');
               writeln;
          end;
       halt;
  end;

procedure attempt(i: byte);
  var p, q, u: byte;
      ok: boolean;
  begin
       for p:= 0 to 1 do
          for q:= 0 to 1 do
             begin
                  res[i, 1]:= p;
                  res[1, i]:= q;
                  ok:= true;
                  for u:= 1 to i do
                     if (not fill(u, i)) or (not fill(i, u)) then
                       begin
                            ok:= false;
                            break;
                       end;
                  if not ok then continue;
                  if (i >= m) and (i >= n) then printres;
                  attempt(i + 1);
             end;
  end;

begin
     init;
     attempt(1);
end.
Chủ đề: Đệ quy, SPOJ, Thuật toán Mức độ:

GRAPH_ – SPOJ

February 9, 2016 by Leave a Comment

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

Thuật toán: Đây là bài tập cơ bản về thuật toán tìm cầu, khớp. Bạn có thể tham khảo thuật toán trong ebook Giải thuật và lập trình của thầy Lê Minh Hoàng.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=10000;
  maxm=50000;
  oo=trunc(1e9);
var
  link,head,ke : array[-maxm..maxm] of longint;
  i,j,n,m,kq1,kq2 : longint;
  cau,khop : longint;
  iscut : array[1..maxn] of boolean;
  count : longint;
  cha,num,low : array[1..maxn] of longint;
  free : array[-maxm..maxm] of boolean;
  nchild : array[1..maxn] of longint;
procedure add(i,u,v:longint);
begin
    link[i] :=head[u];
    head[u] := i;
    ke[i]:=v;
end;
procedure enter;
var u,v : longint;
begin
   assign(input,fi);reset(input);
   readln(n,m);
   for i:=1 to m do
     begin
         read(u,v);
         add(i,u,v);
         add(-i,v,u);
     end;
   close(input);
end;
procedure dfs(u:longint);
var i,j,v : longint;
begin
   inc(count);
   num[u]:=count;
   low[u]:=oo;
   i := head[u];
   while i<>0 do
     begin
         if free[i] then
         begin
         v := ke[i];
         free[-i] := false;
         if cha[v]=0 then
           begin
               cha[v]:=u;
               dfs(v);
               low[u] := min(low[v],low[u]);
           end
           else
           begin
               low[u] := min(low[u],num[v]);
           end;
         end;
         i := link[i];
     end;
end;
procedure process;
var i,u,v : longint;
begin
    fillchar(free,sizeof(free),true);
    fillchar(cha,sizeof(cha),0);
    for i:=1 to n do
        if cha[i]=0 then
          begin
              cha[i] := -1;
              dfs(i);
          end;
    for v:=1 to n do
      begin
          u:=cha[v];
          if (u<>-1) and (low[v]>=num[v]) then
                begin
                    inc(cau);
                end;
      end;
    for v:=1 to n do
      if cha[v]<>-1 then
        begin
          inc(nchild[cha[v]]);
        end;
    fillchar(iscut,sizeof(iscut),false);
    for v:=1 to n do
        if cha[v] <> -1 then
        begin
          u := cha[v];
          if low[v]>=num[u] then
            iscut[u]:= iscut[u] or (cha[u]<>-1) or (nchild[u]>=2);
        end;
    for v:=1 to n do
      if iscut[v] then inc(khop);
end;
procedure print;
begin
    assign(output,fo);rewrite(output);
    writeln(khop,' ',cau);
    close(output);
end;
begin
    enter;
    process;
    print;
end.
Chủ đề: DFS, SPOJ, Thuật toán Mức độ: