S GIÁO D C VÀ ĐÀO T OỞ Ụ Ạ
QU NG NAMẢ
K THI H C SINH GI I L P 9 C P T NHỲ Ọ Ỏ Ớ Ấ Ỉ
NĂM H C 2019-2020Ọ
(Đ thi g m 04 trang)ề ồ
Môn thi : TIN H CỌ
Th i gianờ : 150 phút (không k th i gian giao để ờ ề)
Ngày thi : 10/6/2020
T ng quan v đ thiổ ề ề
Tên bài Tên file
ch ng trìnhươ D li u vàoữ ệ D li u raữ ệ
Bài 1 : Tr c nh tự ậ TN.* TN.INP TN.OUT
Bài 2 : Di n tích hình ch ệ ữ
nh tậHCN.* HCN.INP HCN.OUT
Bài 3 : Xin chào XINCHAO.* XINCHAO.INP XINCHAO.OUT
Bài 4 : Mua quà l u ni mư ệ MUAQUA.* MUAQUA.INP MUAQUA.OUT
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à Free Pascal ho c C++. ụ ươ ứ ặ
Bài 1. Tr c nh t (5 đi m) ự ậ ể
An và Bình là đôi b n thân h c chung l p. Trong l p h c thì t t c các b n đuạ ọ ớ ớ ọ ấ ả ạ ề
ph i tr c nh t và c sau m t s x ngày nh t đnh thì b n đó m i ph i tr c nh t l i.ả ự ậ ứ ộ ố ấ ị ạ ớ ả ự ậ ạ
Bi t r ng, ban đu An và Bình đu tr c nh t ngày đu tiên, và 2 b n mu n bi t sauế ằ ầ ề ự ậ ầ ạ ố ế
bao nhiêu ngày thì 2 b n l i tr c nh t chung v i nhau và khi đó m i b n đã tr c nh tạ ạ ự ậ ớ ỗ ạ ự ậ
bao nhiêu l n.ầ
Yêu c u:ầ Em hãy l p trình đ tr l i câu h i c a An và Bình nhé.ậ ể ả ờ ỏ ủ
D li u vào:ữ ệ đc t file ọ ừ TN.INP g m:ồ
- 1 dòng ch a 2 s nguyên xứ ố 1, x2 (2 ≤ x1, x2 ≤ 109) l n l t là s ngày mà sau đóầ ượ ố
An và Bình m i ớph i tr c nh t l i;ả ự ậ ạ
D li u ra:ữ ệ ghi ra file TN.OUT g m:ồ
- Dòng đu tiên ghi ra s ngày An và Bình cùng nhau tr c nh t l i;ầ ố ự ậ ạ
- Dòng th 2 ch a 2 s l n l t là s l n m t b n đã tr c nh t cho t i lúc 2ứ ứ ố ầ ượ ố ầ ộ ạ ự ậ ớ
b n cùng tr c nh t. ạ ự ậ
Ví d : ụ
TN.INP TN.OUT
6 4 12
2 3
Bài 2. Di n tích hình ch nh tệ ữ ậ (5 đi m) ể
Là m t h c sinh thông minh, nên An luôn tìm đc nh ng cách gi i hay cho nh ngộ ọ ượ ữ ả ữ
bài toán l . Và b n y v a gi i quy t xong bài toán tìm di n tích chung c a 2 hình chạ ạ ấ ừ ả ế ệ ủ ữ
nh t, tuy nhiên, An l i g p khó khăn v i vi c s d ng ngôn ng l p trình đ gi iậ ạ ặ ớ ệ ử ụ ữ ậ ể ả
quy t bài toán này. C th bài toán nh sau: Cho 2 hình ch nh t trên m t ph ng 2Dế ụ ể ư ữ ậ ặ ẳ
v i t a đ đnh trái d i và đnh ph i trên, tìm di n tích ph n chung c a 2 hình chớ ọ ộ ỉ ướ ỉ ả ệ ầ ủ ữ
nh t này?ậ
Yêu c u:ầ Em hãy l p trình đ giúp b n An gi i quy t bài toán này nhéậ ể ạ ả ế .
D li u vào:ữ ệ đc t file ọ ừ HCN.INP g m:ồ
- Dòng 1 ghi 4 s nguyên xố1, y1, x2, y2 t ng ng là t a đ đnh trái d i và đnhươ ứ ọ ộ ỉ ướ ỉ
ph i trên c a hình ch nh t th nh t;ả ủ ữ ậ ứ ấ
- Dòng 2 ghi 4 s nguyên uố1, v1, u2, v2 t ng ng là t a đ đnh trái d i và đnhươ ứ ọ ộ ỉ ướ ỉ
ph i trên c a hình ch nh t th hai;ả ủ ữ ậ ứ
Trong đó: x1 < x2, y1 < y2, u1 < u2, v1 < v2 và (-109 < x1, y1, x2, y2 , u1, v1, u2, v2 <
109 ).
D li u ra:ữ ệ ghi ra file HCN.OUT s nguyên duy nh t là di n tích ph n chung c aố ấ ệ ầ ủ
2 hình ch nh t.ữ ậ
Ví d : ụ
HCN.INP HCN.OUT
1 1 3 3
2 0 4 4
2
Bài 3. Xin chào (5 đi m) ể
An là ng i thích chat v i b n bè trên Internet. C u y đã l p ra m t phòng chatườ ớ ạ ậ ấ ậ ộ
v i đi u ki n r ng tr c khi vào phòng chat, m i ng i ph i chào h i nhau tr c.ớ ề ệ ằ ướ ọ ườ ả ỏ ướ
M t câu chào đc đnh nghĩa r ng, câu chào đó ph i là m t xâu kí t , ch g m cácộ ượ ị ằ ả ộ ự ỉ ồ
ch cái, không ch a kí t tr ng, sao cho khi xóa đi m t s ch cái, nó s tr thành m tữ ứ ự ắ ộ ố ữ ẽ ở ộ
xâu t khóa Key cho tr c, t t nhiên là s không đc phép tráo đi v trí các ch cái,ừ ướ ấ ẽ ượ ổ ị ữ
mà ch đc xóa b t m t s ch cái.ỉ ượ ớ ộ ố ữ
Ví d : V i t khóa key là “xinchao”; khi Bình mu n vào phòng chat, Bình gõụ ớ ừ ố
"choxiancaihao" thì h th ng s xem xét xâu này và s t đng lo i b các ch cái đệ ố ẽ ẽ ự ộ ạ ỏ ữ ể
tr thành t "xinchao". Nh v y Bình đc vào phòng chat.ở ừ ư ậ ượ
Nh ng khi Bình gõ "choxian", h th ng không th làm cách nào xóa b t ch cái đ trư ệ ố ể ớ ữ ể ở
thành t " xinchao" đc. Nh v y, Bình không đc vào phòng chat.ừ ượ ư ậ ượ
Yêu c uầ: Cho t khóa Key và N câu chào, em hãy xác đnh xem câu chào nào đcừ ị ượ
ch p nh n?ấ ậ
D li u vào:ữ ệ Đc t fileọ ừ XINCHAO.INP g m:ồ
- Dòng th nh t ch a s nguyên d ng N (N ≤ 100)ứ ấ ứ ố ươ
- Dòng th hai ch a t khóa Key (có đ dài ≤ 10ứ ứ ừ ộ 4)
- N dòng ti p theo, m i dòng ch a xâu ch cái mà Bình đnh gõ (có đ dài ≤ế ỗ ứ ữ ị ộ
106).
D li u ra:ữ ệ Ghi ra file XINCHAO.OUT g m:ồ
N dòng, m i dòng t ng ng v i câu chào, câu chào đc đng ý thì xu t "YES",ỗ ươ ứ ớ ượ ồ ấ
n u không đng ý thì xu t "NO" (vi t hoa và không ch a d u ngo c kép).ế ồ ấ ế ứ ấ ặ
Ví d :ụ
XINCHAO.INP XINCHAO.OUT
4
hello
ahhellllloou
hlelo
helhcludoo
HelhcLudoo
YES
NO
YES
NO
Ràng bu c:ộ
Có 60% s test ng v i ố ứ ớ 60% s đi m có ố ể xâu ch cái ữ≤ 104;
Có 40% s test còn l i ng v i ố ạ ứ ớ 40% s đi m có có ố ể xâu ch cái (10ữ4, 106].
Bài 4: Mua quà l u ni m ư ệ (5 đi m)ể
An là m t h c sinh tham d cu c thi H c sinh gi i l p 9. Sau khi thi xong, An cùngộ ọ ự ộ ọ ỏ ớ
các b n đc nhà tr ng đa đi tham quan nhi u danh lam th ng c nh và c a hàngạ ượ ườ ư ề ắ ả ử
l u ni m t i thành ph Tam K . An mu n mua quà l u ni m t ng các b n thân nhà.ư ệ ạ ố ỳ ố ư ệ ặ ạ ở
Khi đn m t c a hàng l u ni m trung tâm thành ph , An đc ch c a hàng gi iế ộ ử ư ệ ở ố ượ ủ ử ớ
thi u giá c a n (3≤ n ≤ 10ệ ủ 5) món quà, món quà th i (1 ≤ i ≤ n) có giá ti n là aứ ề i ( 1≤
ai ≤104). An mu n ch n mua m (1 ≤ m ≤ n) món quà sao cho chênh l ch giá ti n gi aố ọ ệ ề ữ
món quà có giá tr l n nh t và nh nh t là ít nh t có th .ị ớ ấ ỏ ấ ấ ể
Yêu c u:ầ Em hãy l p trình giúp An mua các món quà t ng th a mãn yêu c u.ậ ặ ỏ ầ
D li u vàoữ ệ : Đc t fileọ ừ MUAQUA.INP, g m 02 dòng:ồ
- Dòng 1: ghi hai s nguyên m và n, cách nhau b i d u cách;ố ở ấ
- Dòng 2: ghi n s nguyên aố1, a2,… ,an và đt cách nhau b i d u cách.ặ ở ấ
D li u raữ ệ : Ghi ra file MUAQUA.OUT, g m 01 dòng ghi duy nh t s k là đồ ấ ố ộ
chênh l nh giá tr nh nh t c n tìm.ệ ị ỏ ấ ầ
Ví d :ụ
MUAQUA.INP MUAQUA.OUT Gi i thíchả
4 6
10 12 10 5 7 22 5An có th mua các món quà có giá tr :ể ị
10, 12, 10, 7.
Ràng bu c:ộ
Có 50% s test ng v i ố ứ ớ 50% s đi m có 0<Nố ể , M ≤ 105; ai ≤ 103;
Có 30% s test ng v i ố ứ ớ 30% s đi m có 0<Nố ể , M ≤ 105; 103 < ai ≤ 104.
.
------------------H t----------------ế
Thí sinh không đc s d ng tài li u.ượ ử ụ ệ
Cán b coi thi không gi i thích gì thêộ ả m.
S GIÁO D C VÀ ĐÀO T OỞ Ụ Ạ
QU NG NAMẢK THI CH N H C SINH GI I L P 9Ỳ Ọ Ọ Ỏ Ớ
NĂM H C 2019-2020Ọ
Môn thi : TIN H C 9Ọ
H NG D N CH M MÔN TIN H CƯỚ Ẫ Ấ Ọ
Bài thi ch m b ng test, ấ ằ và ch m b ng ph n m m Themis kèm theo (m iấ ằ ầ ề ớ
nh t c a th y Lê Minh hoàng và Đ Đc Đông)ấ ủ ầ ỗ ứ
Bài 1 (5.0 đi m) g m có 10 test, m i test 0,5 đi m, th i gian 1s, b nh 1024ể ồ ỗ ể ờ ộ ớ
MB
30% s test ng v i 30% s đi m c a bài có xố ứ ớ ố ể ủ 1, x2 ≤ 100
30% s test ng v i 30% s đi m c a bài có 1ố ứ ớ ố ể ủ 03 ≤ x1, x2 ≤ 106
40% s test ng v i 40% s đi m c a bài có 1ố ứ ớ ố ể ủ 06 < x1, x2 ≤ 109
Bài2 (5.0 đi m) g m có 10 test, m i test 0.5 đi m, th i gian 1s, b nh 1024 ể ồ ỗ ể ờ ộ ớ
MB
70% s test ng v i 70% s đi m c a bài có -10ố ứ ớ ố ể ủ 9 < x1, y1, x2, y2 , u1,
v1, u2, v2 < 106.
30% s test còn l i ng v i 30% s đi m c a bài có 10ố ạ ứ ớ ố ể ủ 6 x1, y1, x2,
y2 , u1, v1, u2, v2 < 109.
Bài 3 (5.0 đi m) g m có 10 test, m i test 0.5 đi m, th i gian 1s, b nh 1024 ể ồ ỗ ể ờ ộ ớ
MB
60% s test ng v i 60% s đi m có xâu ch cái ≤ 10ố ứ ớ ố ể ữ 4;
40% s test còn l i ng v i 40% s đi m có có xâu ch cái (10ố ạ ứ ớ ố ể ữ 4, 106].
Bài 4 (5.0 đi m) g m có 10 test, m i test 0.5 đi m, th i gian 1s, b nh 1024 ể ồ ỗ ể ờ ộ ớ
MB
60% s test ng v i 60% s đi m có 0<N, M ≤ 10ố ứ ớ ố ể 5; ai ≤ 103;
40% s test ng v i 40% s đi m có 0<N, M ≤ 10ố ứ ớ ố ể 5; 103 < ai ≤ 104.