Tài liệu đề thi học sinh giỏi tin lớp 9 đà nẵng

Së gi¸o dôc ®µo t¹o Thµnh phè ®µ n½ng Kú THi CHäN häc sinh giái THµnh phè 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 BL1.PAS SORT.INP SORT.OUT CIRCLE.INP CIRCLE.OUT 1 Xếp lại dãy số 2 Vòng tròn nguyên tố BL2.PAS Tên file kết quả 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: a 1, 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 4 11 22 33 44 SORT.OUT 11 33 22 11 33 44 22 11 44 22 44 11 22 44 33 33 11 22 33 11 44 33 44 11 44 22 11 44 22 33 10 44 22 33 33 11 44 22 22 33 11 Bài 2: Vòng tròn nguyên tố 1 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. 1 6 4 5 3 2 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 3   CIRCLE.OUT 1 4 3 2 5 6 1 6 5 2 3 4 2 CIRCLE.INP 4 CIRCLE.OUT 1 2 3 8 5 6 1 2 5 8 3 4 1 4 7 6 5 8 1 6 7 4 3 8 4 7 7 3 5 4 6 2 2 ------------------------------------ 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. 2