Các hàm làm tròn số trong C++

May 13, 2017 by Leave a Comment 
value   round   floor   ceil    trunc
-----   -----   -----   ----    -----
2.3     2.0     2.0     3.0     2.0
3.8     4.0     3.0     4.0     3.0
5.5     6.0     5.0     6.0     5.0
-2.3    -2.0    -3.0    -2.0    -2.0
-3.8    -4.0    -4.0    -3.0    -3.0
-5.5    -6.0    -6.0    -5.0    -5.0

Hàm round(x)

Làm tròn về số nguyên gần nhất so với số thực x.

Hàm trunc(x)

Trả về số thực có giá trị bằng phần nguyên của x.

Hàm ceil(x)

Làm tròn lên số thực x. Trả về số thực có giá trị bằng số nguyên nhỏ nhất lớn hơn hoặc bằng x.

Hàm floor(x)

Làm tròn xuống số thực x. Trả về số thực có giá trị bằng số nguyên lớn nhất nhỏ hơn hoặc bằng x.

 

Chú ý: Tất cả các hàm trên đều thuộc thư viện cmath. Bạn phải khai báo thư viện này trước khi sử dụng các hàm trên.

Chủ đề: C++, Ngôn ngữ lập trình

AZNET – spoj

December 4, 2016 by Leave a Comment

Đề bài:

Thuật toán:

Code:

Const   inp = '';
        out = '';
        maxn = 10001;
        maxm = 100001;
 
Var     n,m,ntest,min,max,k,res     :       longint;
        x,y,id :       array [1..2,1..maxm] of longint;
        lab :       array [1..2,1..maxn] of longint;
        sl      :   array [1..2] of longint;
        a,b :       array [0..maxn] of longint;
{***************************************************************************}
function getroot(t,u : longint) : longint;
  begin
      while lab[t,u] > 0 do u := lab[t,u];
      exit(u);
  end;
{***************************************************************************}
procedure union(t,r1,r2 : longint);
var x : longint;
  begin
      x := lab[t,r1]+lab[t,r2];
      if lab[t,r1] > lab[t,r2] then
       begin
           lab[t,r1] := r2;
           lab[t,r2] := x;
       end
      else begin
               lab[t,r2] := r1;
               lab[t,r1] := x;
           end;
  end;
{****************************************************************************}
procedure main;
var i,j,dem,u,v,r1,r2,r3,r4 : longint;
  begin
      for i := 1 to n do
        begin
            lab[1,i] := -1;
            lab[2,i] := -1;
        end;
      max := 0;
      for i := 1 to sl[1] do
        begin
           u := x[1,i]; v := y[1,i];
           r1 := getroot(1,u); r2 := getroot(1,v);
           if r1 <> r2 then
             begin
                 inc(max);
                 union(1,r1,r2);
             end;
        end;
      min := 0;
      for i := 1 to sl[2] do
        begin
            u := x[2,i]; v := y[2,i];
            r1 := getroot(1,u); r2 := getroot(1,v);
            if r1 <> r2 then
              begin
                inc(min);
                union(1,r1,r2);
                r3 := getroot(2,u); r4 := getroot(2,v);
                union(2,r3,r4);
              end;
        end;
      for i := 1 to sl[2] do
        begin
            u := x[2,i]; v := y[2,i];
            r1 := getroot(2,u); r2 := getroot(2,v);
            if r1 <> r2 then
              begin
                  inc(min);
                  union(2,r1,r2);
              end;
        end;
      min := n-1-min;
      res := maxlongint;
      for i := min to max do
        if a[i]+b[n-1-i] < res then
          begin
              res := a[i]+b[n-1-i];
              k := i;
          end;
      for i := 1 to n do
        begin
            lab[1,i] := -1; lab[2,i] := -1;
        end;
      for i := 1 to sl[1] do
        begin
           u := x[1,i]; v := y[1,i];
           r1 := getroot(1,u); r2 := getroot(1,v);
           if r1 <> r2 then union(1,r1,r2);
        end;
      dem := 0;
      for i := 1 to sl[2] do
        begin
            u := x[2,i]; v := y[2,i];
            r1 := getroot(1,u); r2 := getroot(1,v);
            if r1 <> r2 then
              begin
                write(id[2,i],' ');
                inc(dem);
                union(1,r1,r2);
                r3 := getroot(2,u); r4 := getroot(2,v);
                union(2,r3,r4);
              end;
        end;
      if dem < n-1-k then
        begin
           for i := 1 to sl[2] do
            begin
                u := x[2,i]; v := y[2,i];
                r1 := getroot(2,u); r2 := getroot(2,v);
                if r1 <> r2 then
                 begin
                     inc(dem);
                     write(id[2,i],' ');
                     union(2,r1,r2);
                     if dem=n-1-k then break;
                 end;
            end;
        end;
      for i := 1 to sl[1] do
        begin
          u := x[1,i]; v := y[1,i];
          r1 := getroot(2,u); r2 := getroot(2,v);
          if r1 <> r2 then
            begin
                write(id[1,i],' ');
                union(2,r1,r2);
            end;
        end;
      writeln;
  end;
{***************************************************************************}
procedure nhap;
var i,j,u,v,k : longint;
  begin
      assign(input,inp); reset(input);
      assign(output,out); rewrite(output);
      readln(ntest);
      while ntest > 0 do
       begin
           dec(ntest);
           readln(n,m);
           for i := 1 to n-1 do read(a[i]);
           for i := 1 to n-1 do read(b[i]);
           sl[1] := 0; sl[2] := 0;
           for i := 1 to m do
             begin
                 readln(u,v,k);
                 inc(sl[k]);
                 x[k,sl[k]] := u; y[k,sl[k]] := v;
                 id[k,sl[k]] := i;
             end;
           main;
       end;
  end;
{****************************************************************************}
begin
     nhap;
