HSG tin 9- Vĩnh Phúc 2006
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (554.43 KB, 2 trang )
sở gd&đt vĩnh phúc
Đề chính thức
kỳ thi chọn hsg lớp 9 thcs năm học 2005-2006
đề thi môn: tin học
Thời gian làm bài: 150 phút, không kể thời gian giao đề
Bài 1. Tên file chơng trình đặt là BL1.PAS
Nhập từ bàn phím số nguyên dơng N (N1000). Hãy thông báo ra màn hình:
+Số cách phân tích N thành tổng của không quá 2 số nguyên tố (2 số không bắt buộc phải phân
biệt).
+Trong các cách phân tích ở trên đa ra cách mà tích hai số hạng trong tổng là lớn nhất (nếu chỉ
có một số hạng thì tích coi bằng chính số đó).
Ví dụ: Nhập N=10, ta có hai cách phân tích là: 10=3+7=5+5, khi đó thông báo ra màn hình 2
dòng: SO CACH PHAN TICH LA: 2.
CACH PHAN TICH CO TICH LON NHAT LA: 5+5
Bài 2. Tên file chơng trình đặt là BL2.PAS
Nhập từ bàn phím số nguyên dơng N (N 2 0), tiếp theo nhập vào dãy (A) gồm N số a
1
, a
2
, , a
N
.
Hãy tìm cách ghép các phần tử của (A) thành (N div 2) cặp, mỗi cặp có 2 số, mỗi số thuộc không quá 1
cặp, sao cho tổng của các tích 2 số trong các cặp là nhỏ nhất. Thông báo ra màn hình tổng nhỏ nhất tìm
đợc.
Ví dụ: Nhập N=7, dãy (A): 2 1 -2 0 3 4 -5 , ta ghép đợc thành 3 cặp số có tổng của các tích 2
số trong các cặp nhỏ nhất là (-5, 4), (3, -2) và (2, 0), giá trị tổng đó bằng: (-5)x4+3x(-2)+(2x0)=-26.
Khi đó phải đa ra màn hình dòng:
GIA TRI TONG NHO NHAT LA: -26
Bài 3. Tên file chơng trình đặt là BL3.PAS
Một xâu kí tự S đợc gọi là xâu thuần nhất nếu trong biểu diễn của nó chỉ gồm các chữ cái in
Tiếng Anh. Xâu thuần nhất S có thể đợc viết thu gọn theo qui tắc:
+Nếu S
1
là một xâu con thuần nhất của S và P (P2) là số lần xuất hiện liên tiếp S
1
trong S thì
đoạn gồm P lần liên tiếp S
1
trong S đợc viết thu gọn thành S
1
P.
+Nếu S
2
là một xâu thu gọn của một xâu con trong S và Q (Q2) là số lần xuất hiện liên tiếp S
2
thì đoạn gồm Q lần liên tiếp S
2
đợc viết thành (S
2
)Q
Ví dụ: với S=XCAABAABAABCCADADCAABAABAABCCADADY thì một trong những
xâu thu gọn của S là: X(C(A2B)3C2(AD)2)2Y (trong xâu không chứa bất kỳ kí tự trống nào).
Yêu cầu: Nhập từ bàn phím một xâu thu gọn của một xâu thuần nhất, hãy thông báo ra màn
hình độ dài của xâu thuần nhất. Dữ liệu vào là chuẩn không phải kiểm tra, độ dài xâu thu gọn không
quá 30 (không tính kí tự ngoặc đơn). Với xâu thu gọn nh trên thì thông báo ra màn hình dòng:
DO DAI XAU THUAN NHAT BAN DAU LA: 34
Bài 4. Tên file chơng trình đặt là BL4.PAS
Một bảng hình chữ nhật kích thớc MxN đợc chia thành M dòng, N cột (M, N nguyên dơng, có
giá trị không quá 10). Các dòng đợc đánh số từ 1 đến M từ trên xuống dới, các cột đợc đánh số từ 1 đến
N từ trái sang phải. Ô nằm trên dòng i, cột j gọi là ô (i, j). Trên tất cả các ô của bảng, mỗi ô có ghi một
số 0 hoặc 1.
Yêu cầu: Nhập từ bàn phím M, N và bảng hình chữ nhật ban đầu. Hãy tìm cách đổi chỗ giá trị
một số ô của bảng sao cho tập hợp tất cả các ô chứa số 1 sau khi đổi chỗ tạo thành một hình vuông và
số lần đỗi chỗ giá trị hai ô cho nhau là ít nhất. Dữ liệu vào đảm bảo luôn tồn tại cách đổi chỗ theo yêu
cầu. Thông báo ra màn hình bảng hình chữ nhật số ban đầu và sau khi thực hiện đổi xong chỗ các phần
tử cùng số lần đổi chỗ ít nhất các phần tử.
Ví dụ: Nhập M=N=4, nhập hình chữ nhật:
0 1 0 1
1 0 1 0
0 1 0 1
1 1 1 0
thực hiện đổi chỗ giá trị các ô nh sau:
-lần thứ nhất: đổi ô (1, 2) với ô (2, 2)
-lần thứ 2: đổi chỗ ô (1, 4) với ô (3, 1)
-lần thứ 3: đỗi chỗ ô (3, 3) với ô (3, 4).
Thông báo ra màn hình:
BANG BAN DAU:
0 1 0 1
1 0 1 0
0 1 0 1
1 1 1 0
BANG KET THUC:
0 0 0 0
1 1 1 0
1 1 1 0
1 1 1 0
SO LAN DOI CHO: 3
Hết
sở gd&đt vĩnh phúc
kỳ thi chọn hsg lớp 9 thcs năm học 2005-2006
hớng dẫn chấm môn: tin học
Bài 1. 4.0 điểm
Nhập N Số cách Cách có tích lớn nhất Điểm
13 2 2+11 0.75
88 4 41+47 0.75
134 6 67+67 0.75
256 8 107+149 0.75
568 13 257+311 0.50
894 34 433+461 0.50
Bài 2. 3.0 điểm
Nhập N Nhập (A) Thông báo Điểm
5 5 6 3 3 4 42 0.75
5 -5 -6 -3 -3 -4 42 0.75
6 1.1 1.2 -1.1 -1.2 -2.2 2.2 4.07 0.50
4 1000 2000 3000 4000 14000000 0.50
3 1000 2000000 2000 4000000000 0.50
Bài 3. 2.0 điểm
Nhập (A) Thông báo Điểm
A 1 0.50
(AB)2CD 6 0.50
X(C(A3B)3C2(AD)2)2Y 40 0.50
(X(C(A3B)3C2(AD)2)2Y)1000 40000 0.50
Bài 4. 1.0 điểm
Nhập M, N Bảng ban đầu Bảng kết thúc Số lần đổi Điểm
M=N=1 1 1 0 0.25
M=3, N=4 1 0 0 1
0 0 1 0
1 0 0 0
0 0 1 1
0 0 1 1
0 0 0 0
(có duy nhất cách xếp)
2 0.25
M=5, N=6 1 0 1 0 0 1
1 1 0 0 1 1
0 0 1 1 0 1
1 0 1 0 1 0
1 0 0 1 0 1
0 0 0 0 0 0 0 0 1 1 1 1
0 0 1 1 1 1 0 0 1 1 1 1
0 0 1 1 1 1 hoặc 0 0 1 1 1 1
0 0 1 1 1 1 0 0 1 1 1 1
0 0 1 1 1 1 0 0 0 0 0 0
(có đúng 02 cách xếp)
7 0.25
M=7, N=8 1 0 1 0 0 1 0 1
1 1 0 0 1 1 0 0
0 0 1 1 0 1 0 1
1 0 1 0 1 0 0 0
1 0 0 1 0 1 0 1
0 1 0 0 0 1 0 0
1 1 1 0 0 0 0 1
có đúng 3 cách xếp
cách 1: đỉnh ở (1, 1) và (5, 5)
cách 2: đỉnh ở (2, 2) và (6, 6)
cách 3: đỉnh ở (1, 2) và (5, 6)
13 0.25
-Nếu không đa ra đúng cách xếp ở bảng kết thúc hoặc thông báo số lần đổi chỗ sai thì không cho điểm.
