SỞ GD&ĐT HÒA BÌNH ĐỀ THI CHỌN HỌC SINH GIỎI CẤP TỈNH
LỚP 12 THPT, NĂM HỌC 2007-2008
Đề thi chính thức
Môn thi: TIN HỌC
Ngày thi: 19/12/2007
(Thời gian 180 phút Không kể thời gian giao đề)
(Đề thi gồm có 04 bài, 02 trang)
Bài 1 (5 điểm): Tam giác Tên tệp bài làm: BL1.PAS
Trong mặt phẳng cho 3 điểm A(x1; y1), B(x2; y2), C(x3; y3) phân biệt. Viết chương
trình kiểm tra xem 3 điểm A, B, C có phải là ba đỉnh của một tam giác hay không. Nếu
A, B, C có là ba đỉnh của một tam giác thì đưa ra toạ độ trọng tâm G của tam giác ABC.
Dữ liệu vào: nhập từ bàn phím (hoặc từ file văn bản) gồm 6 số thực theo thứ tự là:
x1 y1 x2 y2 x3 y3 (mỗi số cách nhau ít nhất 1 dấu cách)
Kết quả ra: in ra màn hình (hoặc file văn bản) gồm 2 dòng:
+ Dòng 1: Kết luận có phải là tam giác hay không.
+ Dòng 2: Toạ độ trọng tâm G của tam giác (nếu có).
Ví dụ: x1=10,0; y1=0,0; x2= -10,0; y2=0,0; x3=0,0; y3=12,0 là toạ độ 3 đỉnh của tam
giác ABC có tọa độ trọng tâm G (0,0; 4,0)
Bài 2 (5 điểm): Các ước chung nguyên tố Tên tệp bài làm: BL2.PAS
Hãy viết chương trình tìm tất cả các ước số chung nguyên tố của hai số nguyên dương M
và N (M, N là các số nguyên 4 byte)
Dữ liệu vào: Được nhập từ bàn phím (hoặc từ file văn bản) gồm 2 số nguyên dương M
và N, mỗi số nhập cách nhau ít nhất một dấu cách.
Kết quả ra: In ra màn hình (hoặc ra file văn bản) gồm 2 dòng:
+ Dòng 1: Số lượng các ước số chung nguyên tố của M và N (nếu không có thì ghi
số 0).
+ Dòng 2: Các ước số chung nguyên tố của M và N (nếu có), mỗi số viết cách nhau
ít nhất 1 dấu cách.
Ví dụ: M = 60 và N = 45 có 2 ước chung nguyên tố là : 3 và 5.
Bài 3 (5 điểm): Dãy số Fibonaci Tên tệp bài làm: BL3.PAS
Dãy số Fibonaci được định nghĩa như sau:




>−+−
≤
=
2)1()2(
21
)(
nnFnF
n
nF
Hãy lập chương trình in ra số Fibonaci thứ n (0< n ≤100)
Dữ liệu vào: Nhập vào từ bàn phím số n
Kết quả ra: In ra màn hình số F(n) (số Fibonaci thứ n)
Ví dụ: n = 20 ta có F(n) = 6765
Bài 4 (5 điểm): Mê cung Tên tệp bài làm: BL4.PAS
1
Mê cung là một lưới các ô vuông kích thước m x n (m dòng, n cột; các dòng đánh số từ
1 đến m từ trên xuống dưới, các cột đánh số từ 1 đến n từ trái qua phải; 0<m,n≤100).
Trong mỗi ô vuông của lưới có ghi số 0 cho biết là ô trống có thể đi qua được hoặc số 1
cho biết ô đó có vật cản không đi qua được. Một con robot đứng tại ô (i,j) (dòng i, cột j
trong lưới) và robot quay mặt về hướng Bắc (giả sử hướng Bắc là hướng nhìn từ dòng m
lên dòng 1, hướng Đông là từ trái sang phải), con robot chỉ có khả năng di chuyển từ một
ô đến một ô kề cạnh không có vật cản theo hướng nhìn của nó. Hãy lập chương trình:
a) Chỉ ra đường đi ngắn nhất cho con robot ra khỏi mê cung.
b) Hãy mã hoá dãy đường đi của con robot tìm được trong câu a) thành chuỗi điều khiển
ngắn nhất bao gồm các ký tự F, L, R (F - nghĩa là đi thẳng, L - nghĩa là quay trái, R -
nghĩa là quay phải).
Dữ liệu vào: từ file văn bản MECUNG.INP có cấu trúc:

+ Dòng đầu ghi 4 số nguyên m, n, p, q mỗi số cách nhau ít nhất một dấu cách (m -
số dòng, n - số cột của lưới; p và q là toạ độ ban đầu của robot)
+ m dòng sau mỗi dòng ghi n gồm các số 0 hoặc số 1 biểu diễn mê cung, mỗi số
viết cách nhau ít nhất một dấu cách.
Kết quả: ghi ra file văn bản MECUNG.OUT có cấu trúc:
+ Dòng đầu ghi số nguyên k cho biết số bước đi của đường đi ngắn nhất (nếu
không có đường đi thì ghi số 0)
Nếu k > 0 thì:
+ Trên k dòng tiếp theo ghi mỗi dòng 2 số nguyên i, j cách nhau ít nhất một dấu
cách biểu diễn toạ độ dòng, cột của đường đi ngắn nhất tìm được.
+ Dòng cuối cùng ghi ra chuỗi điều khiển đường đi của con robot (chuỗi điều
khiển có thể rất dài, do vậy có thể in trên nhiều dòng).
Ví dụ: Trong minh hoạ dưới đây, con robot đứng tại ô (4,3) thì đường đi ngắn nhất ra
khỏi mê cung là dãy 3 ô: (4,3),(4,4),(5,4) và chuỗi điều khiển đường đi cho con robot là :
RFRF
1 2 3 4 5
1
1 0 1 1 1
2
1 0 1 0 1
3
1 0 1 0 1
4
1 0 0 0 1
5
1 1 1 0 1
Dữ liệu và kết quả mẫu cho ví dụ trên như sau:
MECUNG.INP MECUNG.OUT
5 5 4 3
1 0 1 1 1

1 0 1 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 0 1
3
4 3
4 4
5 4
RFRF
--- Hết ---
2
BẮC
ÔNGĐ
TÂY
N
A
M
SỞ GD&ĐT HÒA BÌNH ĐÁP ÁN VÀ BIỂU ĐIỂM
THI CHỌN HỌC SINH GIỎI CẤP TỈNH
Đề thi chính thức LỚP 12 THPT, NĂM HỌC 2007-2008
Môn thi: TIN HỌC
Ngày thi: 19/12/2007
(Thời gian 180 phút Không kể thời gian giao đề)
Bài 1: Tam giác (5 điểm)
- Có 5 test, mỗi test cho kết quả đúng được 1,0 điểm trong đó:
+ Đưa ra kết luận đúng: 0,5 điểm
+ Đưa ra toạ độ trọng tâm đúng: 0,5 điểm
- Nếu chương trình không cho ra kết quả, giám khảo có thể xem lại mã nguồn và đánh
giá bài làm và cho tối đa 1,0 điểm.
Test 1:

BL1.IN1 BL1.OU1
1.0 1.5 -1.0 -0.5 3.0 2.0 Là tam giác
G(1.0; 1.0)
Test 2:
BL1.IN2 BL1.OU2
0.0 -1.0 -0.5 -2.0 3.0 5.0 Không là tam giác
Test 3:
BL1.IN3 BL1.OU3
-1.0 6.0 2.0 3.0 -0.4 6 Là tam giác
G(0.2; 5.0)
Test 4:
BL1.IN4 BL1.OU4
0.0 3.0 -5.0 -0.5 3.0 5.1 Không là tam giác
Test 5:
BL1.IN5 BL1.OU5
2.0 -3.8 -6 3.4 -2.0 -0.5
Là tam giác
G(-2.0; -0.3)
Bài 2: Các ước chung nguyên tố (5 điểm)
- Có 5 test, mỗi test cho kết quả đúng được 1,0 điểm trong đó:
+ Đưa ra số lượng đúng: 0,5 điểm
+ Đưa ra các ước chung nguyên tố đúng: 0,5 điểm
- Nếu chương trình đưa ra số các ước số chung và tất cả các ước chung của 2 số thì cho
0,5 điểm.
+ Nếu chương trình không cho ra kết quả, giám khảo có thể xem lại mã nguồn và đánh
giá bài làm và cho tối đa 1,0 điểm.
Test 1:
BL2.IN1 BL2.OU1
210 1470
4