end.
Chủ đề: Đồ thị, Kruskal

C11TRCNT – spoj

December 2, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Bài toán đưa về: kiểm tra 3 điểm có thẳng hàng hay không

Code:

const   fi='';
        fo='';
type    dinh=record
                x,y:longint;
                end;
var     i,j,k:integer;
        d,max,min:int64;
        kq,n:byte;
        p:array[1..200] of dinh;
        dem:array[1..200] of int64;
        f:text;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n);
    for i:=1 to n do readln(f,p[i].x,p[i].y);
    close(f);
end;
function kt(x1,y1,x2,y2,x3,y3:longint):boolean;
begin
        if x1*y3-x1*y2+x2*y1-x2*y3+x3*y2-x3*y1=0
        then exit(false) else exit(true);
end;
procedure xuly;
begin
    d:=0; min:=1000000000000000;
    for i:=1 to n do
    begin
        for j:=1 to n do
        if i<>j then
                for k:=1 to n do
                if (i<>k) and (j<>k) then
                                if kt(p[i].x,p[i].y,p[j].x,p[j].y,p[k].x,p[k].y)  then
                                begin
                                        inc(dem[i]);
                                        if (ij) then inc(d);
                                end;
        if dem[i]
Chủ đề: Hình học, SPOJ Mức độ:

LCS2X – spoj

December 2, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Gọi L[i,j] là độ dài dãy con chung bội hai dài nhất với số cuối cùng là A[i] và B[j]1) Với A[i] <> B[j] thì L[i,j] = 0

    2) Với A[i] = B[j] thì L[i,j] = max(L[x,y] + 1) ( với x<i, y<j, A[x]*2 <= A[i] )

  • Để tính max(L[x,y]) nhanh chóng, ta sử dụng mảng F với ý nghĩa:F[y] = max(L[x,y])   =>Kết quả là max(F[j]) (với 1<=j<=n)

    Gọi ma=max(F[y]) ( với y<j, B[y]*2 <= A[i] )

    Khi đó ta có đoạn code phần xử lý sẽ là:

    for (i=1;i<=m;++i){
        ma=0;
        for (j=1;j<=n;++j){
            matruocj=ma;
            if (b[j]*2<=a[i]) ma=max(ma,f[j]);
            if (a[i]==b[j]) f[j]=max(f[j],matruocj+1);
        }
    }
  • Với cách này thì bạn chỉ cần dùng mảng 1 chiềuĐộ phức tạp: O(M*N)

Code:

uses    math;
const   fi      ='';
        fo      ='';
        oo      =trunc(1e4);

var     a, b, f :array[0..oo] of longint;
        ma,matruocj     :longint;
        ans     :longint;
        m, n    :longint;
procedure Optimize;
var     i, j    :longint;
begin
        fillchar(f, sizeof(f),0);
        for i:=1 to m do
                begin
                        ma:=0;
                        for j:=1 to n do
                                begin
                                        matruocj:=ma;
                                        if b[j]*2<=a[i] then ma:=Max(ma,f[j]);
                                        if b[j]=a[i] then f[j]:=max(f[j],matruocj+1);
                                end;
                 end;

end;

Procedure run;
var     i, t,l :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(t);
        for l:=1 to t do
                begin
                        readln(m, n);
                        for i:=1 to m do read(a[i]);
                        for i:=1 to n do read(b[i]);
                        Optimize;
                        ans:=0;
                        for i:=1 to n do
                                if f[i]>ans then ans:=f[i];
                        writeln(ans);
                end;
        close(input);close(output);
end;

begin
        run;
end.
Chủ đề: Quy hoạch động, SPOJ Mức độ:

Đề thi, đáp án, kết quả PreVOI 2016

December 1, 2016 by Leave a Comment
Chủ đề: Ngôn ngữ lập trình