Đề thi học sinh giỏi năm học 2005  2006 môn : Tin học thời gian làm bài : 180 phút

Đại Học Quốc Gia TP. HCM
TRƯỜNG PHỔ THÔNG NĂNG KHIẾU
v v v v v v
ĐỀ THI HỌC SINH GIỎI 
NĂM HỌC 2005 - 2006
Môn : TIN HỌC
Thời gian làm bài : 180 phút
Ngày thi thứ hai : 15 tháng 11 năm 2005
TỔNG QUAN BÀI THI
Tên bài
Tên chương trình
File dữ liệu vào
File kết quả
BÀI 4
Chia dãy số
DAYSO.PAS
DAYSO..INP
DAYSO..OUT
BÀI 5
Các số La mã
LAMA.PAS
LAMA.INP
LAMA.OUT
BÀI 6
Làm đẹp thành phố
TPDEP.PAS
TPDEP.INP
TPDEP.OUT
Bài 4. Chia dãy số
Cho một dãy A gồm N số thực ( 1 ≤ N ≤ 1000). Người ta cần chia dãy này thành K (1 £ K £ N) dãy con, mỗi dãy gồm các số liên tiếp nhau: a1 … ai1; ai1+1… ai2; …; ai(k-1)+1… aN. Có nhiều cách chia như vậy ta cần tìm cách chia sao cho tổng L độ lệch bình phương của phép chia là nhỏ nhất. L được tính như sau:
Độ lệch trên một đoạn gồm các phần tử ai, ai+1, … aj là:
Trong đó TBCij là trung bình cộng của các số ai, ai+1, … aj.
Độ lệch L của phép chia là tổng độ lệch trên toàn bộ K đoạn.
Yêu cầu : Cho dãy A gồm N số và số K, Hãy xác định cách chia với tổng L là nhỏ nhất.
Dữ liệu vào : Cho trong file văn bản DAYSO.IN có nội dung:
Dòng đầu chứa 2 số N và K.
Các dòng trong N dòng tiếp theo chứa N số a1, a2, … aN.
Các số trên cùng một dòng cách nhau bởi khoảng trống.
Kết quả ra : Ghi vào file văn bản DAYSO.OUT tổng L tìm được với độ chính xác 3 chữ số sau dấu phẩy.
Ví dụ : 
DAYSO.INP
DAYSO.OUT
4 2
1 2 3 4
1.000
Bài 5 : Các số La mã
Các số nguyên dương không vượt quá 3999 được biểu diễn trong hệ cơ số La mã bằng cách dùng các ký hiệu số La mã : ‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’ và ‘M’. Để biểu diễn các số la mã người ta dùng bảng các số La mã cơ sở như sau :
Số thập phân
Số La mã
Số thập phân
Số La mã
1
I
90
XC
4
IV
100
C
5
V
400
CD
9
IX
500
D
10
X
900
CM
40
XL
1000
M
50
L
Biểu diễn số tự nhiên N (1≤N≤3999) trong hệ cơ số La mã nhận được bằng cách tìm số La mã cơ sở K lớn nhất có giá trị không vượt quá N. Ghi số La mã K nhận được. Sau đó lặp lại việc tìm kiếm với số N mới bằng N-K cho tới khi N=0. Ví dụ số 193 , đầu tiên ta có số La mã cơ sở lớn nhất không quá 193 là K=C (100) và được số N=93. Với N=93 ta tìm được số K=XC (90) và N=3. Với số 3 ta tìm được số K=I và N=2, tiếp tục ta có K=I, còn lại là N=1. Cuối cùng ta có K=I và N=0. Vì vậy biểu diễn của số 193 là : CXCIII
Cho một bảng A gồm H dòng và V cột, mỗi ô chứa một trong các ký số La mã :‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’ và ‘M’. Các dòng của bảng được đánh số từ 1 tới H từ trên xuống dưới, các cột của bảng được đánh số 1 tới V từ trái qua phải. Một đường đi trên bảng là một cách di chuyển xuất phát từ một ô nào đó tại cột 1 tới một ô nào đó tại cột V mà một bước chỉ được phép di chuyển sang ô chung cạnh cùng dòng bên phải, hoặc ô chung cạch cùng cột. Mỗi ô của bảng đi qua nhiều nhất 1 lần. Lần lượt ghi các ký số trên đường đi bắt đầu từ ô xuất phát ta được 1 xâu S chỉ chứa các ký số La mã.
Yêu cầu : Tìm một đường đi để xâu S nhận được là biểu diến một số tự nhiên N trong khoảng từ 1 tới 3999 và N là nhỏ nhất.
Dữ liệu vào : Từ file văn bản LAMA.INP trong đó : 
Dòng đầu chứa hai số H và V (1≤H,V≤15).
Dòng thứ i trong H dòng tiếp theo, mỗi dòng chứa V kí tự trên dòng i của bảng A.
Kết quả ra : Ghi vào file văn bản LAMA.OUT số N tìm được. Trong trường hợp không có số N thì ghi ra số -1.
Ví dụ : 
LAMA.INP
LAMA.OUT
7 3
CXI
CLX
XLX
IIX
CLX
CXV
MDM
49
Bài 6 : Làm đẹp thành phố
	Thị trưởng thành phố Anpha mong muốn thành phố mình đẹp hơn và ông lên kế hoạch thực hiện điều đó. Bản đồ thành phố được mô tả như một bảng gồm N dòng và M cột. Các dòng của bảng được đánh số từ 1 đến N từ trên xuống dưới, các cột của bảng được đánh số từ 1 tới M và từ trái qua phải. Mỗi một ô có một ngôi nhà và mỗi ngôi nhà có một nét đẹp riêng được đánh giá bởi một giá trị nào đó và gọi là giá trị đặc trương cho nét đẹp của ngôi nhà đó. Giá trị đặc trưng nét đẹp của ngôi nhà nằm ở ô giao giữa dòng i và cột j là Aij. 
	Để làm cho thành phố đẹp hơn, Thị trưởng tiến hành một số thao tác phá huỷ một số ngôi nhà. Mỗi thao tác phá huỷ bao gồm việc phá huỷ tất cả các ngôi nhà nằm trên cùng một dòng hoặc nằm trên cùng một cột trên bản đồ
