Đề thi HSG12 Tỉnh Nghệ An Năm 2009

Sở GD&ĐT Nghệ An
Kì thi chọn học sinh giỏi tỉnh khối 12
Năm học 2008 - 2009



Môn thi: tin học 12 THPT- bảng A
Thời gian làm bài: 180 phút


Bài 1: (6,0 điểm) Kho an toàn
Nhà máy sản xuất vũ khí có nhiều kho hàng và các kho hàng có lính canh gác. Các kho hàng và lính canh được thể hiện trên ma trận m dòng, n cột. Kho hàng được gọi là Kho an toàn nếu xung quanh các kho đó có 8 lính canh.
Hãy lập trình đưa ra vị trí các Kho an toàn.
Dữ liệu: Vào từ tệp văn bản ANTOAN.INP
- Dòng đầu tiên là hai số nguyên m và n (0 < m, n ≤ 100).
- m dòng tiếp theo mỗi dòng có n số 0 hoặc 1 thể hiện kho hàng và lính canh (kho hàng kí hiệu: 0, lính canh kí hiệu: 1).
- Các số trên cùng một dòng ghi cách nhau một dấu cách.
Kết quả: Ghi ra tệp văn bản ANTOAN.OUT
- Nếu có Kho an toàn thì ghi vị trí của các kho đó (chỉ số dòng và chỉ số cột).
- Nếu không có Kho an toàn thì ghi – 1.
- Các số trên cùng một dòng ghi cách nhau một dấu cách.
Ví dụ:

ANTOAN.INP
ANTOAN.OUT

4 5
1 1 1 0 1
1 0 1 1 1
1 1 1 0 1
0 0 1 1 1
2 2
3 4




Bài 2: (6,0 điểm) Tổng các chữ số
Cho một số tự nhiên A có N chữ số (N <= 200). Hãy tính tổng các chữ số của số A và cho biết chữ số lớn nhất là chữ số mấy và ở những vị trí nào tính từ phải qua trái.
Dữ liệu: Vào từ tệp văn bản CHUSO.INP, ghi một số tự nhiên A.
Kết quả: Ghi ra tệp văn bản CHUSO.OUT có cấu trúc như sau:
- Dòng thứ nhất ghi tổng các chữ số.
- Dòng thứ 2 ghi chữ số lớn nhất.
- Dòng thứ 3 ghi các vị trí xuất hiện của chữ số lớn nhất.
- Các số trên cùng một dòng ghi cách nhau một dấu cách.
Ví dụ:
CHUSO.INP
CHUSO.OUT

43210874254678231

67
8
4 12



Bài 3: (5,0 điểm) Xâu con
Cho trước hai xâu kí tự S1 và S2. Viết chương trình tính số lần lặp lại của xâu S1 trong xâu S2.
Dữ liệu: Vào từ tệp văn bản XAU.INP gồm:
- Dòng đầu tiên chứa xâu S1.
- Dòng thứ hai chứa xâu S2.
Kết quả: Ghi ra tệp văn bản XAU.OUT:
- Chỉ một dòng duy nhất ghi số lần lặp lại của xâu S1 trong xâu S2.
Ví dụ:
XAU.INP
XAU.OUT

aba
bababababa
4


Bài 4: (3,0 điểm) Hoán vị
Cho một mảng A gồm N số là một hoán vị từ 1 đến N. Một dãy con của dãy trên là một đoạn liên tục từ u đến v (u <= v).
Yêu cầu: Tìm tất cả các dãy con sao cho dãy con đó cũng là một hoán vị của các số liên tiếp bắt đầu từ 1.
Dữ liệu: V