Đề thi chọn HSG môn Tin học Lớp 9

TỔNG QUAN BÀI THI
Tên bài
File chương trình
File dữ liệu vào
File kết quả
Bài 1
Tam giác
TAMGIAC.*
TAMGIAC.INP
TAMGIAC.OUT
Bài 2
Gặp nhau
GAPNHAU.*
GAPNHAU.INP
GAPNHAU.OUT
Bài 3
Domino
DOMINO.*
DOMINO.INP
DOMINO.OUT
Dấu * được thay thế bởi PAS, PP hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++
Hãy lập trình để giải các bài toán sau:
Bài 1: Tam giác (6 điểm)
Trong mặt phẳng toạ độ Oxy cho N điểm, mỗi điểm Ni được xác định bởi cặp toạ độ nguyên xi, yi. (1 £ i £ 100)
Hãy tính diện tích của tất cả các tam giác được tạo thành từ 3 điểm phân biệt không thẳng hàng và chứa điểm N1(x1, y1). Ghi diện tích các tam giác tìm được vào tệp TAMGIAC.OUT theo thứ tự tăng dần.
Biết công thức tính diện tích tam giác: và với a, b, c là độ dài của 3 cạnh của tam giác.
Dữ liệu vào: được cho trong tệp TAMGIAC.INP gồm có các dòng:
- Dòng đầu tiên có 1 số nguyên dương N (1 £ N £ 100) .
- Các dòng tiếp theo ghi các cặp số nguyên (các số cách nhau ít nhất một kí tự trắng) là tọa độ của đỉểm Ni tương ứng.
Dữ liệu ra: được ghi vào tệp TAMGIAC.OUT gồm:
- Mỗi dòng ghi diện tích của một tam giác theo thứ tự tăng dần (lấy 2 chữ số thập phân). Nếu không tồn tại tam giác thì ghi là NULL.
Ví dụ: 
TAMGIAC.INP
TAMGIAC.OUT
5 
2 7
6 4
5 -2
-1 -2
-2 4
12.00
13.50
13.50
22.50
22.50
27.00
Bài 2: Gặp nhau(7 điểm)
Hoà và Thân là bạn thân của nhau, hai người xa nhau đã lâu, nay mới liên lạc được với nhau qua Internet và họ hẹn gặp nhau tại thành phố Hồ Chí Minh. Họ quyết định đến gặp nhau bằng cách đi máy bay để tiết kiệm thời gian. Hoà và Thân sinh sống và làm việc tại hai thành phố khác nhau. 
Hãy tìm cách giúp Hoà và Thân đến được thành phố Hồ Chí Minh bằng các chuyến bay có thể có nhưng để tiết kiệm chi phí, tại mỗi sân bay mỗi người chỉ được ghé lại 1 lần và mỗi người phải qua ít thành phố nhất. 
Các thành phố xem như là các đỉnh của một đồ thị vô hướng gồm N đỉnh được mã số từ 1 đến N (1 £ i £ 100). Chỉ một số cặp thành phố mới có đường bay còn lại thì không. Giả sử đỉnh xuất phát không trùng đỉnh đích. 
Dữ liệu vào: được cho trong tệp GAPNHAU.INP gồm có các dòng:
- Dòng đầu tiên, được gọi là dòng 0, chứa 4 số tự nhiên N, H, T, D(1£H,T,D£N), trong đó N là số thành phố có sân bay, H là nơi Hoà đang sinh sống và công tác còn T là thành phố mà Thân sống và làm việc, D là mã số của thành phố Hồ Chí Minh nơi mà Hoà và Thân hẹn gặp. (các số cách nhau ít nhất 1 khoảng cách)
- Dòng thứ i (1 £ i £ N - 1), trong N-1 dòng tiếp theo cho biết có hay không đường bay nối thành phố i với thành phố j (j=N-j+1) bằng các số 0, 1 (số 0 nghĩa là không có đường bay giữa hai đỉnh i , j; số 1 nghĩa là tồn tại đường bay giữa hai đỉnh i , j) các số cách nhau ít nhất 1 khoảng cách. 
GAPNHAU.OUT
3 3
6 4 7
2 3 7
Ví dụ:
GAPNHAU.INP
9 6 2 7
1 0 1 1 1 0 0 0
1 1 0 0 0 0 0
0 0 0 1 0 0
0 1 1 0 0
0 0 0 0
0 0 0
0 0
1
1
1
2
4
6
5
9
8
3
7
- Dòng 0: 9 6 2 7 - Có 9 đỉnh mã số từ 1 đến 9, cần tìm đường đi từ đỉnh 6 đến đỉnh 7 và từ đỉnh 2 đến đỉnh 7.
- Dòng 1: 1 0 1 1 1 0 0 0 - đỉnh 1 được nối với các đỉnh 2, 4, 5, và 6. Không có cạnh nối đỉnh 1 với các đỉnh 3, 7, 8 và 9.
- Dòng 2: 1 1 0 0 0 0 0 - đỉnh 2 được nối với các đỉnh 3 và 4. Không có cạnh nối đỉnh 2 với các đỉnh 5, 6, 7, 8 và 9.
- ...
- Dòng 8: 1 – đỉnh 8 có nối với đỉnh 9. 
Vì đồ thị là vô hướng nên cạnh nối đỉnh x với đỉnh y cũng chính là cạnh nối đỉnh y với đỉnh x. thông tin về đỉnh N không cần hiển thị vì với mỗi đỉnh i ta chỉ liệt kê các đỉnh j>i tạo thành đường đi (i,j).
Dữ liệu ra: được ghi trong tệp văn bản GAPNHAU.OUT:
Dòng đầu tiên ghi số tự nhiên k, l là số đỉnh trên đường đi từ H đến D và số đỉnh trên đường từ T tới D (nếu không có đường đi thì ghi số 0).
Dòng thứ 2 ghi lần lượt các đỉnh có trên đường đi từ H đến D. (Nếu không có thì ghi 0)
Dòng thứ 3 ghi lần lượt các đỉnh có trên đường đi từ T đến D. (Nếu không có thì ghi 0)
Bài 3: Domino (7 điểm)
Cho ma trận gồm n dòng và m cột (1 £ m, n £ 100). Mỗi ô trong ma trận được gán mã số 1, 2, ... , n´m theo thứ tự từ dòng trên xuống dòng dưới, trên mỗi dòng tính từ trái qua phải. Trong ma trận, người ta đặt v vách ngăn giữa hai ô kề cạnh nhau. 
Hãy tìm cách đặt nhiều nhất k quân domino, mỗi quân gồm hai ô kề cạnh nhau trên ma trận và không có vách ngăn ở giữa. 
Dữ liệu vào: được cho trong tệp DOMINO.INP. 
- Dòng đầu tiên gồm 3: số n là số dòng, số m là số cột và số v là số vách ngăn (các số cách nhau ít nhất 1 khoảng cách).
- V dòng tiếp theo, mỗi dòng có 2 số a, b (các số cách nhau ít nhất 1 khoảng cách) cho biết vách ngăn đặt giữa hai ô này.
Dữ liệu ra: được ghi vào tệp DOMINO.OUT. 
- Dòng đầu tiên ghi số k là số quân domino tối đa đặt được trên Ma trận.
- K dòng tiếp theo, mỗi dòng 2 số x, y (các số cách nhau ít nhất 1 khoảng cách) cho biết số hiệu của 2 ô kề cạnh nhau tạo thành một quân domino. 
DOMINO.INP
DOMINO.OUT
4 5 8
2 3
4 5
6 7
9 10
10 15
7 12
19 20
13 18
10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1 2
3 4
5 10
6 11
7 8
9 14
12 13
15 20
16 17
18 19
----------------HẾT----------------
* Thí sinh không được sử dụng tài liệu.
* Giám thị không giải thích gì thêm.
Họ và tên thí sinh: ..Số báo danh:...
Giám thị 1: .. Ký tên:..
Giám thị 2: .. Ký tên:..
TỔNG QUAN BÀI THI
Tên bài
File chương trình
File dữ liệu vào
File kết quả
Bài 1
Tam giác
TAMGIAC.*
TAMGIAC.INP
TAMGIAC.OUT
Bài 2
Gặp nhau
GAPNHAU.*
GAPNHAU.INP
GAPNHAU.OUT
Bài 3
Domino
DOMINO.*
DOMINO.INP
DOMINO.OUT
Dấu * được thay thế bởi PAS, PP hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++
Bài 1: Tam giác (6 điểm)
Bài thi được tiến hành chấm theo các bộ “test” chương trình, mỗi bộ test 1 điểm.
Ý tưởng: 
Bài toán kiểm tra kiến thức lập trình giải các bài toán hình học và vận dụng thuật toán sắp xếp.
Các công thức hình học:
Tính độ dài đoạn thẳng: 
Tính diện tích tam giác: với ; a, b, c là độ dài của 3 cạnh của tam giác.
Các thuật toán sắp xếp:
Không bắt buộc thí sinh sử dụng thuật toán sắp xếp cụ thể nào, tuy nhiên chương trình phải đáp ứng được về mặt thời gian thực hiện tối thiểu là 5 giây cho mỗi bộ test. 
Các bộ test chấm điểm:
Test
Dữ liệu vào
Trong tệp TAMGIAC.INP
Dữ liệu ra
Tệp TAMGIAC.OUT
Điểm
Test 1 
5 
2 7
6 4
5 -2
-1 -2
-2 4
12.00
13.50
13.50
22.50
22.50
27.00
1 điểm
Test 2
2
3 1
-2 3
NULL
1 điểm
Test 3
4
0 0
0 2
2 2
2 0
2.00
2.00
2.00
1 điểm
Test 4
5
0 6
3 3
6 0
-6 0
-3 3
9.00
18.00
18.00
36.00
1 điểm
Test 5 
20
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
19 1
 9.00
 18.00
 27.00
 36.00
 45.00
 54.00
 63.00
 72.00
 81.00
 90.00
 99.00
 108.00
 117.00
 126.00
 135.00
 144.00
 153.00
 162.00
