C11SEQ3 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
        tfi='';//c11seq3.inp';
        tfo='';//c11seq3.out';
 
var
        fi,fo:text;
        n:longint;
        f:array[0..24]of qword;
        t:array[0..5] of qword=(244445,48889, 77789, 155578, 111356, 122227);
 
procedure dao(i:longint);
        var s:string;
                tg:char;
                i1,j,code:longint;
        begin
                str(f[i],s);
                for i1:=1 to length(s)-1 do
                        for j:=i1+1 to length(s) do
                                if s[i1]>s[j] then
                                        begin
                                                tg:=s[i1];
                                                s[i1]:=s[j];
                                                s[j]:=tg;
                                        end;
                val(s,f[i],code);
        end;
 
procedure xuli;
        var i:longint;
        begin
                read(fi,n);
                f[1]:=1;
                for i:=2 to 24 do
                        begin
                                f[i]:=f[i-1]*2;
                                dao(i);
                        end;
                if n<=24 then write(f[n])
                else writeln(fo,t[n mod 6]);
        end;
 
 
begin
        assign(fi,tfi);
        assign(fo,tfo);
        reset(Fi);
        rewrite(fo);
        xuli;
        close(fo);
end.

VOTREE – spoj

Đề bài:

Giải thích ví dụ

votree-yeulaptrinh
Truy vấn 1: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 2 đến 5, ở đây có thể thấy 2 là tổ tiên chung gần nhất của các đỉnh 2,3,4,5.
Truy vấn 2: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 1 đến 3, ở đây có thể thấy 1 là tổ tiên chung gần nhất của các đỉnh 1,2,3.
Truy vấn 3: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 4 đến 5, ở đây có thể thấy 3 là tổ tiên chung gần nhất của các đỉnh 4,5.

Thuật toán:

    Có thể nhận thấy rằng tổ tiên chung gần nhất ( LCA ) của 3 đỉnh a,b,c sẽ bằng với LCA(a,LCA(c,b)). Dựa trên tính chất nãy ta có thể sử dụng Interval Tree để tìm LCA của 1 đoạn liên tiếp bằng cách tổ chức cây IT sẽ lưu LCA của các phần tử trong đoạn quản lý.

    Các phần cơ bản của cây IT:

    IT[id] = phần tử đang được quản lý khi đoạn quản lý gồm 1 phần tử.

    IT[id] = LCA(IT[id*2],IT[id*2+1] ).

    P/s : Có rất nhiều cách để tìm LCA ví dụ như : Sparse Table, Heavy Light Decomposition, Interval Tree, …

Code:

const
        tfi='';
        tfo='';
 
var
        fi,fo:Text;
        ke,nx:array[-70000..70000] of longint;
        num,thoat,hd:array[0..70000] of longint;
        f:array[0..70000,0..20] of longint;
        n,q,jmax,dem,dem1:longint;
        t:array[0..3000000] of longint;
 
procedure nhap;
        var i,j,u,v:longint;
        begin
                read(fi,n,q);
                for i:=1 to n-1 do
                        begin
                                read(fi,u,v);
                                ke[i]:=v;
                                nx[i]:=hd[u];
                                hd[u]:=i;
                                ke[-i]:=u;
                                nx[-i]:=hd[v];
                                hd[v]:=-i;
                        end;
                for j:=1 to 20 do if 1 shl j<=n then jmax:=j+1;
        end;
 
procedure DFS(u:longint);
        var j,v:longint;
        begin
                inc(dem);
                num[u]:=dem;
                for j:=1 to jmax do f[u,j]:=f[f[u,j-1],j-1];
                j:=hd[u];
                while j<>0 do
                        begin
                                v:=ke[j];
                                if f[v,0]=0 then
                                        begin
                                                f[v,0]:=u;
                                                DFS(v);
                                        end;
                                j:=nx[j];
                        end;
                inc(dem1);
                thoat[u]:=dem1;
        end;
 
function cha(x,y:longint):boolean;
        begin
            cha:=(num[x]<=num[y]) and (thoat[y]<=thoat[x]);
        end;
 
