Đề thi HSG Tin 8-9

Sở Giáo Dục Đào Tạo



Tổngquan
 Kì Thi Chọn HsG LớP 9 thcs Năm Học 2008-2009
Đề thi môn :Tin học
(Thời gian 150 phút không kể thời gian giao đề)

(Đề thi gồm 2 trang )



Tên bài
Tên fie chương trình
Tên file dữ liệu
Tênfile kết quả
thời gian

Bài 1
Xếp diêm
hms.pas
hms.inp
hms.out
1s/test

Bài 2
Chu kỳ xâu
cyc.pas
cyc.inp
cyc.out
1s/test

Bài 3
Hoán vị có điều kiện
per.pas
per.inp
per.out
1s/test

Lập trình giải các bài toán sau:
Bài 1: Xếp diêm (4 điểm)
Với các que diêm có thể xếp được các số nguyên không âm, các chữ số thập phân có cách xếp như hình vẽ


Bờm có N que diêm và muốn xếp diêm thành bộ số chỉ giờ dạng hh:mm:ss( chuẩn 24 giờ ) sao cho dùng hết đúng N que diêm và thời điểm biểu diễn được là muộn nhất trong ngày .
Dữ liệu (file hms.inp) : Ghi duy nhất số nguyên N (1=Kết quả (file hms.out): Ghi thời điểm biểu diễn được theo định dạng hh:mm: ss(ghi số -1 nếu không có cách sắp sếp )
Ví dụ:

hms.inp
hms.out

12
11:11:11


Bài 2:Chu kì xâu(4 điểm )
Một xâu P được gọi là tiền tố của xâu A nếu tồn tại xâu B sao cho xâu PB (ghép B vào sau P) bằng xâu A. Một tiền tố P của A được gọi là tiền tố thực sự nếu P≠p P≠A
Xâu Q được gọi là xâu chu kì của xâu A nếu Q là một tiền tố thực sự cáu A và A là tiền tố của xâu QQ.Chẳng hạn abab và ababab là hai xâu chu kì của xâu abababa.Chu kì cực đại của A là xâu vhu kì dài nhất của hoặc xâu rỗng nếu A không có sâu chu kì .
cho một xâu S chỉ gồm các chữ cái ‘...hãy tính tổng dộ dài chu kì cực đại của tất cả các tiền tố của S .
Dữ liệu (cyc.inp)
Dòng 1 số nguyên N( 1<=N<=250 ) - đọ dài của xâu S
Dòng 2 xâu S
Kết quả (cyc.out):
Dòng 1: số nguyên kết quả
Ví dụ:

cyc.inp
cyc.out

8
babababa
24


Giải thích ví dụ:

Tiền tố
Chu kì cực đại

‘
‘’

‘
‘’

‘
‘

‘
‘

‘
‘

‘
‘


‘

‘
‘

Bài 3: Hoán vị có điều kiện ( 2 điểm)
Hoán vị của N sốnguyên dương dầu tiên là dãy A =( a1 a2 a3 ,..., an) trong đó mỗi số nguyên 1,2,...,n dều xuất hiện đúng một lần. Một dẫycon của A là dãy nhận đươc sau khi loại bỏ 0,1,2,.. phần tử của A và dữ nguyên phần còn lại .
xét N= 4 và A=(1,4,3,2) .Độ dài của dãy con tăng dài nhất của A là 2 .A có 3 dãy con tăng độ dài là 2 là(1,4 ), (1,3); (1,2).Dộ dài của dãy con giảm dài nhất của A là 3 .A chỉ có 1 dãy con giảm dài nhất là 3 (4,3,2).
Cho N và hai số nguyên P.Q ,hãy sxác