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 2020 - 2021Ọ
(Đ 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/4/2021
T ng quan v đ thiổ ề ề
Tên bàiTên file
ch ngươ
trình D li u vàoữ ệ D li u raữ ệ Th iờ
gian
Bài 1: Chia quàCHIAQUA.* CHIAQUA.INP CHIAQUA.OUT 1s
Bài 2: Mã s nhân viênốCODE.* CODE.INP CODE.OUT 1s
Bài 3: Xâu đi x ngố ứ XAUDX.* XAUDX.INP XAUDX.OUT 1s
Bài 4: c sên ăn rauỐOCSEN.* OCSEN.INP OCSEN.OUT 1s
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: (5 đi mể) Chia quà
Nhân d p đi siêu th cùng m , H ng đã mua M qu táo v làm quà cho hai ng i b nị ị ẹ ằ ả ề ườ ạ
thân là Nga và Trang. M i qu táo có tr ng l ng là 100g ho c 200g. H ng mu n chiaỗ ả ọ ượ ặ ằ ố
đu M qu táo trên thành hai ph n có tr ng l ng b ng nhau đ chia cho hai b n vì khiề ả ầ ọ ượ ằ ể ạ
mua H ng quên ki m tra đi u này. ằ ể ề
Yêu c u:ầ Theo em, H ng có th chia M qu táo trên thành hai ph n có tr ng l ng b ngằ ể ả ầ ọ ượ ằ
nhau đc không?ượ
D li u vào:ữ ệ T t p văn b n ừ ệ ả CHIAQUA.INP g m:ồ
- Dòng th nh t là s nguyên M (1 ≤ M ≤ ứ ấ ố 106);
- Dòng th hai g m M s nguyên aứ ồ ố 1, a2, …, aM là tr ng l ng c a các qu táo màọ ượ ủ ả
H ng đã mua và m i s nguyên aằ ỗ ố i cách nhau m t kho ng tr ng (ộ ả ắ d li u vào đm b o chữ ệ ả ả ỉ
có hai tr ng h p aườ ợ i = 100 ho c aặi = 200).
D li u ra:ữ ệ Ghi ra t p văn b n ệ ả CHIAQUA.OUT
N u H ng có th chia đc thì thông báo là ế ằ ể ượ YES, còn n u không chia đc thì thôngế ượ
báo là NO.
Ví d :ụ
CHIAQUA.INP CHIAQUA.OUT
3100 200 100 YES
CHIAQUA.INP CHIAQUA.OUT
4
100 100 100 200
NO
Bài 2: (5 đi mể) Mã s nhân viênố
T ng Giám đc công ty Hoa H ng n i ti ng là ng i r t c n tr ng. Ông ta th cổ ố ồ ổ ế ườ ấ ẩ ọ ự
hi n vi c qu n lí nhân viên b ng cách gán cho m i nhân viên m t mã s . Công ty có Nệ ệ ả ằ ỗ ộ ố
nhân viên thì m i nhân viên i (i = 1, 2, …, N) đu có m t mã s hoàn toàn khác nhau. Doỗ ề ộ ố
b n đi công tác m t th i gian dài nên ông ta giao l i quy n qu n lí cho tr lý c a ông. Khiậ ộ ờ ạ ề ả ợ ủ
ông tr v , công ty đã có s thay đi s l ng nhân viên. Vì v y, khi ti p nh n thêm nhânở ề ự ổ ố ượ ậ ế ậ
viên m i, ông ta mu n bi t mã s l n nh t đ gán cho nhân viên m i. ớ ố ế ố ớ ấ ể ớ
Yêu c u:ầ Hãy tìm mã s l n nh t ch a xu t hi n trong N mã s đã cho.ố ớ ấ ư ấ ệ ố
D li u vào:ữ ệ T t p văn b n ừ ệ ả CODE.INP g m:ồ
- Dòng th nh t ghi s nguyên d ng N là s l ng nhân viên ứ ấ ố ươ ố ượ (1 < N ≤ 106);
- N dòng ti p theo, dòng th i ghi s aế ứ ố i (i = 1, 2, ..., N; |ai| ≤ 109).
D li u ra:ữ ệ Ghi ra t p văn b n ệ ả CODE.OUT g m m t s duy nh t là mã s tìm đc.ồ ộ ố ấ ố ượ
Ví d :ụ
CODE.INP CODE.OUT
6
7
4
2
5
6
1
3
Ràng bu c:ộ
Sub1: Có 50% test t ng ng 50% s đi m c a bài v i N ươ ứ ố ể ủ ớ ≤ 100 và |ai| ≤ 103;
Sub2: Có 30% test t ng ng 30% s đi m c a bài v i N ươ ứ ố ể ủ ớ ≤ 1000 và |ai| ≤ 106;
Sub3: Có 20% test t ng ng 20% s đi m còn l i c a bài v iươ ứ ố ể ạ ủ ớ N ≤ 106 và |ai| ≤ 109.
Bài 3: (5 đi mể) Xâu đi x ng ố ứ
Cho m t xâu ST (đ dài không quá 2x10ộ ộ 3 kí t ) ch a ít nh t m t ch cái in hoaự ứ ấ ộ ữ (‘A’…
‘Z’) ho c m t ch cái th ng (‘a’… ‘z’) ho c ch s (‘0’...‘9’). ặ ộ ữ ườ ặ ữ ố
Yêu c u:ầ Hãy tìm đ dài c a xâu con đi x ng dài nh t.ộ ủ ố ứ ấ
M t xâu đc g i là đi x ng n u nó không có ít h n m t kí t và n u đc t tráiộ ượ ọ ố ứ ế ơ ộ ự ế ọ ừ
sang ph i hay t ph i sang trái đu gi ng nhau.ả ừ ả ề ố
Ví dụ: ‘B’; ‘TOT’; ‘BAILIAB’ là các xâu đi x ng.ố ứ
‘HOCBAI’ là xâu không đi x ng.ố ứ
D li u vào:ữ ệ T t p văn b n ừ ệ ả XAUDX.INP g m m t xâu ST.ồ ộ
D li u ra:ữ ệ Ghi ra t p văn b n ệ ả XAUDX.OUT g m m t s duy nh t là đ dài c a xâuồ ộ ố ấ ộ ủ
con đi x ng dài nh t.ố ứ ấ
Ví d :ụ
XAUDX.INP XAUDX.OUT
ABFGHIKLMLKIHGH 11
Ràng bu c:ộ V i N là đ dài c a xâu STớ ộ ủ
Sub1: Có 60% test t ng ng 60% s đi m c a bài v i N < 255;ươ ứ ố ể ủ ớ
Sub2: Có 40% test khác t ng ng 40% s đi m còn l i c a bài v i N ≤ 2x10ươ ứ ố ể ạ ủ ớ 3.
Bài 4: (5 đi mể) c sên ăn rauỐ
M t khu v n hình ộ ườ ch nh tữ ậ có kích th c NxM (ướ N dòng, M c tộ). Ta đánh s cácố
dòng t 1 đn N theo chi u t trên xu ng d i và các c t t 1 đn M theo chi u t tráiừ ế ề ừ ố ướ ộ ừ ế ề ừ
sang ph i đ chia khu v n thành các ô. Trong các ô đó, ngoài nh ng ô là đt đ ng iả ể ườ ữ ấ ể ườ
nông dân tr ng rau v n có nh ng ô là đá không th tr ng rau đc. M t chú c sên xu tồ ẫ ữ ể ồ ượ ộ ố ấ
phát t i ô (x, y) (ạx là v trí dòng, y là v trí c tị ị ộ ). N u ô xu t phát là đt, chú c sên có thế ấ ấ ố ể
di chuy n sang 4 ô k c nh v i ô đó (ể ề ạ ớ bên trái, bên ph i, bên trên, bên d iả ướ ) và đngươ
nhiên không th di chuy n vào ô đá đc. Tr ng h p ô xu t phát là đá thì chú c sênể ể ượ ườ ợ ấ ố
không th di chuy n đn ô nào khác.ể ể ế
Yêu c u:ầ Hãy tính xem chú c sên có th di chuy n đn nhi u nh t là bao nhiêu ô đ ănố ể ể ế ề ấ ể
rau?
D li u vào:ữ ệ T t p văn b n ừ ệ ả OCSEN.INP g m:ồ
- Dòng th nh t g m 4 s nguyên N, M, X, Y (ứ ấ ồ ố m i s cách nhau m t kho ng tr ngỗ ố ộ ả ắ )
(1 ≤ X ≤ N ≤ 2000, 1 ≤ Y ≤ M ≤ 2000);
- Trong N dòng ti p theo, m i dòng g m M s nguyên 0 ho c 1 (ế ỗ ồ ố ặ m i s cách nhauỗ ố
m t kho ng tr ngộ ả ắ ). S 0 nghĩa là ô tr ng rau, s 1 nghĩa là ô đá.ố ồ ố
D li u ra:ữ ệ Ghi ra t p văn b n ệ ả OCSEN.OUT g m m t s nguyên là s l ng ô l nồ ộ ố ố ượ ớ
nh t mà chú c sên có th di chuy n đn đ ăn rau. N u chú c sên không ăn đc ô rauấ ố ể ể ế ể ế ố ượ
nào thì ghi k t qu là -1.ế ả
Ví d :ụ
OCSEN.INP OCSEN.OUT
4 5 2 4
0 0 1 0 0
0 1 0 0 1
1 0 0 0 0
0 1 0 0 1
10
Ràng bu c:ộ
Sub1: Có 50% test t ng ng 50% s đi m c a bài v i N, M < 10;ươ ứ ố ể ủ ớ
Sub2: Có 30% test t ng ng 30% s đi m c a bài v i N, M ≤ 100;ươ ứ ố ể ủ ớ
Sub3: Có 20% test khác t ng ng 20% s đi m còn l i c a bài v i N, M ≤ 2ươ ứ ố ể ạ ủ ớ x103.
------------------H t-----------------ế
H và tên thí sinh:ọ ………………………………………. SBD: …………………..
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: 2020 - 2021Ọ
Môn thi : TIN H CỌ
H NG D N CH MƯỚ Ẫ Ấ
Bài thi ch m b ng test ấ ằ và ch m b ng ph n m m Themis kèm theo (ấ ằ ầ ề ph n m m 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ó 20 test, m i test 0.25 đi m, th i gian 1s, b nh 1024 MBể ồ ỗ ể ờ ộ ớ
80% s test t ng ng v i 80% s đi m c a bài v i M ≤ 10ố ươ ứ ớ ố ể ủ ớ 0;
20% s test t ng ng v i 20% s đi m còn l i c a bài v i M ≤ 1ố ươ ứ ớ ố ể ạ ủ ớ 06.
Bài 2. (5.0 đi m) g m có 20 test, m i test 0.25 đi m, th i gian 1s, b nh 1024 MBể ồ ỗ ể ờ ộ ớ
50% test t ng ng 50% s đi m c a bài v i N ≤ 100 và |aươ ứ ố ể ủ ớ i| ≤ 103;
30% test t ng ng 30% s đi m c a bài v i N ≤ 1000 và |aươ ứ ố ể ủ ớ i| ≤ 106;
20% test t ng ng 20% s đi m còn l i c a bài v i N ≤ 10ươ ứ ố ể ạ ủ ớ 6 và |ai| ≤ 109.
Bài 3. (5.0 đi m) g m có 20 test, m i test 0.25 đi m, th i gian 1s, b nh 1024 MBể ồ ỗ ể ờ ộ ớ
60% test t ng ng 60% s đi m c a bài v i N < 255;ươ ứ ố ể ủ ớ
40% test khác t ng ng 40% s đi m còn l i c a bài v i N ≤ 2x10ươ ứ ố ể ạ ủ ớ 3.
Bài 4. (5.0 đi m) g m có 30 test (ể ồ t test 1 đn 29, m i test 0.167 đi m; test 30: 0.157 ừ ế ỗ ể
đi mể), th i gian 1s, b nh 1024 MBờ ộ ớ
50% test t ng ng 50% s đi m c a bài v i N, M < 10;ươ ứ ố ể ủ ớ
30% test t ng ng 30% s đi m c a bài v i N, M ≤ 100;ươ ứ ố ể ủ ớ