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 11
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
Cấp số cộng
BL1.*
DCSCMAX.INP
DCSCMAX.OUT

2
Subsequence
BL2.*
PERMUTE.INP
PERMUTE.OUT

Dấu * trong tên file chương trình sẽ được thay thế bằng PAS hoặc PP tùy thuộc môi trường thí sinh chọn tương ứng là Borland Pascal hoặc Free Pascal.
Hãy lập trình giải các bài toán sau đây:

Bài 1: Cấp số cộng
Cho dãy số nguyên A1,A2,...,AN. Ta gọi dãy con của dãy đã cho là dãy thu được từ việc xoá khỏi dãy đã cho một số số hạng của nó và giữ nguyên thứ tự của các số hạng còn lại. Bản thân dãy đã cho cũng là một dãy con của chính nó.
Yêu cầu: Trong số các dãy con của dãy đã cho lập thành một cấp số cộng với công sai d, hãy tìm một dãy con gồm nhiều phần tử nhất, hoặc thông báo là dãy đã cho không chứa dãy con như vậy.
Dữ liệu vào: Đọc từ file văn bản DCSCMAX.INP gồm có:
- Dòng đầu tiên chứa số nguyên dương N.
- Dòng thứ i trong số N dòng tiếp theo chứa số hạng thứ i của dãy số đã cho.
Kết quả: Ghi ra file văn bản DCSCMAX.OUT gồm có:
- Dòng đầu tiên ghi hai số 0 (cách nhau một dấu cách) nếu không tìm được dãy thoả mãn yêu cầu.
- Trái lại, dòng đầu tiên ghi 2 số k và d (cách nhau một dấu cách), trong đó k là số lượng phần tử và d là công sai của dãy con tìm được và ghi tiếp trên k dòng tiếp theo, mỗi dòng một số là vị trí của phần tử của dãy con tìm được theo thứ tự xuất hiện của chúng trong dãy đã cho.
Hạn chế: 1<=N<=10000; -30000<=A[i]<=30000, i=1..N
Ví dụ:
DCSCMAX.INP
DCSCMAX.OUT

10
3
9
8
90
15
19
23
21
11
27
5 6
1
2
5
8
10

Bài 2: Đường hoán đổi
Một công ty tàu hoả đã xây dựng các đường hoán đổi, Sự bố trí các đường được chỉ trong hình sau :

Hình B-1: Bố trí các đường hoán đổi
Một tàu có thể kéo từ 2 đến 72 toa. Có 26 loại toa xác định bởi 26 ký tự thường “a..z”, các toa giống nhau không thể phân biệt được và mỗi toa, ta không quan tâm đến hướng. Với dãy ký tự thường độ dài từ 2 đến 72 cho biết cấu hình của một tàu.
Nhờ vào các đường hoán đổi ta có thể biến đổi cấu hình đích của một tàu, một tàu được chia thành 2 tàu con ở một vị trí tuỳ ý (ưu tiên để vào đường kho). Mỗi tàu con có thể có hướng ngược lại (dùng đường đảo ngược). Cuối cùng 2 tàu con được nối theo thứ tự khác để tạo thành cấu hình cuối cùng. Chú ý rằng việc đảo ngược không bắt buộc với mỗi tàu con.
Ví dụ, cấu hình đích là “abcd”, tàu chia thành 2 tàu con 3:1, 2:2 hoặc 1:3 toa. Mỗi sự chia nhỏ, cấu hình cuối cùng có thể như sau (‘+” mô tả vị trí nối cuối cùng):
[3:1]
abc+d cba+d d+abc d+cba
[2:2]
ab+cd ab+dc ba+cd ba+dc cd+ab cd+ba dc+ab dc+ba
[1:3]
a+bcd a+dcb bcd+a dcb+a
Trừ các trường hợp giống hệt nhau ta có 12 cấu hình riêng biệt.
Yêu cầu : Cho 1 cấu hình đích, tính số cấu hình riêng biệt được xây dựng dùng đường hoán đổi mô tả trên.
Dữ liệu vào: Đọc từ file PERMUTE.INP có dạng như sau :
Số test = m 1st test 2nd test ... m-th test
Mỗi test hiện diện một cấu hình