Đề thi chọn học sinh giỏi tỉnh năm học 2013 - 2014 môn: Tin học 11 - Vòng 2

SỞ GD&ĐT QUẢNG BÌNH 	KÌ THI CHỌN HSG TỈNH NĂM HỌC 2013-2014
	Khóa thi ngày 28 - 3 - 2014
 ĐỀ CHÍNH THỨC	Môn: Tin học
	LỚP 11 THPT - VÒNG II	
Họ và tên:  Thời gian: 180 phút (không kể thời gian giao đề)
Số báo danh: ..	 Đề gồm có 02 trang
ĐỀ RA
Sử dụng ngôn ngữ lập trình Turbo Pascal để lập trình giải các bài toán sau:
Câu 1: (3,0 điểm) Tổng dãy chia hết cho K	 SUMDIV.PAS
Cho dãy số nguyên A gồm N số a1, a2, ..., aN. 
Dãy B được gọi là dãy con của A nếu B nhận được từ A bằng cách lấy các số liên tiếp có tổng giá trị chia hết cho K.
(1 ≤ N ≤ 10000, 1 ≤ i ≤ N, -32000 ≤ ai ≤ 32000, 1 ≤ K ≤ 32000). 
Yêu cầu: Hãy tìm số lượng dãy con B khác nhau được tạo ra từ dãy A.
Dữ liệu vào: Ghi trong file văn bản SUMDIV.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N, là số lượng phần tử của dãy số A.
- Dòng 2: Ghi N số nguyên lần lượt là giá trị của các số trong dãy A, các số được ghi cách nhau ít nhất một dấu cách.
- Dòng 3: Ghi số nguyên dương K.
Dữ liệu ra: Ghi ra file văn bản SUMDIV.OUT, theo cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương D là số lượng dãy con tìm được.
Ví dụ:
SUMDIV.INP
SUMDIV.OUT
7 
3 4 1 4 3 2 6
5
7	
Câu 2: (3,5 điểm) Giải nén	UNZIP.PAS	
	Để tiết kiệm chi phí trong việc gửi và nhận dữ liệu thông qua các kênh truyền, các file văn bản trước khi được gửi đi đều được nén lại để giảm dung lượng bộ nhớ. Sau khi nhận được các file văn bản gửi đến, muốn đọc được nội dung thì các file vừa nhận phải được giải nén.
	Việc nén một xâu văn bản chỉ chứa các kí tự chữ cái in hoa được thực hiện như sau: Một đoạn liên tiếp các kí tự chữ cái giống nhau được thay bằng một đoạn kí tự mới gồm các kí tự chữ số thể hiện số lượng của chữ cái và tiếp theo sau là kí tự chữ cái đó (AAAAAAA được thay bằng 7A), nếu chỉ có một kí tự chữ cái thì giữ nguyên kí tự đó. Ví dụ: AAAAAABBBCDDD sẽ được nén lại là 6A3BC3D.
Việc giải nén là chuyển một xâu đã được nén trở về xâu gốc ban đầu trước khi nó được nén. Ví dụ: 6A3BC3D được chuyển thành AAAAAABBBCDDD.
Cho một file văn bản gồm nhiều dòng, mỗi dòng chứa một xâu văn bản đã được nén, file chỉ chứa tối đa 100 dòng (Mỗi xâu văn bản gốc trước khi nén có tối đa 255 kí tự).
Yêu cầu: Hãy thực hiện giải nén các xâu văn bản trên mỗi dòng trong file đã cho chuyển thành các xâu gốc ban đầu.
Dữ liệu vào: Ghi trong file văn bản UNZIP.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N là số lượng xâu trong file văn bản.
- Dòng thứ i trong N dòng tiếp theo: Mỗi dòng ghi một xâu đã được nén.
Dữ liệu ra: Ghi ra file văn bản UNZIP.OUT theo cấu trúc như sau:
Dữ liệu được ghi trên N dòng, dòng thứ i ghi xâu đã được giải nén tương ứng với xâu đã được nén trong file dữ liệu vào.
Ví dụ:
UNZIP.INP
UNZIP.OUT
2
6A3BC3D
5ABC
AAAAAABBBCDDD
AAAAABC
Câu 3: (3,5 điểm) Bánh sinh nhật	 SOCOCAKE.PAS
Nhân dịp sinh nhật, Tèo được bố mẹ mua cho một cái bánh hình chữ nhật. Tèo sẽ dùng dao cắt chiếc bánh làm 4 phần cho bố, mẹ, chị và cho mình. Bánh được trang trí theo dạng lưới gồm N×N ô vuông, trên mỗi ô có thể được gắn một viên sô cô la hoặc là không. Tèo sẽ cắt bánh bằng một nhát cắt dọc và một nhát cắt ngang. Vì trong gia đình Tèo ai cũng thích sô cô la nên Tèo muốn cắt bánh sao cho phần mình nhận được có nhiều sô cô la nhất và trên mỗi phần còn lại có sô cô la không ít hơn phần của mình. 
Yêu cầu: Hãy tìm cách giúp Tèo cắt bánh theo ý muốn của mình.
Dữ liệu vào: Ghi trong file văn bản SOCOCAKE.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên N (1 ≤ N ≤ 100).
- N dòng tiếp theo: Mỗi dòng ghi một xâu có độ dài N thể hiện chiếc bánh. Kí tự “#” thể hiện một ô trên chiếc bánh được gắn sô cô la, còn kí tự “.” thể hiện một ô trên chiếc bánh không gắn sô cô la.
Dữ liệu ra: Ghi ra file văn bản SOCOCAKE.OUT theo cấu trúc:
- Dòng 1: Ghi số nguyên K là số sô cô là nằm trên phần bánh của Tèo.
- Dòng 2: Ghi số nguyên u thể hiện nhát cắt giữa dòng thứ u và dòng thứ u + 1.
- Dòng 3: Ghi số nguyên v thể hiện nhát cắt giữa cột thứ v và cột thứ v + 1.
Ví dụ:
SOCOCAKE.INP
SOCOCAKE.OUT
8
. . # . . # . .
. # # . . # . .
. . . . . . # .
. # # . . . . .
. . # . # . . .
. . . . . . # .
. . . . . . . .
. . # . . # . .
3
3
4
(Có 55% số test với N ≤ 50; 45% số test với N >50).
....... Hết .......