1 điểm
Test 6
3
0 1
0 2
0 3
NULL
1 điểm
Chương trình tham khảo
type diem = record
 x,y:integer;
 end;
 mang = array[1..50] of real;
var dtg,dd,n,k,i,j:integer;
 d1,d2,d3,p:real;
 d:array[1..50] of diem;
 dt:mang;
 f,g:text;
procedure sapxep(var a:mang;n:integer);
var x,y:integer;
 tg:real;
begin
 for x:=n downto 2 do
 for y:=1 to x -1 do
 if a[y] > a[y+1] then
 begin
 tg := a[y];
 a[y] := a[y+1];
 a[y+1]:=tg;
 end;
end;
procedure nhap;
begin
 assign(f,'t2.inp');
 reset(f);
 readln(f,n);
 for i:= 1 to n do
 readln(f,d[i].x,d[i].y);
 close(f);
end;
procedure xuat;
 var dm:array[1..50] of real;
begin
 assign(g,'thu.oup');
 rewrite(g);
 if dtg<1 then writeln(g,'khong co tam giac nao')
 else
 begin
 sapxep(dt,dtg);
 for i:=1 to dtg do
 if dt[i] > 0 then writeln(g,dt[i]:10:2);
 end;
 close(g);
end;
function dientich(a,b,c:diem):real;
begin
 d1:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
 d2:=sqrt(sqr(a.x-c.x)+sqr(a.y-c.y));
 d3:=sqrt(sqr(b.x-c.x)+sqr(b.y-c.y));
 if (d1+d2 >d3) and (d1+d3>d2) and (d2 + d3 > d1) then
	 begin
	 p:=(d1+d2+d3)/2;
 dientich:=sqrt(p*(p-d1)*(p-d2)*(p-d3));
	 end
 else dientich := 0;
