SỞ GIÁO DỤC – ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 CẤP TỈNH
THỪA THIÊN HUẾ NĂM HỌC 2005 – 2006
Đề chính thức Môn thi: TIN HỌC, vòng 1
Số báo danh: Thời gian: 150 phút (không kể thời gian giao đề)

HỌC SINH LẬP TRÌNH GIẢI HAI BÀI TOÁN SAU:
(đề thi có 3 trang)
Tổng quan về các file:
Tên bài Tên file nguồn
Tên file văn bản chứa dữ liệu vào, ra
Vào Ra
Bài toán cổ TOANCO.PAS TOANCO.INP TOANCO.OUT
Kim tự tháp TUTHAP.PAS TUTHAP.INP TUTHAP.OUT
BÀI 1: BÀI TOÁN CỔ.
Tương truyền rằng, ngày xưa có một mưu sĩ thấy dân chúng quá
nghèo khổ nên ông ta đã đến thách đố đánh cờ cùng nhà vua nhằm lấy thóc
trong kho đem phân phát cho dân nghèo. Nhà vua ra điều kiện nếu đánh thua
nhà vua thì mưu sĩ sẽ bị chém đầu, ngược lại mưu sĩ sẽ được trọng thưởng
bằng vật chất. Nếu đánh thắng cờ với nhà vua, mưu sĩ chỉ xin một điều đó là
trong mỗi ô cờ gồm 8x8 ô thì lần lượt bỏ vào ô thứ 1: 1 hạt thóc, ô thứ 2:
1x2 hạt thóc, ô thứ 3: 1x2x3 hạt thóc,… cho đến ô cuối cùng. Nhà vua nghe
qua rất khoái chí và đồng ý ngay. Sau lần đấu cờ đó nhà vua đã mất rất nhiều
kho lương thực cho dân nghèo.
Do bản tính hiếu thắng của nhà vua, ông vẫn tiếp tục thách đấu với
những tay cao thủ cờ khác trong thiên hạ nhưng bây giờ rút kinh nghiệm ông
chỉ xuất trong kho ra bây giờ không phải là thóc nữa mà là vàng. Nguyên tắc
để nhận được vàng sau khi đánh thắng nhà vua như sau:
1. Mỗi ô trong bàn cờ có một số. Con số này được gán vào như sau:
- Ô số 1: 1
- Ô số 2: 1x2 = 2
- Ô số 3: 1x2x3 = 6

trúc được xây dựng cũng phải có hình tam giác. Chính quyền địa phương
nhiều nơi đã tìm kiếm rất vất vả, cuối cùng cũng chọn ra được một số khu
vườn như thế. Dưới đây là một trong các khu vườn có hình dáng cần tìm:
2
Tuy nhiên trên các khuôn viên lại có một số công trình, cây cối, … đã
có trước đây cần phải duy trì. Họ phải lại bắt đầu tính toán để tìm ra được
một ô đất cũng có hình tam giác mà diện tích của nó là lớn nhất. Hình vẽ
trên cho ta thấy các ô có màu đen chính là các công trình đã có; các ô trắng
là đất trống và đường viền đậm là khu vực được đánh dấu để xây dựng.
Yêu cầu: Hãy lập trình tìm ra khu đất có diện tích lớn nhất theo yêu
cầu của các nhà khoa học đã đưa ra.
Dữ liệu vào: gồm nhiều dòng:
- dòng đầu tiên là n, n là độ rộng của tam giác (1 ≤ n ≤ 100).
- n dòng tiếp theo chứa các ký tự {#, -} đại diện các hàng của tam
giác. Ký tự ‘#’ là màu đen và ‘-’ màu trắng. Trong mỗi tam giác,
số ký tự ‘#’ và ‘-’ là lẻ và giảm dần từ 2n – 1 xuống 1.
Dữ liệu ra: chỉ một dòng chứa một số nguyên là kết quả tìm ra khu
đất lớn nhất cần xây dựng có nội dung “Dien tich lon nhat:” tiếp theo là diện
tích tìm được. Nếu không tìm ra cũng trả lời “KHONG TIM RA”
Ví dụ, với hình trên ta có dữ liệu vào, ra như sau:
Dữ liệu vào Dữ liệu ra
5
#-##----#
-----#-
---#-
-#-
-
Dien tich lon nhat: 9

- Giám thị không giải thích gì thêm.

23
24
5
6
7
8
9
10
14
15
24
25
26
124
125
624
625
3124
3125
9999
100
200
501
5001
7029
7501
5 -> 2
6 -> 2
7 -> 4
8 -> 2

3
-----
--#
-
4
3
-#-#-
---
#
5
---------
-------
-----
---
-
10
--#--#--#---#---#--
---------#-------
--#-##----#----
---------#---
#-#------#-
--#-#-#--
------#
--#--
---
-
20
----------------#------#-#------#--#---
#------#------##-#--#------------##--
-#--------#--##--------##-#---#-#--

5
-----------##-----##--#---#--------
--------------#---#---#-------#--
----#-----#----#-----#---#-#--#
---##-----#--#------#--#----#
-----------#-#--##---------
-------------#--------#-#
-------#--------#-----#
--#-##-#----------#--
--#--#----#-##--#-#
--##--#--#-#-----
-------#------#
-------#-----
------#--#-
----#-#--
--#--##
#----
--#
#
40
#----------#---------------##------#-#--#---------------##--##---#-#-#------#--
-----#------------#--------#-#-#----#--------#-#-------------##-####--#------
#----#------#------##--#------#-----#-#-----------#--#-#-------#-#---------
---#---##-#--##--#-#------##-#-----##---#--#--#--#-#-#--##--#-##---#----#
-----#---##----#----------------#------------------#----------------#--
------------------##-----#--#-##----#--####---##-----#--##------##--#
---#------#-----#----------#-----#--#--#-#------#----#----#----#---
---##-------------------#-----#-#--#----#-#-----##-------#----#--
-##---------#---------#----#----##----------------#------------
---#--------##------###--------#--#--#-#---#-------#-------#-

100
6