SỞ GD&ĐT V
ĨNH PHÚC
KÌ THI CHỌN HSG LỚP 9 CẤP TỈNH NĂM HỌC 2012-2013
ĐỀ THI MÔN: TIN HỌC
Thời gian làm bài: 150 phút, không kể thời gian giao đề
(Đề thi có 02 trang)
Tổng quan về đề thi
Tên bài
Chương trình
Dữ liệu
Kết quả
Giới hạn
Điểm
Tiền xu
COINS.PAS
COINS.INP
COINS.OUT
1s/test
40
Bậc đối xứng
PALINDEG. PAS
PALINDEG.INP
PALINDEG.OUT
1s/test
40
Dãy con
CONFLICT. PAS
CONFLICT.INP
CONFLICT.OUT
1s/test
20

Bài 2. BẬC ĐỐI XỨNG
Xâu đối xứng là xâu đọc từ trái qua phải giống như đọc từ phải qua trái, chẳng hạn các xâu
′ ′, ′ ′ là các xâu đối xứng.
Người ta định ngh
ĩa b
ậc đối xứng của xâu , kí hiệu deg
( )
, như sau:
 Nếu không phải là xâu đối xứng hoặc có độ dài bằng 1 thì bậc đối xứng của bằng 0
(viết là: deg
( )
= 0)
ĐỀ CHÍNH THỨC
 Nếu là xâu đối xứng có độ dài lớn hơn 1, giả sử = … ( > 1), thì bậc đối xứng
của được tính theo công thức: deg
( )
= 1+deg
( )
, trong đó xâu là nửa trái của theo
ngh
ĩa:
= … với =
(
+1
)
div2.
Chẳng hạn:
 deg
(
′

 Dòng 1: số nguyên là bậc đối xứng của xâu .
Ví dụ
PALINDEG.INP
PALINDEG.OUT
bobobbobob
3
Bài 3. DÃY CON
Cho dãy số nguyên =( , ,…, ) và số nguyên dương . Hãy tìm cách xóa bỏ
trong dãy một số phần tử sao cho dãy con thu được có nhiều phần tử nhất đồng thời trong dãy con
này không có hai phần tử nào có tổng chia hết cho .
Chẳng hạn, với = 5, = 3, = (1,2,3,4,5), dãy con dài nhất thu được có độ dài 3, có 4
dãy con nh
ư v
ậy, đó là
(
1,2,3
)
;
(
1,3,4
)
;
(
2,3,5
)
;(3,4,5).
Dữ liệu (CONFLICT.INP)
 Dòng 1: hai số nguyên , (1 ≤ ≤ 10 ;2 ≤ ≤10 )
 Dòng 2: số nguyên , ,…, (
| |