end;
procedure bailam;
begin
 dtg:=0;
 if n < 3 then exit;
 for i:= 2 to n-1 do
 for j:= i+1 to n do
 begin
 dtg:=dtg+1;
	 dt[dtg]:=dientich(d[1],d[i],d[j]);
 end;
end;
begin
 nhap;
 bailam;
 xuat;
end.
Bài 2: Gặp nhau(7 điểm)
Bài thi được tiến hành chấm theo các bộ “test” chương trình, mỗi bộ test 1 điểm.
Ý tưởng: 
Bài toán xử lý trên đồ thị vô hướng. Kiểm tra kiến thức, kỹ năng vận dụng lý thuyết đồ thị đơn giản để tìm đường đi ngắn nhất trong đồ thị từ đỉnh A đến đỉnh B bất kỳ. 
Thuật toán:
Xuất phát từ đỉnh v[1] = s, mỗi bước lặp i ta thực hiện các kiểm tra sau. Gọi k là số đỉnh đã đi qua và được tích luỹ trong mảng giải trình đường đi v, cụ thể là xuất phát từ đỉnh v[1] = s, sau một số lần duyệt ta quyết định chọn đường đi qua các đỉnh v[1], v[2], v[3],, v[k]. Có thể gặp các tình huống sau:
a) (Đến đích?) nếu v[k] = t tức là đã đến được đỉnh t: thông báo kết quả, dừng thuật toán, ngược lại thực hiện b.
b) (Thất bại?) k = 0: nếu đã quay trở lại vị trí xuất phát v[i] = s mà từ đó không còn đường đi nào khác thì phải lùi một bước nữa, do đó k = 0. Trường hợp này chứng tỏ bài toán vô nghiệm, tức là, do đồ thị không liên thông nên không có đường đi từ đỉnh s đến đỉnh t. Ta thông báo vô nghiệm và dừng thuật toán.
c) (Đi tiếp?) nếu từ đỉnh v[k] tìm được một cạnh chưa đi qua và dẫn đến một đỉnh i nào đó thì tiến theo đường đó, nếu không: thực hiện bước d.
d) (Lùi một bước) Bỏ đỉnh v[k], lùi lại đỉnh v[k-1].
Thuật toán trên có tên là sợi chỉ Arian được phỏng theo một truyền thuyết cổ Hy Lạp sau đây. Anh hùng Te-dây phải tìm diệt con quái vật nhân ngưu (đầu người, mình trâu) Minotav ẩn náu trong một phòng của mê cung có nhiều ngõ ngách rắc rối đã từng làm lạc bước nhiều dũng sĩ và những người này đều trở thành nạn nhân của Minotav. Người yêu của chàng Te-dây là công chúa của xứ Mino đã đưa cho chàng một cuộn chỉ và dặn chàng như sau: Chàng hãy buộc một đầu chỉ vào cửa mê cung (phòng xuất phát s), sau đó, tại mỗi phòng trong mê cung, chàng hãy tìm xem có Minotav ẩn trong đó không. Nếu có, chàng hãy chiến đấu dũng cảm để hạ thủ nó rồi cuốn chỉ quay ra cửa hang, nơi em trông ngóng chàng. Nếu chưa thấy Minotav tại phòng đó, chàng hãy kiểm tra xem chỉ có bị rối hay không. Cuộn chỉ bắt đầu rối khi nào từ phòng chàng đứng có hai sợi chỉ đi ra hai cửa khác nhau. Nếu chỉ rối như vậy, chàng hãy cuộn chỉ để lùi lại một phòng và nhớ đánh dấu đường đã đi để khỏi lạc bước vào đó lần thứ hai.
Nếu không gặp chỉ rối thì chàng hãy yên tâm dò tìm một cửa chưa đi để qua phòng khác. Đi đến đâu chàng nhớ nhả chỉ theo đến đó. Nếu không có cửa để đi tiếp hoặc từ phòng chàng đang đứng, mọi cửa ra đều đã được chàng đi qua rồi, thì chàng hãy cuốn chỉ để lùi lại một phòng rồi tiếp tục tìm cửa khác.
Ta xuất phát từ sơ đồ tổng quát cho lớp bài toán quay lui.
Thí sinh tuỳ ý kết hợp thuật toán trên cùng lúc cho 2 vị trí xuất phát đỉnh khác nhau hoặc thực hiện riêng lẽ việc tìm đường đi cho mỗi đỉnh xuất phát.
Các bộ Test chấm điểm
Test
Dữ liệu vào
Trong tệp GAPNHAU.INP
Dữ liệu ra
Tệp GAPNHAU.OUT
Điểm
Test 1 
9 6 2 7
1 0 1 1 1 0 0 0
1 1 0 0 0 0 0
0 0 0 1 0 0
0 1 1 0 0
0 0 0 0
0 0 0
0 0
1
3 3
6 4 7
2 3 7
1 điểm
Test 2
4 1 4 3
1 0 0
0 0
1
0 2
0
4 3
1 điểm
Test 3
5 2 5 4
1 0 0 0
0 0 1
1 1
0
4 3
2 5 3 4
5 3 4
1 điểm
Test 4
10 10 1 5 
1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0
1 0 0 0 
1 0 0 
1 0 
1 
6 5
10 9 8 7 6 5
1 2 3 4 5
1 điểm
Test 5 
5 1 4 5
1 0 0 0
0 0 0
1 0
0
0 0 
0 
0
1 điểm
Test 6
20 7 18 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 1 
0 0 0 0 0 0 1 
0 0 0 0 0 1 
0 0 0 0 1 
0 0 0 1 
0 0 1 
0 1 
1 
3 3
7 20 3
18 20 3
1 điểm
Test 7
10 10 1 2 
1 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0
1 0 0 0 
1 0 0 
1 0 
1 
3 2
10 1 2
1 2
Giải thuật tham khảo:
(* ----------------------------------------
(Thuat toan Arian)
 s: dinh xuat phat
 t: dinh ket.
------------------------------------------*)
procedure MC;
var i: byte;
begin
Doc; {doc du lieu}
{----------------------------
 khoi tao mang d, 
danh dau cac dinh da tham: 
d[i] = 1: dinh da tham 
d[i] = 0: dinh chua tham 
-----------------------------}
fillchar(d,sizeof(d),0); 
k := 1; {k – dem so dinh da chon }
v[k] := s; {dinh xuat phat }
d[s] := 1; {da tham dinh s }
repeat
if v[k] = t then {den dich }
begin
ket(k); {ghi ket qua: giai trinh duong di }
	exit;
