S GIÁO D C & ĐÀO T OỞ Ụ Ạ
QU NG NAMẢ
K THI CH N H C SINH GI I L P 12 THPTỲ Ọ Ọ Ỏ Ớ
Năm h c 2013-2014ọ
Môn thi : TIN H CỌ
Th i gian :ờ 180 phút (không k th i gian giao để ờ ề)
Ngàythi : 02/10/2013
T ng quan v đ thiổ ề ề
Tên bài Bài làm D li u vàoữ ệ D li u raữ ệ
Bài 1 : Ph ng trình đng dươ ồ ư BL1.PAS BL1.INP BL1.OUT
Bài 2 : Dãy con dài nh tấBL2.PAS BL2.INP BL2.OUT
Bài 3 : Đng h m dài nh tườ ầ ấ BL3.PAS BL3.INP BL3.OUT
(Đ thi này g m có 2 trang)ề ồ
Bài 1. Ph ng trình đng d (6 đi m)ươ ồ ư ể
Cho ba s nguyên N, M và y (0< N <3000; 0< M <3000; 0< y <3000).ố
Yêu c u :ầ Hãy tìm t t c các s nguyên ấ ả ố x [0; M-1] sao cho xN y (mod M).
D li u vàoữ ệ : Ghi trong file text, tên file là BL1.INP g m ba s nguyên N, M, y.ồ ố
D li u ra ữ ệ : Ghi ra file text, tên file là BL1.OUT g m 1 dòng, li t kê t t c cácồ ệ ấ ả
s ốx tìm đc. Trong tr ng h p không tìm đc thì ghi -1.ượ ườ ợ ượ
BL1.INP BL1.OUT
20 13 9 2 3 10 11
Bài 2. Dãy con dài nh t ( 7 đi m)ấ ể
Cho m t dãy s nguyên g m N ph n t aộ ố ồ ầ ử 1, a2, ..., aN và m t s nguyên k.ộ ố
Gi thi t dãy cho luôn luôn t n t i m t dãy con có t ng các ph n t chia h t choả ế ồ ạ ộ ổ ầ ử ế
k.
Yêu c u ầ: Hãy tìm dãy con có nhi u ph n t nh t có t ng các ph n t chia h t choề ầ ử ấ ổ ầ ử ế
k.
D li u vào:ữ ệ Ghi trong file text, tên file là BL2.INP g m 2 dòng:ồ
- Dòng đu ghi hai s nguyên N và k ( 0<N< 1000; 0< k <1000).ầ ố
- Dòng ti p theo ghi N s nguyên aế ố i (0<ai 5000, i =1,..,N).
D li u ra : ữ ệ Ghi ra file text, tên file là BL2.OUT, g m:ồ
- Dòng đu ghi đ dài dãy con tìm đc.ầ ộ ượ
- Dòng ti p theo ghi các ph n t c a dãy con. ế ầ ử ủ
1
Đ CHÍNH TH CỀ Ứ
10 21 3 7
11 31 12 14
5 21 13 16
- Dòng cu i cùng ghi t ng các ph n t c a dãy con đóố ổ ầ ử ủ
BL2.INP BL2.OUT
10 17
12 32 14 11 22 5 25 44 52 17
8
12 32 14 11 5 44 52 17
187
Bài 3 . Đng h m dài nh t ( 7 đi m)ườ ầ ấ ể
Các nhà kh o sát đa ch t đã ghi l i đ sâu t i đa ng v i các v trí có thả ị ấ ạ ộ ố ứ ớ ị ể
đào đc mà không g p m ch n c ng m c a m t khu đt có d ng hình chượ ặ ạ ướ ầ ủ ộ ấ ạ ữ
nh t. Các s đo đc ghi l i trên m t b n đ g i là b n đ đ sâu. B n đ đậ ố ượ ạ ộ ả ồ ọ ả ồ ộ ả ồ ộ
sâu là m t hình ch nh t đc chia thành MxN ô vuông, m i ô vuông ghi m t sộ ữ ậ ượ ỗ ộ ố
nguyên bi u th đ sâu có th đào đc t i v trí đó c a khu đt. Ng i ta mu nể ị ộ ể ượ ạ ị ủ ấ ườ ố
đào m t đng h m thoát n c dài nh t c a khu đt này b t đu t m t ô cóộ ườ ầ ướ ấ ủ ấ ắ ầ ừ ộ
đ sâu nào đó (không nh t thi t b t đu các ô biên) và k t thúc m t ô tùy ý.ộ ấ ế ắ ầ ở ế ở ộ
Do n c ch y t n i cao xu ng n i th p, nên đng h m thoát n c khi đàoướ ả ừ ơ ố ơ ấ ườ ầ ướ
qua các ô ph i theo nguyên t c đi t ô có đ sâu nh h n đn ô chung c nh cóả ắ ừ ộ ỏ ơ ế ạ
đ sâu l n h n. ộ ớ ơ
Yêu c u ầ: Hãy đa ra đ dài t i đa c a đng h m thoát n c có th đào đc.ư ộ ố ủ ườ ầ ướ ể ượ
D li u vàoữ ệ : Ghi trong file text, tên file là BL3.INP g m hai dòng:ồ
- Dòng đu ghi hai s nguyên M và N ( 0<M ầ ố 100; 0 < N
100).
- M dòng ti p theo, m i dòng ghi N s nguyên aế ỗ ố i
(0< ai 100, i = 1,..,N).
D li u ra ữ ệ : Ghi ra file text tên file là BL3.OUT g m m t s nguyên là s ô màồ ộ ố ố
đng h m dài nh t đi qua.ườ ầ ấ
BL3.INP BL3.OUT
3 4
10 21 3 7
11 31 12 14
5 21 13 16
5
===H t===ế
2
H1
H NG D N CH MƯỚ Ẫ Ấ
MÔN : TIN H C 12Ọ
====
Yêu c u: Th i gian test m i b không quá 5 giây. Quá th i gian quy đnh không ầ ờ ỗ ộ ờ ị
cho đi m.ể
Bài 1 (6 đi m)ể Test 12 b , m i b 0,5độ ỗ ộ
Test BL1.INP BL2.OUT
1 20 13 9 2 3 10 11
2 10 4 1 1 3
3 3 4 5 -1
4 100 70 60 10 60
5 500 197 158 2 28 169 195
6 998 999 972 43 63 159 174 270 285 381 396 492 507 603 618 714 729
825 840 936 951
7 998 999 900 -1
8 2009 13 6 2
9 2008 1000 961 29 97 153 221 279 347 403 471 529 597 653 721 779 847
903 971
10 1972 22 14 6 16
11 2009 2008 512 2 504 1006 1508
12 2011 22 16 16
Bài 2 (7 đi m) ể Test 07 b , m i b 01 đi m. Chú ý: Tr ng h p thí sinh đa raộ ỗ ộ ể ườ ợ ư
ph ng án dãy con khác v i đáp án nh ng đúng v s l ng và t ng dãy con thìươ ớ ư ề ố ượ ổ
v n cho đi m t i đa (n u đó là ph ng án đúng)ầ ể ố ế ươ
Test BL2.INP BL2.OUT
1 10 17
12 32 14 11 22 5 25 44 52 17
8
12 32 14 11 5 44 52 17
187
2 10 5
1 6 11 5 10 15 20 2 4 9
8
6 11 5 10 15 20 4 9
80
3 12 6
2 4 5 6 7 18 9 21 4 11 1 3
11
2 4 5 6 18 9 21 4 11 1 3
84
4 11 19
23 11 19 12 21 37 1 55 66 10 38
9
23 11 19 12 21 1 55 10 38
190
5 10 6
6 7 5 1 9 7 8 99 90 10
9
6 7 5 1 9 7 99 90 10
234
6 BL26.INP 500
3
1 2 3 4 5…. 500
125250
7 BL27.INP 990
2 4 6 8….1980 999 (lo i s 72ạ ố
trong dãy)
982017
Bài 3 (7 đi m)ể Test 07 b , m i b 01 đi mộ ỗ ộ ể
Test BL3.INP BL3.OUT
1 3 3
2 4 3
1 5 6
2 3 7
6
2 5 5
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
1 2 3 4 5
20
3 4 5
10 2 3 4 1
11 3 4 5 1
12 3 7 6 3
8 8 8 9 7
8
4 4 4
1 1 7 4
1 4 1 5
2 3 2 1
1 1 1 7
4
5 BL35.INP 99
6 BL36.INP 101
7 BL37.INP 100
4