Đề HSG tin học ĐBSCL

SỞ GD&ĐT BẠC LIÊU KỲ THI HSG ĐBSCL LẦN THỨ 16 - NĂM 2009

Đề thi đề nghị Môn: Tin học
(Gồm 3 câu) Thời gian: 180 phút (Không kể thời gian giao đề)

ĐỀ:

I. CẤU TRÚC ĐỀ:

Câu
Tên bài
Tên file
Input
Output
Điểm

1
Cặp số song sinh
S3.pas
S3.inp
S3.out
6

2
Điền khuyết xâu kí tự
Fs.pas
Fs.inp
Fs.out
7

3
Dãy đặc biệt
Ddb.pas
Ddb.inp
Ddb.out
7


II. CÂU HỎI

Câu 1 (6 điểm) - Cặp số song sinh
Hai số a, b được gọi là cặp số song sinh nếu như ở dạng biểu diễn nhị phân thì hai số này không được sai khác nhau quá 1 bit.
Yêu cầu: Cho trước hai số nguyên dương a và b (a, b đều nhỏ hơn 1.000.000.000). Hãy kiểm tra hai số a, b có phải là cặp số song sinh hay không.

Input: File văn bản s3.inp cấu trúc như sau:
Gồm một số dòng (nhỏ hơn 1.000.000);
Mỗi dòng chứa 2 số cần kiểm tra;
Mỗi số trên dòng cách nhau ít nhất một khoảng trắng.

Output: File văn bản s3.out cấu trúc như sau:
Gồm 1 dòng, là những con số 0 hoặc 1 đứng liền nhau tạo thành một dãy số nhị phân.
Tính từ trái sang phải, kí tự thứ i là 1 nếu tại dòng thứ i của file input chứa cặp số song sinh; Ngược lại kí tự tại vị trí thứ i là 0

Ví dụ

S3.inp

S3.out

3
8 9

11



Câu 2 (7 điểm) - Điền khuyết xâu kí tự
Cho trước 2 xâu ký tự a, b (chiều dài của mỗi xâu không quá 100).
Yêu cầu: Viết chương trình bổ sung một số ký tự vào a và một số ký tự vào b để hai xâu a và b trở nên giống nhau (phân biệt chữ hoa, thường). Tổng số kí tự bổ sung vào là ít nhất.
Input: File văn bản fs.inp cấu trúc như sau:
Bao gồm một số dòng (là số chẵn, có thể lên đến 10.000 dòng).
Mỗi dòng là một xâu kí tự (không quá 100 kí tự).
Output: File văn bản fs.out cấu trúc như sau:
Gồm một số dòng (là số dòng của file input chia 2)
Dòng thứ i chứa xâu kí tự là kết quả của việc bổ sung 2 xâu tại dòng thứ i*2-1 và i*2 trên file input.
Ví dụ:

Fs.inp



Abcde
Abdf

Abcdef


Câu 3 (7 điểm) - Dãy đặc biệt
Dãy số an cho trước được gọi là dãy đặc biệt nếu thỏa 2 điều kiện :
n là số chính phương;
Các phần tử trong an đôi một khác nhau;
Các phần tử trong an có thể lần lượt sắp xếp vào ma trận vuông
để
tạo thành một ma phương.
Chú ý: Ma phương là một ma trận vuông có tính chất sau: tổng các phần tử trên từng dòng bằng tổng các phần tử trên từng cột và cũng bằng tổng các phần tử trên 2 đường chéo.
Yêu cầu: Cho dãy an (với -10.000 < ai < 10.000; n là số nguyên dương nhỏ hơn 3000). Viết chương trình kiểm tra xem dãy an có phải là dãy đặc biệt hay không. Nếu phải thì hãy xuất ma phương ra còn không phải thì xuất ra dòng chữ “khong phai day dac biet”.
Input: file văn bản ddb.inp. Dòng đầu tiên chứa số n. Dòng tiếp theo chứa n số lần lượt là các phần tử trong dãy. Mỗi số cách nhau ít nhất một khoảng trắng.
Output: file văn bản ddb.out. Dòng đầu tiên chứa số m là cấp của ma phương hoặc là chứa dòng chữ “khong phai day dac biet”. Nếu dòng đầu tiên chứa số m thì m dòng tiếp theo mỗi dòng chứa m số là lượt là các phần tử của ma phương (mỗi số cách nhau 1 khoảng trắng).
Ví dụ:
ddb.inp

ddb.out

5
2 4 3 5 6

khong phai day dac biet

 (Vì n không phải là số chính phương)
--Hết--