end;
if k < 1 then {vo nghiem }
begin
	ket(0);
	exit;
end;
 i := Tim; 
 {tu dinh v[k] tim 1 dinh chua tham i }
if i > 0 then 
	 {neu tim duoc, i > 0, di den dinh i }
	NhaChi(i)
else CuonChi; 
	{neu khong tim duoc, } 
 { i = 0: lui 1 buoc - bo dinh v[k] }
until false;
end;
Bài 3: Domino (7 điểm)
Bài thi được tiến hành chấm theo các bộ “test” chương trình, mỗi bộ test 1 điểm.
Ý tưởng: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Bài này có hai điểm khác với dạng bài cặp ghép truyền thống. Thứ nhất là ghép cặp được thực hiện từ một tập A với chính nó: 
f: A ® A. 
Thứ hai, mỗi số trong tập A chỉ có thể ghép tối đa với 4 số trong các ô kề cạnh nó mà ta tạm gọi là số kề. Thí dụ, 8 có 4 số kề theo thứ tự trái, phải và trên, dưới là 7, 9 và 3, 13. Các số ngoài rìa và các số có vách ngăn còn có ít bạn hơn. Thí dụ, 20 có đúng 1 bạn. 
Thuật toán
Khi đọc dữ liệu ta xác định ngay cho mỗi số i trong bảng bốn số kề và ghi vào mảng ke với ý nghĩa như sau ke[i][j] = 1 khi và chỉ khi i có số kề tại vị trí j; j = 1, 2, 3, 4. Nếu i có vách ngăn phải thì i sẽ mất bạn kề phải. Tương tự, nếu i có vách ngăn dưới thì i sẽ mất bạn kề dưới. Ngoài ra, dễ hiểu rằng các số trên dòng 1 thì không có số kề trên, các số trên dòng n thì không có số kề dưới. Tương tự, các số trên cột 1 thì không có số kề trái, các số trên cột m thì không có số kề phải.
Nhắc lại rằng ta chỉ cần sử dụng một mảng a với ý nghĩa a[i] = j, đồng thời a[j] = i cho biết số i chọn số kề j để ghép thành 1 quân domino. Nói cách khác nếu ta xếp được f(i) = j thì ta phải gán a[i] = j và a[j] = i. 
Tiếp đến ta thực hiện thủ tục Xep(i) cho mọi số chưa được ghép cặp (a[i] = 0) và chưa là bạn của bất kì số nào (b[i] = 0). 
Khi ghi kết quả ra file ta lưu ý là hai cặp (i , a[i] = j) và (j, a[j] = i) thực ra chỉ tạo thành một quân domino duy nhất, do đó ta chỉ cần ghi một trong hai cặp đó. Ta chọn cặp i a[i].
Các bộ Test chấm điểm
Test
Dữ liệu vào
Trong tệp DOMINO.INP
Dữ liệu ra
Tệp DOMINO.OUT
Điểm
Test 1 
4 5 8
2 3
4 5
6 7
9 10
10 15
7 12
19 20
13 18
10
1 2
3 4
5 10
6 11
7 8
9 14
12 13
15 20
16 17
18 19
1 điểm
Test 2
1 1 0
0
Test 3
1 2 0
1
1 2
Test 4
1 2 1
1 2
0
Test 5
1 10 3
1 2
3 4
4 5
4
2 3
5 6
7 8
9 10
Test 6
3 3 2
1 2
4 5
4
1 4
2 3
6 9
7 8
Test 7
4 4 11
1 5
3 4
5 6
6 7
6 10
7 11
10 11
10 14
11 12
12 16
13 14
4 
1 2
4 8
9 13
15 16
Tuỳ theo sự sắp xếp domino của thí sinh, tuy nhiên chỉ cần 1 phương án đúng thì cũng đạt điểm tối đa.
Chương trình tham khảo
(* Domino.pas *)
uses crt;
const maxmn = 201; fn = 'domino.inp'; gn = 'domino.out';
 bl = #32; nl = #13#10; phai = 1; trai = 2; tren = 3; duoi = 4;
