HSG tin 9- Vĩnh Phúc 2006

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 (N≤1000). 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≤), tiếp theo nhập vào dãy (A) gồm N số a1, a2, .., aN. 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 S1 là một xâu con thuần nhất của S và P (P≥2) là số lần xuất hiện liên tiếp S1 trong S thì đoạn gồm P lần liên tiếp S1 trong S được viết thu gọn thành S1P.
+Nếu S2 là một xâu thu gọn của một xâu con trong S và Q (Q≥2) là số lần xuất hiện liên tiếp S2 thì đoạn gồm Q lần liên tiếp S2 được viết thành (S2)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