HSG tin 9 tỉnh Vĩnh Phúc 2007

SỞ GD&ĐT VĨNH PHÚC
------------------
ĐỀ CHÍNH THỨC
KỲ THI CHỌN HSG CẤP THCS NĂM HỌC 2006-2007
ĐỀ THI MÔN: TIN HỌC
Thời gian làm bài: 150 phút, không kể thời gian giao đề.
------------------------------


Lưu ý: đề thi có 02 trang

Câu 1. Sắp xếp mảng 2 chiều – tên file chương trình: BL1.PAS
Cho mảng 2 chiều A có M dòng, N cột. Các dòng được đánh số từ 1 đến M từ trên xuống, các cột được đánh số từ 1 đến N từ trái sang. Mỗi phần tử của mảng là một số nguyên.
Yêu cầu: Sắp xếp các phần tử của mảng sao cho trên mỗi dòng từ trái sang tạo thành một dãy không giảm và trên mỗi cột từ trên xuống tạo thành một dãy không giảm.
Dữ liệu vào: đọc từ file văn bản có tên BL1.INP có cấu trúc
-Dòng đầu tiên ghi hai số nguyên dương M, N (M, N≤100).
-Dòng thứ i trong số M dòng tiếp theo ghi N số nguyên tương ứng của mảng A. Mỗi phần tử của A có giá trị tuyệt đối không quá 100000.
Dữ liệu ra: ghi vào file văn bản BL1.OUT mảng A có M dòng, N cột sau khi sắp xếp theo yêu cầu.
Hai số liên tiếp trong các file dữ liệu vào và ra cách nhau ít nhất một kí tự trống.
Ví dụ:
BL1.INP
BL1.OUT

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

Câu 2.Xâu kí tự - tên file chương trình: BL2.PAS
Cho hai xâu kí tự S1 và S2 chỉ gồm các kí tự là các chữ cái tiếng Anh. Ta gọi S1 là một mẫu của S2 nếu có thể ghép một số kí tự của S2 để được S1.
Yêu cầu: đếm số mẫu S1 được xây dựng từ S2 thỏa mãn: mỗi kí tự của S2 thuộc không quá một mẫu S1, hai cách xây dựng một mẫu S1 từ S2 mà chỉ khác nhau vị trí ghép các kí tự được coi là một cách.
Dữ liệu vào: đọc từ file văn bản có tên BL2.INP gồm 02 dòng:
-Dòng đầu tiên, bắt đầu từ đầu dòng ghi xâu S1.
-Dòng thứ hai, bắt đầu từ đầu dòng ghi xâu S2.
Mỗi xâu kí tự có độ dài không quá 255.
Dữ liệu ra: ghi vào file văn bản BL2.OUT theo cấu trúc:
-Dòng đầu tiên ghi số nguyên S là số cách xây dựng S1 từ S2 (S=0 nếu không có cách nào).
-Nếu S≠0 thì mỗi dòng trong số S dòng tiếp theo ghi chỉ số của các kí tự trong S2 được lấy để ghép thành một mẫu S1, các chỉ số này được ghi theo thứ tự xuất hiện của các kí tự trong xâu S1. Hai số liên tiếp ghi cách nhau ít nhất một khoảng trống.
Ví dụ:
BL2.INP
BL2.OUT

abcd
bcdagdhbscgahacd
2
4 1 2 3
12 8 10 6

Giải thích ví dụ: Ta có S1=, S2=, khi đó ta có tối đa 02 mẫu S1 được xây dựng từ các kí tự của S2 như sau:
Mẫu 1: gồm các kí tự ở các vị trí: 4, 1, 2, 3 trong S2 và theo thứ tự các kí tự xuất hiện trong S1.
Mẫu 2: gồm các kí tự ở các vị trí: 12, 8, 10, 6 trong S2 và theo thứ tự các kí tự xuất hiện trong S1.
Sau khi xây dựng xong 02 mẫu trên thì dễ thấy trong S2 không thể xây dựng thêm được mẫu S1 nào nữa.

Câu 3. Phân chia dãy số - tên file chương trình: BL3.PAS
Cho dãy số nguyên A có N phần tử: A1, A2, ..., AN.
Yêu cầu: tìm một cách phân chia tất cả các phần tử của tập {1, 2, ..., N} thành các tập con thỏa mãn đồng thời các điều kiện sau:
-Tổng các phần tử của A có chỉ số thuộc cùng một tập con chia hết cho số nguyên dương M cho trước.
-Hai tập con khác nhau không có phần tử chung.
-Số tập con là nhiều nhất.
Dữ liệu vào: đọc từ file văn bản có tên BL3.INP, có cấu trúc:
-Dòng đầu tiên ghi hai số nguyên dương N, M (N≤100, M≤1000).
-Dòng thứ hai ghi các số thuộc dãy A, theo thứ tự từ A1 đến AN.
Dữ liệu ra: ghi vào file văn bản có tên BL3.OUT theo cấu trúc:
-Dòng đầu