type mi1 = array[0..maxmn] of integer;
var n: integer; { so dong }
 m: integer; { so cot }
 nm: integer;{ nm = n.m }
 f,g: text;
 ke: array[0..maxmn,phai..duoi] of Boolean;
 st: mi1; { stack } p: integer; { ngon st }
 a, t: mi1;
procedure Doc;
 var i, j, k, v, t: integer;
begin
 fillchar(ke,sizeof(ke),true);
 assign(f,fn); reset(f);
 readln(f,n,m,v); { v - so vach ngan }
 nm := n*m;
 { dong 1 va dong n } k := (n-1)*m;
 for j := 1 to m do
 begin
 ke[j, tren] := false; ke[j+k, duoi] := false;
 end;
 j := 1; { cot 1 va cot m }
 for i := 1 to n do
 begin
 ke[j , trai] := false; j := j + m; ke[j-1, phai] := false;
 end;
 for k := 1 to v do
 begin
 readln(f,i,j);
 if i > j then begin t := i; i := j; j := t end; { i < j }
 if i = j-1 then ke[i,phai] := false else ke[i,duoi] := false;
 end;
 close(f);
end;
procedure Update(i,j: integer);
var q: integer;
begin
 repeat
 q := a[i]; { i bo so q }
 a[i] := j; a[j] := i; { de nhan so j }
 j := q;
 i := t[i]; { chuyen qua so truoc }
 until q = 0;