function lca(x,y:longint):longint;
        var j:longint;
        begin
                if cha(x,y) then exit(x);
                if cha(y,x) then exit(y);
                for j:=jmax downto 0 do
                        if not cha(f[x,j],y) then x:=f[x,j];
                exit(f[x,0]);
        end;
 
procedure init(i,l,r:longint);
        var mid:longint;
        begin
            if l=r then
                begin
                        t[i]:=l;
                        exit;
                end;
            mid:=(l+r) div 2;
            init(i*2,l,mid);
            init(i*2+1,mid+1,r);
            t[i]:=lca(t[i*2],t[i*2+1]);
        end;
 
function get(i,l,r,u,v:longint):longint;
        var mid:longint;
        begin
                if (l>v) or (r<u) then exit(u);
                if (u<=l) and (r<=v) then exit(t[i]);
                mid:=(l+r) div 2;
                get:=lca(get(i*2,l,mid,u,v),get(i*2+1,mid+1,r,u,v));
        end;
 
procedure xuli;
        var i,u,v,pa,j:longint;
        begin
                f[1,0]:=1;
                DFS(1);
                init(1,1,n);
                for i:=1 to q do
                        begin
                                read(fi,u,v);
                                writeln(fo,get(1,1,n,u,v));
                        end;
 
        end;
 
begin
        assign(fi,tfi);
        assign(fo,tfo);
        reset(fi);
        rewrite(fo);
        nhap;
        xuli;
        close(fo);
end.

Nhập, xuất dữ liệu từ file trong C++

Tất cả các chương trình mà ta đã gặp trong cuốn sách này đều lấy dữ liệu vào từ bàn phím và in ra màn hình. Nếu chỉ dùng bàn phím và màn hình là các thiết bị vào ra dữ liệu thì chương trình của ta khó có thể xử lý được khối lượng lớn dữ liệu, và kết quả chạy chương trình sẽ bị mất ngay khi ta đóng cửa sổ màn hình output hoặc tắt máy. Để cải thiện tình trạng này, ta có thể lưu dữ liệu  tại  các thiết bị lưu trữ thứ cấp mà thông dụng nhất thường là ổ đĩa cứng. Khi đó dữ liệu tạo bởi một chương trình có thể được lưu lại để sau này được sử dụng bởi chính nó hoặc các chương trình khác. Dữ liệu lưu trữ như vậy được đóng gói tại các thiết bị lưu trữ thành các cấu trúc dữ liệu gọi là tp (file).

Chương này sẽ giới thiệu về cách viết các chương trình lấy dữ liệu vào (từ bàn phím hoặc từ một tệp) và ghi dữ liệu ra (ra màn hình hoặc một  tệp).

Khái niệm dòng dữ liệu

Trong một số ngôn ngữ lập trình như C++ và Java, dữ liệu vào ra từ tệp, cũng  như từ bàn phím và màn hình, đều được vận hành thông qua các dòng dliu (stream). Ta có thể coi dòng dữ liệu là một kênh hoặc mạch dẫn  mà  dữ  liệu được truyền qua đó để chuyển từ nơi gửi đến nơi nhận.

Dữ liệu được truyền từ chương trình ra ngoài theo một dòng ra (output stream). Đó có thể là dòng ra chuẩn nối và đưa dữ liệu ra màn hình, hoặc dòng ra nối với một tệp và đẩy dữ liệu ra tệp đó.

Chương trình nhận dữ liệu vào qua một dòng vào (input stream). Dòng vào thì có thể là dòng vào chuẩn nối và đưa dữ liệu vào từ màn hình, hoặc dòng vào nối với một tệp và nhận dữ liệu vào từ tệp đó.

Dữ liệu vào và ra có thể là các kí tự, số, hoặc các byte chứa các chữ số nhị  phân.

Trong C++, các dòng vào ra được cài đặt bằng các đối tượng của các lớp dòng vào ra đặc biệt. Ví dụ, cout mà ta vẫn dùng để ghi ra màn hình chính là dòng ra chuẩn, còn cin là dòng vào chuẩn nối với bàn phím. Cả hai đều là các đối tượng dòng dữ liệu (khái niệm “đối tượng” này có liên quan đến tính năng hướng đối tượng của C++, khi nói về các dòng vào/ra của C++, ta sẽ phải đề cập nhiều đến tính năng này).

Tp văn bn và tp nhphân

