Dethigioitin9Danang07-08-dapan

Sở giáo dục đào tạo Kỳ THi CHọN học sinh giỏi THành phố
Thành phố đà nẵng năm học 2007-2008
------------------ ------------------------------- Môn thi : Tin học - Lớp 9
Thời gian làm bài 150 phút
(Không tính thời gian giao đề)

Đề chớnh thức:
TỔNG QUAN ĐỀ THI
Đề thi gồm có 02 trang
TT
Tên bài
Tên file chương trình
Tên file dữ liệu
Tên file kết quả

1
Xếp lại dãy số
BL1.PAS
SORT.INP
SORT.OUT

2
Vòng tròn nguyên tố
BL2.PAS
CIRCLE.INP
CIRCLE.OUT


Hãy lập trình giải các bài toán sau đây:
Bài 1: Xếp lại dãy số
Cho dãy số nguyên dương đôi một khác nhau: a1, a2, ..., an. Một hoán vị của dãy số là một cách sắp xếp khác các số hạng của dãy. Hãy liệt kê tất cả các hoán vị của dãy đã cho thoả mãn: giữa hai phần tử bất kỳ M và N trong hoán vị đó, không tồn tại phần tử P nào của hoán vị để:2P = M + N.

Ví dụ: Với dãy: 11, 22, 33, 44 thì
Hoán vị 33 11 22 44 là thoả mãn điều kiện trên
Hoán vị 11, 44, 22, 33 không thoả mãn vì có phần tử P = 22 nằm giữa hai phần tử M = 11 và N = 33 mà: 22 * 2 = 11 + 33.

Dữ liệu vào: Đọc từ file văn bản SORT.INP. Các số trên 1 dòng cách nhau ít nhất 1 dấu trống
Dòng 1: Chứa số n (2 ( n ( 11)
Dòng 2: Chứa các số a1, a2, ..., an của dãy (1 ( ai ( 100).

Dữ liệu ra: Ghi ra file văn bản SORT.OUT. Các số trên 1 dòng cách nhau ít nhất 1 dấu trống
K dòng đầu, mỗi dòng ghi 1 hoán vị tìm được.
Dòng cuối cùng ghi số lượng hoán vị tìm được (K)

Ví dụ:

SORT.INP

SORT.OUT

4
11 22 33 44

11 33 22 44
11 33 44 22
22 11 44 33
22 44 11 33
22 44 33 11
33 11 22 44
33 11 44 22
33 44 11 22
44 22 11 33
44 22 33 11
10




Bài 2: Vòng tròn nguyên tố
Một vòng tròn chứa 2n vòng tròn nhỏ (Xem hình vẽ). Các vòng tròn nhỏ được đánh số từ 1 đến n theo chiều kim đồng hồ. Cần điền một số tự nhiên từ 1 đến 2n vào mỗi vòng tròn nhỏ (mỗi số chỉ được phép điền một lần) sao cho tổng của hai số trên hai vòng tròn nhỏ liên tiếp là số nguyên tố. Số điền ở vòng tròn nhỏ 1 luôn là số 1.


Dữ liệu vào: Đọc từ file văn bản CIRCLE.INP gồm chỉ một dòng chứa số nguyên dương n
(1 < n < 10).
Dữ liệu ra: Ghi ra file văn bản CIRCLE.OUT có cấu trúc như sau:
k dòng đầu, mỗi dòng ghi các số trong các vòng tròn nhỏ bắt đầu từ vòng tròn nhỏ 1 đọc theo thứ tự của các vòng tròn nhỏ, mỗi số cách nhau một dấu cách.
Dòng cuối cùng ghi số lượng các cách điền số tìm được (k).

Ví dụ:
CIRCLE.INP
CIRCLE.OUT

CIRCLE.INP
CIRCLE.OUT

3
1 4 3 2 5 6
1 6 5 2 3 4
2

4
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
4


------------------------------------ HẾT --------------------------------------
Thí sinh không được sử dụng tài liệu dưới mọi hình thức.
Giám thị không giải thích gì thêm.

Sở giáo dục đào tạo Kỳ THi CHọN học sinh giỏi THành phố
Thành phố đà nẵng năm học 2007-2008
------------------ ------------------------------- Môn thi : Tin học - Lớp 9
Thời gian làm bài 150 phút
(Không tính thời gian giao đề)

HƯớng dẫn chấm:

Bài 1: (5 điểm, mỗi test 1 điểm)
CIRCLE1.INP
3

CIRCLE1.OUT
1 4 3 2 5 6
1 6 5 2 3 4
2
CIRCLE2.INP
4

CIRCLE2.OUT
1 2 3 8 5 6 7 4
1 4 7 6 5 8 3 2
1 2 5 8 3 4 7 6