S GIÁO D C VÀ ĐÀO T OỞ Ụ Ạ
QU NG NAMẢK THI OLYMPIC 24/3 T NH QU NG NAMỲ Ỉ Ả
NĂM 2021
Môn thi : TIN H C L P 10Ọ Ớ
Th i gian:ờ150 phút (không k th i gian giaoể ờ
đ)ề
(Đ thi có 03 trang)ề
T NG QUAN Đ THIỔ Ề T NG QUAN Đ BÀIỔ Ề
Bài Tên bàiFile ch ngươ
trình File d li u vàoữ ệ File k t quế ả Th iờ
gian
1Chia h tế
cho 3
CHIAHET3.* CHIAHET3.INP CHIAHET3.OUT 1 s
2S nguyênố
t đc bi tố ặ ệ
SPECPRIME.* SPECPRIME.INP SPECPRIME.OUT 1 s
3Nén xâu NENXAU.* NENXAU.INP NENXAU.OUT 1 s
4S t nhiên ố ự
nh nh tỏ ấ SOMIN.* SOMIN.INP SOMIN.OUT 1 s
D u * đc thay th b i PAS ho c CPP c a ngôn ng l p trình đc s d ng t ngấ ượ ế ở ặ ủ ữ ậ ượ ử ụ ươ
ng là Pascal ho c C++.ứ ặ
Hãy l p trình gi i các bài toán sau:ậ ả
Bài 1. Chia h t cho 3 (5 đi m) ế ể
Cho m t s t nhiên ộ ố ự N (N<1032).
Yêu c u:ầ Hãy cho bi t N có chia h t cho 3 không? ế ế
N u N chia h t cho 3 thì ghi ra “YES”, ng c l i n u N không chia h t cho 3 thì ghi raế ế ượ ạ ế ế
“NO”.
D li u vào:ữ ệ T t p văn b n ừ ệ ả CHIAHET3.INP g m m t s ồ ộ ố N;
K t qu :ế ả Ghi ra t p văn b nệ ả CHIAHET3.OUT ch “YES” ho c “NO”.ữ ặ
Ví d :ụ
CHIAHET3.INP CHIAHET3.OUT
123 YES
1234 NO
Ràng bu c:ộ
Có 60% test ng 60% s đi m c a bài v i N ứ ố ể ủ ớ ≤ 106;
Có 20% test ng 20% s đi m c a bài v i N ứ ố ể ủ ớ ≤ 1018;
Có 20% test khác ng v i 20% s đi m còn l i c a bài v i N ứ ớ ố ể ạ ủ ớ < 1032.
Bài 2. S nguyên t đc bi t ố ố ặ ệ (5 đi m) ể
Nam r t yêu thích s nguyên t vì v y c u ta th ng s u t m các s nguyên t . L nấ ố ố ậ ậ ườ ư ầ ố ố ầ
này b s u t p c a Nam là nh ng s nguyên t đc bi t, t c là nh ng s nguyên t đó cóộ ư ậ ủ ữ ố ố ặ ệ ứ ữ ố ố
t ng các ch s c a nó l i là s nguyên t . ổ ữ ố ủ ạ ố ố
Yêu c u:ầ Hãy li t kê ra t t c các s nguyên t đc bi t nh h n ho c b ng N theo th tệ ấ ả ố ố ặ ệ ỏ ơ ặ ằ ứ ự
tăng d n.ầ
D li u vào:ữ ệ T t p văn b n ừ ệ ả SPECPRIME.INP g m 1 dòng ch a s N;ồ ứ ố
K t qu :ế ả Ghi ra t p văn b nệ ả SPECPRIME.OUT các s nguyên t đc bi t nh h n ho cố ố ặ ệ ỏ ơ ặ
b ng N theo th t tăng d n.ằ ứ ự ầ
Ví d :ụ
SPECPRIME.INP SPECPRIME.OUT
20 2 3 5 7 11
Ràng bu c:ộ
Có 60% test ng 60% s đi m c a bài v i N ứ ố ể ủ ớ ≤ 106;
Có 40% test ng 40% s đi m c a bài v i N ứ ố ể ủ ớ ≤ 109;
Bài 3. Nén xâu (5 đi m) ể
Trong máy tính, đ ti t ki m b nh ng i ta th ng tìm cách nén d li u. M t xâuể ế ệ ộ ớ ườ ườ ữ ệ ộ
ký t có th nén l i thành m t xâu m i b ng cách nén các ký t gi ng nhau đng c nhự ể ạ ộ ớ ằ ự ố ứ ạ
nhau.
Ví d : Xâu aaaa s nén thành 4a. ụ ẽ
Yêu c uầ: Hãy l p trình đ nén m t xâu ký t th ng theo cách trên.ậ ể ộ ự ườ
D li u vào: ữ ệ T t p văn b n ừ ệ ả NENXAU.INP, g m m t xâu các ký t là ch cái in th ng. ồ ộ ự ữ ườ
K t qu : ế ả Ghi ra t p văn b n ệ ả NENXAU.OUT, g m m t xâu ký t sau khi nén.ồ ộ ự
Ví d :ụ
NENXAU.INP NENXAU.OUT
mmaabbbeeeezh 2m2a3b4ezh
Ràng bu c:ộ
Có 50% test ng 50% s đi m c a bài có đ dài xâu ứ ố ể ủ ộ ≤ 255;
Có 20% test ng 20% s đi m c a bài có đ dài xâu ứ ố ể ủ ộ ≤ 103;
Có 30% test ng 30% s đi m c a bài có đ dài xâu ứ ố ể ủ ộ ≤ 105;
Bài 4. S t nhiên nh nh t (5 đi m) ố ự ỏ ấ ể
Mai và Lan là đôi b n thân, Mai đang tìm cách gi i m t bài toán liên quan t i s tạ ả ộ ớ ố ự
nhiên. Lúc này, Mai đang r t c n s giúp đ c a ấ ầ ự ỡ ủ Lan. Th thách l n này là m tử ầ ộ dãy g mồ
N s t nhiên b t k n m trong đo n t 0 t i 10ố ự ấ ỳ ằ ạ ừ ớ 6. Hãy vi t ch ng trình tìm s t nhiênế ươ ố ự
nh nh t không có trong dãy s đó. Vì s l ng các s t nhiên trong dãy s đã cho có thỏ ấ ố ố ượ ố ự ố ể
r t l n nên vi c tìm th công là không th . Chính vì v y, Mai c n m t thu t toán đ cài đtấ ớ ệ ủ ể ậ ầ ộ ậ ể ặ
vào máy tính và nh máy tính tìm giúp.ờ
Các em hãy giúp đ hai b n gi i quy t bài toán nhé.ỡ ạ ả ế
Yêu c u:ầ Cho m t dãy A g m N s t nhiên. Hãy tìm s t nhiên nh nh t không xu tộ ồ ố ự ố ự ỏ ấ ấ
hi n trong dãy đó.ệ
D li u vào :ữ ệ T t p văn b n SOMIN.INP g m m t dãy N s t nhiên;ừ ệ ả ồ ộ ố ự
D li u ra :ữ ệ Ghi ra t p văn b nệ ả SOMIN.OUT g m duy nh t 1 s th a mãn yêu c u.ồ ấ ố ỏ ầ
Ví d :ụ
SOMIN.INP SOMIN.OUT
5 4 3 6 1 2 0
2 4 0 3 1 2 6 2 8 5 7
Ràng bu c:ộ
Có 80% test ng 80% s đi m c a bài v i N ứ ố ể ủ ớ ≤ 104, 0 ≤ ai ≤ 106;
Có 20% test ng v i 20% s đi m c a bài v i N ứ ớ ố ể ủ ớ ≤ 106, 0 ≤ ai ≤ 109 .
–––––––––––– H t ––––––––––––ế
H và tên thí sinh: …..…………………………………. S báo danh: ………………ọ ố
S GIÁO D C ĐÀO T OỞ Ụ Ạ
QU NG NAMẢK THI OLYMPIC QU NG NAM NĂM 2021Ỳ Ả
ĐÁP ÁN VÀ H NG D N CH M MÔN TIN HOC 10ƯỚ Ẫ Ấ
Bài 1: (5 đi mể) M i TEST đúng cho 0,25 đi m. Thỗ ể i gian ch y 1s/ 1testờ ạ .
TEST CHIAHET3.INP CHIAHET3.OUT
11111 NO
21234 NO
3546 YES
4 207306 YES
… CHIAHET3.INP CHIAHET3.OUT
20 CHIAHET3.INP CHIAHET3.OUT
Bài 2: (5 đi mể) M i TEST đúng cho 0,25 đi m. Thỗ ể i gian ch y 1s/ 1testờ ạ .
TEST
SPECPRIME.INP SPECPRIME.OUT
120 2 3 5 7 11
250 2 3 5 7 11 23 29 41 43 47
3100 2 3 5 7 11 23 29 41 43 47 61 67 83 89
…
SPECPRIME.INP SPECPRIME.OUT
20
SPECPRIME.INP SPECPRIME.OUT
Bài 3: (5 đi mể) M i TEST đúng cho 0,5 đi m. Thỗ ể i gian ch y 1s/ 1testờ ạ .
TEST NENXAU.INP NENXAU.OUT
1fyyqagcodnbsyjiuadft f2yqagcodnbsy
jiuadft
2nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
nnbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb 48n43b
3 NENXAU.INP NENXAU.OUT
… NENXAU.INP NENXAU.OUT
20 NENXAU.INP NENXAU.OUT
Bài 4: (5 đi mể) M i TEST đúng cho 0,25 đi m. Thỗ ể i gian ch y 1s/ 1testờ ạ .