2 3 5 7
Test 2:
BL2.IN2 BL2.OU2
4290 38220
4
2 3 5 13
1
Test 3:
BL2.IN3 BL2.OU3
59400 35280
3
2 3 5
Test 4:
BL2.IN4 BL2.OU4
61132 26273 0
Test 5:
BL2.IN5 BL2.OU5
1729067923 2043443909
1
157187993
Bài 3: Dãy số Fibonaxi (5 điểm)
- Có 5 test, mỗi test cho kết quả đúng được 1,0 điểm trong đó:
+ Đúng Test 1: 1,0 điểm
+ Đúng Test 2: 1,0 điểm
+ Đúng Test 3: 1,0 điểm
+ Đúng Test 4: 1,0 điểm
+ Đúng Test 5: 1,0 điểm
+ Nếu chương trình không cho ra kết quả, giám khảo có thể xem lại mã nguồn và đánh
giá bài làm và cho tối đa 1,0 điểm.
Test 1:

BL3.IN1 BL3.OU1
23 28657
Test 2:
BL3.IN2 BL3.OU2
24 46368
Test 3:
BL3.IN3 BL3.OU3
55 88232072445
Test 4:
BL3.IN4 BL3.OU4
92 4586221326012050429
Test 5:
BL3.IN5 BL3.OU5
100 102454869877067178275
Bài 4: Mê cung (5 điểm)
- Có 5 test, mỗi test cho kết quả đúng được 1,0 điểm trong đó:
+ câu a: 0,5 điểm
+ câu b: 0,5 điểm
- Nếu chương trình không cho ra kết quả, giám khảo có thể xem lại mã nguồn và đánh
giá bài làm và cho tối đa 1,0 điểm.
Test 1:
MECUNG.IN1 MECUNG.OU1
5 5 4 3
1 0 1 1 1
1 0 1 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 0 1
3
4 3

4 4
5 4
RFRF
Test 2:
2
MECUNG.IN2 MECUNG.OU2
10 10 2 2
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 0 0 0
1 0 1 1 1 1 1 1 0 1
1 0 1 1 0 0 0 0 0 1
1 0 1 1 0 1 1 1 0 1
1 0 1 1 0 1 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
11
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 9
4 9
4 10
RFFFFFFFRFFLF

Test 3:
MECUNG.IN3 MECUNG.OU3
10 10 5 5
1 1 1 1 1 0 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 1 0 1
1 0 1 1 0 1 0 1 0 1
1 0 1 1 0 0 0 1 0 1
1 0 1 1 1 0 1 1 0 1
1 0 1 1 0 1 1 1 0 1
1 0 0 0 1 0 0 0 0 1
1 1 1 1 1 1 1 0 1 1
12
5 5
4 5
4 4
4 3
4 2
3 2
2 2
2 3
2 4
2 5
2 6
1 6
FLFFFRFFRFFFFLF
Test 4:
MECUNG.IN4 MECUNG.OU4
10 10 5 5

1 1 1 1 1 0 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 0 1
1 1 0 0 0 0 0 1 0 1
1 0 1 1 0 1 0 1 0 1
1 0 1 1 0 0 0 1 0 1
1 0 1 1 1 0 1 1 0 1
1 0 1 1 0 1 1 1 0 1
1 0 0 0 1 0 0 0 0 1
1 1 1 1 1 1 1 0 1 1
0
Test 5:
MECUNG.IN5 MECUNG.OU5
100 100 50 51
file dữ liệu quá lớn không
in ra giấy
2506
file kết quả quá lớn không in ra
giấy
3