ĐỀ THI THỬ HSG

SỞ GD&ĐT VĨNH PHÚC
TRƯỜNG THPT YÊN LẠC 2


KÌ THI KSCL ĐỘI TUYỂN HỌC SINH GIỎI KHỐI 11
ĐỀ THI MÔN TIN HỌC
NĂM HỌC 2017 - 2018
Thờigianlàmbài 180phút, khôngkểthờigiangiaođề.
Đềthigồm: 02 Trang.

Tổngquanđềthi
Tênbài
File chươngtrình
File dữkiệu
File kếtquả
Thờigian
Điểm

Bài 1
MERGENUM.*
MERGENUM.INP
MERGENUM.OUT
1s/test
3

Bài 2
TIMSO.*
TIMSO.INP
TIMSO.OUT
1s/test
3

Bài 3
MAXPATH.*
MAXPATH.INP
MAXPATH.OUT
1s/test
4

Lưu ý: Thísinhthaydấu * trong File chươngtrìnhbằng pas hoặccpptùytheongônngữlậptrìnhmàthísinhsửdụngtươngứnglà Pascal hoặc C/C++
Lậptrìnhgiảicácbàitoánsau:
Bài 1: Ghépsố
Cho 2 sốnguyêndươngx,y ta xâydựngsố z bằngcáchghépcácchữsốcủa x và y saochothứtựcácchữsốcủa x và y vẫngiữnguyêntrên z. Tìmgiátrịbénhấtvàlớnnhấtcủa z.
Dữliệuvào:Lấytừ file MERGENUM.INP
Mộtdònggồm 2 sốnguyêndương x và y
Dữliệura:Ghivào file MERGENUM.OUT
Dòngthứnhấtghigiátrịbénhấtcủa z vàdòngthứ 2 ghigiátrịlớnnhấtcủa z
Giớihạn:1<=x,y<=108dữliệuđảmbảokhôngcócácchữsố 0 vônghĩacủa x và y.
Vídụ:
MERGENUM.INP
MERGENUM.OUT

13 26
1236
2613

Bài 2: Tìmsố
Cho sốnguyêndương X, khiđảongượctrậttựcácchữsốcủa X ta sẽthuđượcmộtsốnguyêndương Y, Y đượcgọilàsốđảongượccủa X.
Vídụ: X=613 thì Y=316 làsốđảongượccủa X.
Sốnguyêndương Y đượcgọilàsốnguyêntốnếunóchỉcóhaiướcsốlà 1 vàchínhnó, số 1 khôngphảilàsốnguyêntố.
Cho 2 sốnguyêndương P và Q (1<=P<=Q<=2.109; Q-P<=105).
Yêucầu:Hãyđếmcácsốnguyêndương X thỏamãn P<=X<=Q vàsốđảongượccủasố X làsốnguyêntố.
Dữliệuvào: Cho trong File vănbảnTIMSO.INPcócấutrúcnhưsau:
Gồm 1 dòngghi 2 sốnguyêndương P và Q cáchnhauítnhất 1 dấucách
Dữliệura:Ghira file vănbảnTIMSO.OUTghisốlượngsốtìmđược
Vídụ:
TIMSO.INP
TIMSO.OUT

10 19
11
13
14
16
17

Bài 3: Đườngđicựcđại
Tạimộtxứsởnọ, nhàvua ban hànhmộtluậtrấtkìlạ. Đểthabổngtùnhân, nhàvuaralệnhchodựngmộttúilướiAcókíchthướcMxN, trênmỗitúilướighimộtsốnguyên. Mộtngườixuấtpháttạitúilướinàođócủacột 1, cần sang cột N (tại ô nàocũngđược). Quytắcđưaralà: Từnút A[i,j] chỉđượcquyền sang mộttrongbanút A[i,j+1], A[i-1,j], A[i+1,j+1]. Trongđó, chỉsốđầulàhàng, chỉsốsaulàcột. Nếuaiđi qua hếtlướiA (đếncộtcuốicùng) đãchomàtổngcủacácsốđãđi qua lớnnhấtthìnhàvuasẽthabổng.
Do tính ham chơi, mộtlầnBờmđãbịlạcvàoxứsởtrênvàbịbắtlàmtùnhân.
Yêucầu:HãytìmmộtđườngđithỏamãnquytắctrêncủanhàvuađểgiúpBờmđượcthabổng, trongđó 1<=N, M<=100; -1000Dữliệuvào:Từ file vănbảnMAXPATH.INP, gồm:
- Dòng 1: Chứa 2 sốnguyên M, N
- Dòngitrong M dòngtiếptheo, mỗidòngchứa N sốnguyên.
Dữliệura:Ghira file vănbảnMAXPATH.OUT, gồm:
- Dòng 1: Ghithứtựcácbướcđitừcột 1 đếncột N trongđómỗi con sốthểhiệnhàngcầnđặtchântrênmỗicột.
- Dòng 2: Ghitổngcácsốđi qua
Vídụ:
MAXPATH.INP
MAXPATH.OUT

4 5
1 2 6 7 9
7 6 5 6 7
1 2 3 4 2
4 7 8 7 6
2 2 1 1 1
35

-------------------------------------------Hết----------------------------------------
Cánbộcoithikhônggiảithíchgìthem


SỞ GD&ĐT VĨNH PHÚC
TRƯỜNG THPT YÊN LẠC 2

KÌ THI KSCL ĐỘI TUYỂN HỌC SINH GIỎI KHỐI 11
ĐÁP ÁN MÔN TIN HỌC
NĂM HỌC 2017 - 2018

Test chấm
Bài
Test
Input
Output
Điểm






Bài 1. Ghépsố
1
13 25
1235
2513
0.25


2
13 256
13256
25613
0.25


3
1388 256
1235688
2561388
0.25


4
1388 674
1367488
6741388
0.25


5
1388 67417
136741788
674171388
0.25


6
1388 674176
1367417688
6741761388
0.25


7
13881 674176
13674176881
67417613881
0.25


8
138581 674176
136741768581
674176138581
0.25


9
1385581 6274176
13627417685581
62741761385581
0.5


10
13855481 62374176
1362374176855481
6237417613855481
0.5






Bài 2. Tìmsố
1
10 25
6
0.25


2
10 100
25
0.25


3
10 1000
193
0.25


4
10 10000
1422
0.25


5
10 100000
11014
0.25


6
100 10000
1397
0.25


7
100 100000
10989
0.25


8
100 1000000
89487
0.25


9
1000 100000
10821
0.5


10
10000 1000000
88090
0.5





Bài 3.
Đườngđicựcđại


1
4 5
1 2 6 7 9
7 6 5 6