Đề thi chọn học sinh giỏi thành phố Đà Nẵng năm học 2007-2008 môn thi: Tin học - lớp 11

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 đích là một xâu chứa từ 2 đến 72 ký tự thường trong một dòng.
	Dữ liệu ra: Mỗi test ghi kết quả vào file PERMUTE.OUT số cấu hình riêng biệt tàu có thể có được trên một dòng.
	Ví dụ :
PERMUTE.INP
PERMUTE.OUT
4
aa
abba
abcd
abcde
1
6
12
18
------------------------------------ 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.