Về bản chất, tất cả dữ liệu trong các tệp đều được lưu trữ dưới dạng một chuỗi các bit nhị phân 0 và 1. Tuy nhiên, trong một số hoàn cảnh, ta không  coi nội dung của một tệp là một chuỗi 0 và 1 mà coi tệp đó là một chuỗi các kí tự. Một   số tệp được xem như là các chuỗi kí tự và được xử lý bằng các dòng và hàm cho phép chương trình và hệ soạn thảo văn bản của bạn nhìn các chuỗi nhị phân như là các chuỗi kí tự. Chúng được gọi là các tp văn bn (text file). Những tệp không phải tệp văn bản là tp nhphân (binary file). Mỗi loại tệp được xử lý   bởi các dòng và hàm riêng.

Chương trình C++ của bạn được lưu trữ trong tệp văn bản. Các tệp ảnh và nhạc  là các tệp nhị phân. Do tệp văn bản là chuỗi kí tự, chúng thường trông giống nhau tại các máy khác nhau, nên ta có thể chép chúng  từ  máy này sang  máy khác mà không gặp hoặc gặp phải rất ít rắc rối. Nội dung của các tệp nhị phân thường lấy cơ sở là các giá trị số, nên việc sao chép chúng giữa các máy có thể gặp rắc rối do các máy khác nhau có thể dùng các quy cách lưu trữ số không giống nhau. Cấu trúc của một số dạng tệp nhị phân đã được chuẩn hóa để chúng có thể được sử dụng thống nhất tại các platform khác nhau. Nhiều dạng tệp ảnh và âm thanh thuộc diện này.

Mỗi kí tự trong một tệp văn bản được biểu diễn bằng 1 hoặc 2 byte, tùy theo đó  là kí tự ASCII hay Unicode. Khi một chương trình viết một giá trị vào một tệp văn bản, các kí tự được ghi ra tệp giống hệt như khi chúng được ghi ra màn hình bằng cách sử dụng cout. Ví dụ, hành động viết số 1 vào một tệp sẽ dẫn đến kết quả là 1 kí tự được ghi vào tệp, còn với số 1039582 là 7 kí tự được ghi vào  tệp.

Các tệp nhị phân lưu tất cả các giá trị thuộc một kiểu dữ liệu cơ bản theo cùng một cách, giống như cách dữ liệu được lưu trong bộ nhớ máy tính. Ví dụ, mỗi  giá trị int bất kì, 1 hay 1039582 đều chiếm một chuỗi 4 byte.

 Vào ra tệp

C++ cung cấp các lớp sau để thực hiện nhập và xuất dữ liệu đối với  tệp:

  • ofstream: lớp dành cho các dòng ghi dữ liệu ra tệp
  • ifstream: lớp dành cho các dòng đọc dữ liệu từ tệp
  • fstream: lớp dành cho các dòng vừa đọc vừa ghi dữ liệu ra tệp.

Đối tượng thuộc các lớp này do quan hệ thừa kế nên cách sử dụng chúng khá giống với cin và cout – các đối tượng thuộc lớp istream và ostream – mà chúng ta đã dùng. Khác biệt chỉ là ở chỗ ta phải nối các dòng đó với các  tệp.

c-p-yeulaptrinh.pw

Hình 8.1: Các thao tác cơ bn vi tp văn bn.

Chương trình trong Hình 8.1 tạo một tệp có tên hello.txt và ghi vào đó một câu “Hello!” theo cách mà ta thường làm đối với cout, chỉ khác ở chỗ thay cout bằng đối tượng dòng myfile đã được nối với một tệp. Sau đây là các bước thao tác với tệp.

  • Mở tệp

Việc đầu tiên là nối đối tượng dòng với một tệp, hay nói cách khác là mở một  tệp. Kết quả là đối tượng dòng sẽ đại diện cho tệp, bất kì hoạt động đọc và ghi  đối với đối tượng đó sẽ được thực hiện đối với tệp mà nó đại diện. Để mở một  tệp từ một đối tượng dòng, ta dùng hàm open của nó:

open (fileName, mode);