Việc xác định thành phố đẹp đến mức độ nào người ta dùng một giá trị B tính theo công thức: 
B=S-K*C
	Trong đó B là giá trị đặc trưng cho nét đẹp của cả thành phố, S là tổng giá trị đặc trưng nét đẹp các ngôi nhà không bị phá, K là số thao tác phá huỷ thực hiện và C là một hằng số nguyên cho trước gọi là hệ số phá huỷ.
Yêu cầu : Giúp Thị trưởng có được thành phố với giá trị đặc trưng cho nét đẹp là lớn nhất bằng một số thao tác phá huỷ nào đó.
Dữ liệu vào : Từ file văn bản TPDEP.INP trong đó :
Dòng đầu chứa 3 số N, M và C (1≤N, M≤20, 0≤C≤100000),
Dòng thứ i trong N dòng tiếp theo chứa M số nguyên Ai1, Ai2, ... , AiM với giá trị tuyệt đối không vượt quá 1000. 
Các số trên một dòng được ghi cách nhau bởi ít nhất một khoảng trắng.
Kết quả ra : Ghi vào file văn bản TPDEP.OUT một số nguyên duy nhất là giá trị đặc trưng cho nét đẹp của thành phố lớn nhất tìm được.
Ví dụ : 
TPDEP.INP
TPDEP.OUT
3 5 4
-1 -1 -1 -1 -1
-1 1 -1 1 -1
-1 -1 -1 -1 -1
-9