end;
function Xep(i: integer): integer;
 var j, k: integer;
begin
 Xep := 1;
 p := 0; inc(p); st[p] := i; { nap st }
 fillchar(t, sizeof(t),0); t[i] := i;
 while p > 0 do
 begin
 i := st[p]; dec(p); { Lay ngon st }
 for k := 1 to 4 do
 if ke[i,k] then { i co o ke }
 begin
 case k of
 tren: j := i - m;
 duoi: j := i + m;
 phai: j := i + 1;
 trai: j := i - 1;
 end;
 if a[j] = 0 then { j chua bi chiem }
 begin Update(i,j); exit end
 else if t[a[j]] = 0 { a[j] chua co trong st }
 then begin inc(p); st[p] := a[j]; t[a[j]] := i end;
 end;
 end;
 Xep := 0;
end;
function Par: integer;
var i, v: integer;
begin
 fillchar(a,sizeof(a),0); v := 0;
 for i := 1 to nm do
 if a[i] = 0 then v := v + Xep(i);
 par := v;
end;
procedure Ghi(k: integer);
var i: integer;
begin
 assign(g,gn); rewrite(g);
 writeln(g, k);
 for i := 1 to nm do
 if i < a[i] then
 writeln(g,i,bl,a[i]); 
 close(g);
end;
procedure Run;
var k: integer;
begin
 Doc; k := Par; Ghi(k);
end;
BEGIN
 Run;
 writeln(nl,' Fini'); readln;
END.
----------------HẾT----------------