Trong đó, fileName là một xâu kí tự thuộc loại const char * với kết thúc là kí tự null (hằng xâu kí tự cũng thuộc dạng này), là tên của tệp cần mở, và mode là tham số không bắt buộc và là một tổ hợp của các cờ  sau:

ios::in     mở để đọc

ios::out    mở để ghi

ios::binary  mở ở dạng tệp nhị  phân

ios::ate    đặt ví trí bắt đầu đọc/ghi tại cuối tệp. Nếu cờ này không được đặt giá trị gì, vị trí khởi đầu sẽ là đầu tệp.

ios::app    mở để ghi tiếp vào cuối tệp. Cờ này chỉ được dùng  cho dòng mở tệp chỉ để ghi.

ios::trunc   nếu tệp được mở để ghi đã có từ trước, nội dung cũ sẽ bị  xóa

để ghi nội dung mới.
Các cờ trên có thể được kết hợp với nhau bằng toán tử bit OR (|). Ví dụ, nếu ta muốn mở tệp people.dat theo dạng nhị phân để ghi bổ sung dữ liệu vào cuối tệp, ta dùng lời gọi hàm sau:

ofstream myfile;
myfile.open ("people.dat",
   ios::out | ios::app | ios::binary);
Trong trường hợp lời gọi hàm open không cung cấp tham số mode, chẳng hạn Hình 8.1, chế độ mặc định cho dòng loại ostream là ios::out, cho dòng loại istream là ios::in, và cho dòng loại fstream là ios::in | ios::out.

Cách thứ hai để nối một dòng với một tệp là khai báo tên tệp và kiểu mở tệp  ngay khi khai báo dòng, hàm open sẽ được gọi với các đối số tương ứng. Ví dụ:

ofstream myfile ("hello.txt",
   ios::out | ios::app | ios::binary);

Để kiểm tra xem một tệp có được mở thành công hay không, ta dùng hàm thành viên is_open(), hàm này không yêu cầu đối số và trả về một giá trị kiểu bool bằng true nếu thành công và bằng false nếu xảy ra trường hợp ngược lại


if (myfile.is_open()) { /* file now open and ready */ }
  • Đóng tệp

Khi ta hoàn thành các công việc đọc dữ liệu và ghi kết quả, ta cần đóng tệp để

tài nguyên của nó trở về trạng thái sẵn sàng được sử dụng. Hàm thành viên này

 

không có tham số, công việc của nó là xả các vùng bộ nhớ có liên quan và đóng tệp:

 

Sau khi tệp được đóng, ta lại có thể dùng dòng myfile để mở tệp khác, còn tệp vừa đóng lại có thể được mở bởi các tiến trình  khác.

Hàm close cũng được gọi tự động khi một đối tượng dòng bị hủy trong khi    nó

đang nối với một tệp.

 

  • Xlý tp văn bn

Chế độ dòng tệp văn bản được thiết lập nếu ta không dùng cờ ios::binary khi mở tệp. Các thao tác xuất và nhập dữ liệu đối với tệp văn bản được thực hiện tương tự như cách ta làm với cout và cin.

#include <iostream>
#include <fstream>
 
using namespace std; 
 
int main ()
{
  ofstream courseFile (“courses.txt); if (courseFile.is_open())
  {
    courseFile <<1 Introduction to Programming\n”; courseFile <<2 Mathematics for Computer Science\n”; courseFile.close();
  }
  else cout << “Error: Cannot open file”;
  return 0;
}

Kết quả chạy chương trình [tệp courses.txt]

  • Introduction to Programming

 

  • Mathematics for Computer Science
Hình 8.2: Ghi dliu ra tp văn bn.
#include <iostream>
#include <fstream>
#include <string>
 
using namespace std; 
 
int main ()
{
  ifstream file (“courses.txt); 
  if (file.is_open())
  {
    while (! file.eof())
    {
      string  line; getline (file,line);
      cout << line << endl;
    }
    file.close();
  }
  else cout << “Error! Cannot open file”;
  return 0;
}

Kết quả chạy chương trình

  • Introduction to Programming
  • Mathematics for Computer Science

c-p-2-yeulaptrinh.pw

Hình 8.3: Đọc dliu ttp văn bn.

 

Chương trình ví dụ trong Hình 8.2 ghi hai dòng văn bản vào một tệp. Chương trình trong Hình 8.3 đọc nội dung tệp đó và ghi ra màn hình. Để ý rằng trong chương trình thứ hai, ta dùng một vòng lặp để đọc cho đến cuối tệp. Trong đó, myfile.eof() là hàm trả về giá trị true khi chạm đến cuối tệp, giá trị true mà myfile.eof() trả về đã được dùng làm điều kiện kết thúc vòng lặp đọc tệp.

Kiểm tra trạng thái của dòng

Bên cạnh hàm eof() có nhiệm vụ kiểm tra cuối tệp, còn có các hàm thành viên khác dùng để kiểm tra trạng thái của dòng:

bad()  trả về true nếu một thao tác đọc hoặc ghi bị thất bại. Ví dụ khi ta cố viết vào một tệp không được  mở  để ghi hoặc khi thiết bị lưu  trữ không còn chỗ trống để ghi.

fail() trả về true trong những trường hợp bad() trả về true và khi có lỗi định dạng, chẳng hạn như khi ta đang định đọc một số nguyên nhưng lại gặp phải dữ liệu là các chữ cái.

eof()   trả về true nếu chạm đến cuối tệp

good()    trả về false nếu xảy tình huống mà  một trong các hàm trên nếu được gọi thì sẽ trả về true.

Để đặt lại cờ trạng thái mà một hàm thành viên nào đó đã đánh dấu trước đó, ta dùng hàm thành viên clear.

STONE1 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi='';//stone1.inp';
  fo='';//stone1.out';
  maxn=403;
  maxm=403;
type
  arr1 = array[1..maxn] of longint;
var
  link,head,ke : array[-maxm..maxm] of longint;
  f,deg : array[1..maxn] of longint;
  i,j,n,m,k : longint;
  st : array[1..maxn,1..maxn] of longint;
  top : array[1..maxn] of longint;
  a : array[1..maxn,1..maxn] of boolean;
  cx : array[1..maxn] of boolean;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure enter;
  var u,v,i : longint;
  begin
    assign(input,fi);reset(input);
    read(n);
    for i := 1 to n do
      begin
        read(u,k);
        for j:=1 to k do
          begin
            read(v);
            if a[u,v] = false then
              begin
                a[u,v] := true;
                inc(deg[u]);
              end;
            if a[v,u] = false then
              begin
                a[v,u] := true;
                inc(deg[v]);
              end;
          end;
      end;
    close(input);
  end;
procedure push(i,x : longint);
  begin
    inc(top[i]);
    st[i,top[i]] := x;
  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 : arr1);
  var i,j,x : longint;
  begin
    i :=l;j:=r;
    x := a[(l+r) div 2];
    repeat
      while a[i] > x do inc(i);
      while a[j] < x do dec(j);
      if i<=j then
        begin
          swap(a[i],a[j]);
          inc(i);dec(j);
        end;
    until i>j;
    if i<r then qs(i,r,a);
    if j>l then qs(l,j,a);
  end;
procedure dfs(u : longint);
  var i,v,s : longint;
  begin
    cx[u] := false;
    if deg[u] <= 1 then begin f[u] := 1; exit; end;
    for v := 1 to n do
      if a[u,v] then
      if cx[v] then
        begin
          dfs(v);
          push(u,f[v]);
        end;
    qs(1,top[u],st[u]);
    s := st[u,1];
    v := st[u,1]-1;
    for i:= 2 to top[u] do
      if v < st[u,i] then
      begin
        s := s + (st[u,i]-v);
        v := v + (st[u,i]-v);
        v := v - 1;
      end else v := v-1;
    f[u] := s;
  end;
procedure process;
  begin
    fillchar(cx,sizeof(cx),true);
    dfs(1);
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(f[1]);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.

P152SUMI – ptit

Đề bài:


Thuật toán:


Tạo một mảng quy hoạch có dạng
xau[i]==xau[i+1]? arr[i+1]=arr[i]+1 : arr[i+1]=arr[i];
với arr[0]=0;
VD: #..###
ta có;
arr[0] = 0;
arr[1] = 0; (#.)
arr[2] = 1; #(..)
arr[3] = 1; #.(.#)
arr[4] = 2; #..(##)
arr[5] = 3; #..#(##)

arr[i+1] = số cặp kí tự giống nhau từ xâu[0 -> i];
-> Với mỗi truy vấn ta có:
Số cặp giống nhau từ l->r = arr[r-1] – arr[l-1];

Code:


#include <iostream>
#include <string>
using namespace std;
 
int main ()
{
	string xau;
	cin>>xau;
	int arr[100005];
	arr[0]=0;
	for (int i=0; i<xau.size()-1; i++)
	{
		if (xau[i]==xau[i+1])
			arr[i+1]=arr[i]+1;
		else
			arr[i+1]=arr[i];
	}
	int m;
	cin>>m;
	for (int i=1; i<=m; i++)
	{
		int l, r;
		cin>>l>>r;
		cout<<arr[r-1]-arr[l-1]<<endl;
	}
	return 0;
}

BCISLAND – ptit

Đề bài:


Thuật toán:


- Bài này chia ra làm các bước như sau:
+ B1: Tìm độ cao lớn nhất so với mặt nước biển. (Hmax)
+ B2: Với độ cao tăng thêm: extra = 1-&gt;Hmax ta sẽ loang bắt đầu từ các cạnh là biển loang vào những nới có độ (độ cao &lt;= extra).
VD: có bản đồ:
5 5 5 5 7
4 1 1 1 4
4 1 2 1 3
7 1 0 0 4
7 3 4 4 4
với extra=1 ta thu được check[][]:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

+B3: Đếm số thành phần liên thông tại check[][] với các check[][]==0 bằng DFS;
Số thành phần liên thông &gt; 1 thì tại độ cao extra đó đảo bị chia cắt;
VD: ở bản đồ trên tại extra = 3 ta có check[][]:
0 0 0 0 0
0 1 1 1 0
0 1 0 1 1
0 1 1 1 0
0 1 0 0 0

Code:


#include <iostream>
using namespace std;
 
int n, m;
int seawater[102][102];
int Hmax=0;
void read ()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			cin>>seawater[i][j];
			if (seawater[i][j]>Hmax) Hmax=seawater[i][j];
		}
	}
}
 
int check[102][102];
int check_connect[102][102];
void init ()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			check[i][j]=0;
			check_connect[i][j]=0;
		}
	}
}
 
int extra;
int x_ar[]={+1, +0, -1, +0};
int y_ar[]={+0, -1, +0, +1};
void loang (int i, int j)
{
	check[i][j]=1;
	for (int k=0; k<4; k++)
	{
		int X=j+x_ar[k];
		int Y=i+y_ar[k];
		if (X>=1 && X<=m && Y>=1 && Y<=n)
		{
			if (check[Y][X]==0 && seawater[Y][X]<=extra) loang (Y, X);
		}
	}
}
 
void DFS (int i, int j)
{
	check_connect[i][j]=1;
	for (int k=0; k<4; k++)
	{
		int X=j+x_ar[k];
		int Y=i+y_ar[k];
		if (X>=1 && X<=m && Y>=1 && Y<=n)
		{
			if (check_connect[Y][X]==0 && check[Y][X]==check[i][j]) DFS (Y, X);
		}
	}
}
 
int main ()
{
	int t=0;
	while (1)
	{
		cin>>n>>m;
		if (n==0 && m==0) break;
		t++;
		read ();
		int kt=0;
		for (int k=0; k<=Hmax; k++)
		{
			extra=k;
			init ();
			for (int i=1; i<=n; i++)
			{
				for (int j=1; j<=m; j++)
				{
					if ((i==1 || i==n || j==1 || j==m) && seawater[i][j]<=k && check[i][j]==0) loang (i, j);
				}
			}
			//dem lien thong?
			int count_connect=0;
			for (int i=1; i<=n; i++)
			{
				for (int j=1; j<=m; j++)
				{
					if (check_connect[i][j]==0 && check[i][j]==0)
					{
						count_connect++;
						DFS (i, j);
					}
				}
			}
			if (count_connect>1)
			{
				kt=1;
				break;
			}
		}
		if (kt==1) cout<<"Case "<<t<<": Island splits when ocean rises "<<extra<<" feet."<<endl;
		else cout<<"Case "<<t<<": Island never splits."<<endl;
	}
	return 0;
}

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

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.