- Trang chủ >>
- Đề thi >>
- Đề thi lớp 10
Bộ đề thi HSG quốc gia môn tin học các năm 2016 2020
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (38.56 MB, 93 trang )
SỞ GIÁO DỤC VÀ ĐÀO TẠO
THÀNH PHỐ HỒ CHÍ MINH
ĐỀ THI CHÍNH THỨC
(Đề thi có 02 trang)
KỲ THI HỌC SINH GIỎI LỚP 12 THPT
KHÓA NGÀY 07/3/2018
Môn thi: Tin học
Thời gian làm bài: 150 phút
(Không kể thời gian phát đề)
TỔNG QUAN BÀI THI
Tên bài
Bài 1 Trung bình cộng
Bài 2 Đổi quà
Bài 3 Ba lô kiểu mới
Tên chương trình
AVERAGE.*
CHANGE.*
NEWBACK.*
Tập tin dữ liệu
AVERAGE.INP
CHANGE.INP
NEWBACK.INP
Tập tin kết quả
AVERAGE.OUT
CHANGE.OUT
NEWBACK.OUT
Dấu * được thay thế bởi PAS hay 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 3 bài toán sau:
Bài 1: Trung bình cộng – AVERAGE.* (6 điểm)
Tý là một bạn học sinh rất thích Tin học. Nhân dịp Xuân về, lớp tổ chức trò chơi
“Ai làm toán nhanh”. Cách chơi như sau: có n gói kẹo được đánh số từ 1 đến n, gói thứ
i có ai chiếc kẹo; nhiệm vụ của người chơi là chọn một số gói kẹo liên tiếp trong n gói
kẹo đã cho sao cho trung bình cộng của số kẹo trong các gói được chọn là k cho trước;
người thắng cuộc là người chọn được nhiều gói kẹo nhất và toàn bộ số kẹo đó sẽ là
phần thưởng dành cho người đó.
Yêu cầu: Hãy lập trình giúp Tý là người thắng cuộc trong cuộc thi.
Dữ liệu vào: Từ tập tin văn bản AVERAGE.INP có cấu trúc như sau:
- Dòng đầu tiên chứa 2 số nguyên n và k; (1 ≤ n ≤ 105, 1 ≤ k ≤ 109)
- Dòng thứ 2 chứa n số nguyên a1, a2, . . ., an; (1 ≤ ai ≤ 109, i =1, 2, 3, …, n).
Kết quả: Ghi vào tập tin văn bản AVERAGE.OUT một số nguyên ghi độ dài
của dãy tìm được hoặc số 0 nếu không tồn tại cách chọn.
Ví dụ:
AVERAGE.INP
53
12346
AVERAGE.OUT
3
Bài 2: Đổi quà – CHANGE.* (7 điểm)
Tèo nhận được một số phiếu thưởng giá trị như nhau và phát hiện mình có thể
có nhiều cách đổi các món quà mình thích. Ví dụ trong hội chợ này, các món quà đang
đổi với 1 phiếu thưởng, 2 phiếu thưởng và 3 phiếu thưởng. Tèo có đúng 5 phiếu thưởng
để đổi. Anh ta có thể đổi 5 món quà với giá 1 phiếu thưởng hoặc 1 món quà với giá 3
phiếu thưởng và thêm 1 món quà ở mức 2 phiếu thưởng. Tất nhiên, có những kết hợp
khác cho tổng cộng 5 cách khác nhau Tèo có thể chi tiêu tất cả phiếu thưởng của mình
vào món quà.
Đề thi Học sinh giỏi Lớp 12 – môn Tin học
Trang 1/2
Sau đây là năm cách mà Tèo có thể đổi quà:
1.3 + 1.2
1.3 + 2.1
1.2 + 3.1
2.2 + 1.1
5.1
Yêu cầu: Viết một chương trình tính số cách Tèo có thể dùng N phiếu thưởng
đổi các món quà có thể đổi từ 1..K.
Dữ liệu vào: Trong tập tin văn bản CHANGE.INP chỉ gồm 1 hàng duy nhất có
2 số nguyên N và K cách nhau ít nhất một khoảng trắng (1 ≤ N ≤ 1000); (1 ≤ K ≤ 100).
Kết quả: Ghi vào tập tin văn bản CHANGE.OUT một số nguyên là số cách có
thể đổi.
Ví dụ:
CHANGE.INP
53
CHANGE.OUT
5
Bài 3: Ba lô kiểu mới – NEWBACK.* (7 điểm)
Bờm thiết kế một ba lô từ cao su siêu bền, ba lô này có tính năng mới. Ba lô có
sức chứa v0 cm3. Nếu đồ vật mang theo có thể tích không quá v0 thì không có vấn đề gì
xảy ra. Nhờ ba lô làm bằng cao su nên còn có thể nhét thêm nhiều thứ nữa, khi đó màng
cao su sẽ căng và ép lên đồ vật bên trong. Nếu thể tích sử dụng là v > v0 thì các đồ vật
trong ba lô sẽ phải chịu một áp lực p = v – v0. Bờm có n đồ vật có thể phải mang theo
khi du lịch. Đồ vật thứ i có thể tích vi, trị giá là ci và chịu được áp lực không quá pi.
Yêu cầu: Hãy xác định tổng trị giá lớn nhất mà Bờm có thể mang đi.
Dữ liệu vào: Từ tập tin văn bản NEWBACK.INP:
- Dòng đầu chứa 2 số nguyên n và v0. (1 ≤ n ≤ 100); (0 ≤ v0 ≤ 105),
- N dòng tiếp theo mỗi dòng chứa 3 số nguyên dương vi, ci và pi ; (1 ≤ ci ≤ 105),
(0 ≤ vi ≤ 105).
Kết quả: Đưa ra tập tin văn bản NEWBACK.OUT chứa số nguyên duy nhất là
tổng trị giá lớn nhất mà Bờm có thể mang đi.
Ví dụ:
NEWBACK.INP
3 10
311
424
542
NEWBACK.OUT
6
------ Hết ------
Đề thi Học sinh giỏi Lớp 12 – môn Tin học
Trang 2/2
BQ
GrAo DUC v.A. DAO TAO
on
rY rnr
cu-e. N
Irec slNrr cror QUoc crA
THPT
NAnn zots
rm cniml rr{tfc
Mdn: TIN HqC
Thdi gian: 180 phrit (khdng k€ thdi gian giao di)
Ngdy thi thtl
nhdt: lltut2alS
(DA thi c6 05 trang, g6m 03 bdi)
rONc euAN NGAY THr rrrll
TGn
bii
Bai't
Robot
Bai 2
Ddng xe
Bei 3
Trd choi kh6i hQp
vio
b6n
xnar
vio
File k5t
qui
File chuong trinh
File dii,liQu
ROBOT.*
ROBOT.INP
ROBOT.OUT
QUEUE.*
QUEUE.INP
QUEUE.OUT
BLGAME.*
BLGAME.INP
BLGAME.OUT
DAu * tluqc thay th6 b&i PAS ho{c CPP cia rg6n ng& l$p trinh tluqc s&dgng trang rtng
li
Pascal ho{c C++.
Hdy $p trinh gidi ctic bdi todn sau:
Bai 1. Robot (7 ali6m)
li
"Tim dulng tho6t mC cung". Tu6n vira ch6 tpo duo. c mQt
robot dt5 tham dg cuQc thi ndy. TuAn r6t thAnh thqo trong k! thuflt ch6 t4o m6y nhrmg trong lflp trinh
l4i kh6ng dugc tdt nhu vgy. Do d6, Tu6n m6i chi I$p du-o. c mQt chucrng trinh cdn kh6 tlcrn ginn diO
Chri de cria cuQc thi ROBCON n6m nay
khi6n robot ctra minh.
Robot di chuy6n vA phia trudc vdi t6c dQJ mdt/ei6y cho tltln khi e{p vQt can. Khi gap v$t cin robot
s€1i€ntiiipthgchiQ,g,uy@chodiintt,itruocm6tn6kh6ngc6v$tcinvi[iti6ptgcdi
chuy6n vA phia trudc. Thdi gian dd robot thuc hiQn d6i hufng chuy0n d0ns ld cpc nhanh,
tlugc coi h-b[ns 0. Robot khdng bao
vi th6
si] tt, dtng chuy6n dOng.
Ee thr} nghiQm robot, tuan da xdy dpg mQt md cung tr€n mQt m{t sdn thi tt6u r6t rQng l6n. M{t
sdn c6 d4ng m$t ludi 0 vu6ng kich thudc lx 1 mdt. Cric cQt cta luoi ttucv. c tt6nh sO UOi c6c s6
nguy6n tir -1010 d6n 1010, tir tr6i qua ph6i. C6c ddng cta ludi dugc d6nh s6 mi c6c s5 nguydn tir
-10r0 cl6n l0qti tElffig dudi. 0 nam tr6n giao cfia cQtx vd ddngy dugc g6n v6i tga iIO G, y).
tmffi *"--tu6n xdy dgng ld mQt luoi con kich thu6c NxN voi 6 0 g6c tr6i tr6n c6 tga dO (1,1),
Trong mQt s6 6 cria m€ cung c6 itpt vflt cAn, c6c 6 cdn lgi Ii 6 r6ng (6 kh6ng c6 v{t can).
fu6n d6t robot cta minh vio 6 c6 tga ttQ (x,y), mflt robot quay vii phia tr€n cria ludi vi cho robot
chuy6n dQng. Bir5t .6rg ,i tri md fu6n d4t robot khdng c6 vet c&n vd c6 ft nh6t mQt 0 chung cpnh
vdi 6 t$t robot li 6 r6ng. TuSn mu6n x6c elinh vi tri cria robot sau S gi6y.
YGu
ciu: Hay gitip
Dft li$u: Vdo
tt
Tufln
giii
quy6t vAn dC d6t ra.
file vdn bin ROBOT.INP:
Trang L/5
o
Ddng dAu ti6n chrla bt5n s6 nguy6n N, x,
-lO5
<
=x,y
!,
^S
du-o. c
ghi cdch nhau bdi ddu c6ch,
I
< N S 1000,
105;
ddng tiiSp theo mO t6 mE cung, m6i ddng g6m N ky hiQu ttugc ghi li6n ti6p nhau, m5i ky
o#'
cho bi6t 6 tuong {mg trong m6 cung c6 v$t
hiQu du-o. c lAy tt tflp {'#', '.'}, trong
o //
cin, cdn kI hiQu '.' cho bii5t 6 tuong img trong mE cung ld 6 r6ng.
K6t qui: Ghi ra file vdn ben ROBOT.OUT hai s6 nguy6n ciich nhau bdi rnQt dAu c6ch ld tqa
dQ cria
6 md robot ttpt d6n sau ^S gi6y.
Chri
f:
O xu6t ph6t vd 0
mi robot ttpt d6n sau ,S gi6y khdng
ntr6t tlii5t phni
nim trong mC cung.
Ring buQc:
o
o
C6 50%
sO
lugng test img vdi 50%
50o/os5 tugng test cdn
lpi ung
v&
sO
ai6m cria
bii
th6a mdn diAu kiQn: 1 S S S 10s.
S}Yoso dii0m cria bdi th6a mdn itiAu kiQn:
I sj$-
Vi dg:
ROBOI.OUT
ROBOT. INP
4359
tf
ROBOT. INP
ROBOT.OUT
3257
23
25
*#*
#*.
*..
*..
*...
#..#
##. #
Gif,i thich: Hinh la) du6i cldy minh hga cho vi dp thrl nh6t. tuOi con gdm c6c 6 tluo.c td nAn x6m
li rnQ cung. Dudng di chuy6n cria robot xu6t phet fi O (3,5) (0 c6 chii'R) qua c6c 6 c0a sdn thi ddu
duqc chi ra bsi c6c mfii t6n. Trong vi dg ndy 6 xudt ph6t kh6ng thuQc m0 cung. Sau 9 gi6y, robot
tlat
t1.5n
6 (2,3).
Tuong t.u, hinh lb) minh hqa dudng
di
(2,s),dqtddn6(2,6)sauTgiay
chuyiirycria robot trong
vi dUthqhai: Robot xu6t phat tir
,jfi**j/,[lo"',--,),
-.go
, ,,
O
r
-2
-t
-7"
1
0
I
?
3
4
]
6
I
n
3
4
5
at
6
Hinh 1a)
Hinh 1b)
Trang2/5
Bai 2. Dong xe
vio
b6n (7 di6ml
B6n xe kh6ch li€n tinh XYZ c6 WA
6 d6n xe khrich cfip b6n A6 nanfr kh6ch xu6ng xe. Ciic
gtJE-dA dugc d6nh s5 1 Ai5n U. Ban diAu hdnh b6n xe nhQn dugc y6u cAu cQp b6n cria mQt ddng
ta*ry-xe.r.rracrt:!9 dffi'1r" vu c6p b6n, tAn tuot r. nay sau xe kia. C6c xe kh6ch duoc d6nh
*
I
sottrta6n,n,,tn}-trrttgchdtlugcphgc,o.ffinhflncfpb6n,n6unhun6
dugc xiSp phpc vg tpi mQt trong s6 c6c $rrig-d6+4-chij5 trong khoing tir ai il6n &i (l < a, < bi S
vi il6ng thdi tpi di6m ttd ttuqc b5 tri d6 phuc vg n6 chua c6 xe ndo tronii5 c6c xe (trong ddng xe
dang x6t) d6n tnrdc tte cSp b6n tpi tl6. Ni5u c6 mQt xe kh6ch diSn luE tluo. c phpc vq md Ban diAu
M
tim dugc diAm d6 theo tlring y6u cAu d6 phuc vV n6, thi xe niy vi tdt cb citc xe
n6 sC ddng log di chuyiin sang biSn xe kh6c vd viQc phgc vg ddng xe chiim Om tai
di5n sau
Y6u ciu: Hdy girip Ban diAu hnnh b6n xe x6c rtinh sd lugng 16n nh6t c6c xe kh6ch trong ddng xe
md b6n xe kh6ch XYZ c6 th6 phpc vg tlip rlng cdc tliAu ki$n d6 n6u.
Dfr li$u: Vdo f& file vdn bin QUEUE.INP: Ddng tliu ti6n chtla sd nguy6n ducrng T (T < 5) lA sd
lugng test. Ti6p d6n ld Inh6m ddng, m6i nh6m ld thdng tin v0 mQt test theo khu6n dpng sau ddy:
o
Ddng dAu ti6n chrla hai s5 nguy€n M vi Ntuong ung ld s5 lugng di6m tI6 trong b6n xe vd s5
lugng xe trong ddng xe y€u cAu du-o. c phpc vg;
o
Ddng thrl i trong s6 lf dOng tiiSp theo m6 ti ydu cAu cta xe khdch thrt i gdm hai s6 nguydn a;
vd b; (1 1 ai 1 bi < tv| mO t& khoing chi sd cta c6c diem d5 trong b6n xe md xe kh6ch thrl i
ch6p nhSn dugc phpc vg tpi tl6. Hai sd tr6n cirng ddng duo. c ghi c6ch nhau b&i d6u c6ch.
K5t quf,: Ghi ra file vin bnn QUEUE.OUT ?"ddng, m5i ddng ghi sd lugng xe kh6ch ldn nhdt trong
ddng xe md btSn xe kh6ch XYZ c6 th6 phpc vg ld cdu tr& lli cho test tuong img trong dtt li$u vdo.
Ring buQc:
o C6 25% sd test img vdi 25o/a s6 di6m cria bdi c6: I < N, M < lA;
o C6 25%s|testkh6cungvdi 25%s6di6rncrlabdic6: I SN, M<3A0;
o C6 25% s|test kh6c img vdi 25% s6 tli6m cria bdic6: 1 Sli, M< 50000; ai: l, i:
o 25Yo si5 test cdn lai img vdi 25Yo s5 di6m ctia bdi c6: 1
1,2,..., N;
Vi dg:
QUEI'E. INP
QUEUE. INP
QUEUE. OUT
1
1
43
L4
11
11
46
L2
t2
13
13
24
t4
Giii thich: Trong vf d9 thrl nh5t, xe kh6ch thri nh6t y6u cAu dugc
QUEUE.OUI
cgp b6n & mQt trong c6c di6m d6
1,2,3, 4, ta c6 th6 x6p n6 vdo diem <16 s5 +. Ca hai xe kh6ch 2 vi 3 d6u
ttiCm tt6 sti l, do d6, kh0ng th6 phpc vg dugc xe kh6ch sd 3 (ttt5n sau;.
r8r]t]E
y6u cdu dugc c$p b5n d
H
h
[-,
'Tra ng 3/5
Trong vf dp thri hai, hai xe khilch dflu ti6n c6 thO x6p vdi di6m tI6 s6 I vA 2 (xe 1 vdo eliAm d5 s6 t
vd xe 2 vdo di6m d5 sO Z, ho{c xe I vdo di6m O5 s5 Z vA xe 2 vio di6m d6 sd t;. Xe kh6ch thr} ba
phii x6p cflp b6n tpi tti6m a6 s5 :. D6n luqt xe khich thrl tu, ta khdng tim tlu-oc ttirSm d6 nio drip
img y€u cAu cria n6, vi thii b6n xeXYZ ctrAm Am phuc vg ddng xe tai d6y, mpc dir ntiu b0 qua xe
kh6ch tht tu, ta c6 thd x6p di6m d6 cho xe kh6ch s6 S lnhung xe ndy vd c6 xe khdch sO O aa theo xe
kh6ch
sO + Ai
tim b6n xe kh6c).
Bai 3. Trd choi rnOi ngp (6 di6m)
Trd choi kh6i n$p H mQt hd choi v6i mQt m6i frQp chu nh0tj& vi tr6n ludi
hinh cht nhgt 1/ du-o. c chia thanh mxn 6 vu6ng tlon vi. C6c hdng cria lu6i tluqc d6nh s6 trl t tdi m tit
L
uen xuong ouor va c6c cQt cria lu6i clugc d6nh s6 ttr t tdi r tir trdi qua phAi. 6 nim tren giao cria
hing f vd cQtT dugc ggi lA 6 (r,j). Ban dAu, mOi nQp dugc tl4t d gbctrditr€n crla luli H, cU th6 mflt
tlay kh6i hQp chi6m dtng axb 6 cria ludi, Id c6c 6 nim trong hinh chft nh{t con cta ludi ^Fl vdi 6 d
g6c tr6i trOn ld (1,1) vi 6 & g6c phii dudi ld (a,b). M6i budc, nguoi choi c6 th6 thpc hiQn mdt trong
cric 1o4i thao t6c sau:
"
.
DAy t
Let khOi hQp
Vi dp, cdc hinh
16n
phii
mOt 6;
trdn, xu5ng dudi, sang tr6i ho{c sang phii mQt 6.
vE trong Hinh 2
du6i diy mO ti
vitri
cria
ttr6i trqp kich thu6c 1x2x1
sau khi thpc
hi$n tung lopi thao t6c.
I
Trpng thdi tru6c khi thgc hi6n thao t6c
U,
DAy l6n tr€n
DAy xu6ng dudi
DAy sang trdi
EAy sang phii
LSt xuting duoi
L$t sang tr6i
Lflt sang ph6i
{1
a
L{t
l6n tr6n
Hinh 2.
Trang 4/5
Khi bit d6u choi, tdt ca cdc 6 md khdi hQp tld l6n tlugc gt s6ng mdLu xanh vd c6 fr 6 kh6c tr€n ludi
itusc b$t s6ng miu {{.4;a" 6 cdn l4i arrye-the4il rraOJtr''"iE-af61qi ra n6-G, ,GG r.r,i
ttrEe-menrtaot6tnay, kh6i hgp vin nim gqn trdn fu6i Hvi kh6ng tld l€n O s6ng miu d6 nlo. Sau
khi mQt thao tdc dugc thgc hiQn, nhttng 6 bi kh6i hQp tld l6n dang O trpng *rai tit s6 duo. c bgt s6ng
mdu xanh, nhtrng 6 dang
4i b$t s6ng mdq xanh. Nhigm vU cria
nguoi choi li tim c6ch thgchi$n ddy cic thao t6c hqp lQ A6 OAt duo. crrGl-ts6ng miu xanh nh5t.
Il vd vi trf cria c6c 6 s6ng mdu d6, hay x6c
dinh s6 lugng nhiAu nh6t c6c 6 tlu-oc bflt sring mdu xanh md ngudi choi c6 th6 dpt iluo. c.
YOu cAu: Cho kich thu0c
Dit li$u: Vdo ttr file
I
v6n
ttr6i fr6p, kich thudc cria ludi
bin BLGAME.INP:
Ddng thr? nh6t chfa s6u sti nguy6n duong a, b, c, m, n, k, c6c
sr5
dugc ghi c6ch nhau b6i d6u
c6ch;
.
Ddng
thf s trong
c6ch x",
y,li
s6
f dOng ti6p theo chfa hai s6 nguy€n duong du-o. c ghi ciich nhau bdi d{u
tga d$ cria mQt 6 dA bAt s6ng mdu d6 (s
:
1,2, ...,
k).
K6t qui: Ghi ra file vdn b6n BLGAME.OUT mQt s6 nguy€n auy n(lrta ,6
tluo. c b$t s6ng mdu xanh md ngudi ch
\
,M*
"nff6t cac 6
Vi dg:
BIGAME. INP
BIGA},TE.
12t332
22
33
OUT
,I
7
Giii thfch:
Hinh vE b6n ph6i m6 tf, trang thrii uit eiu trd ch
phii, d6y xu6ng du6i, d6y lOn tr€n, it6y sang tr6i, d6y
sang tnii, iiAy xu6ng duoi, dAy xudng du6i, cu6i cirng rtAy sang
phii d6 bQt itugc 7 6 ctnludi s6ng mdu xanh.
tdc: LQt sang
Rdng buQc:
c
C6 25o/os6 test img
c
C625Yosi5 testkhSc img v6i25%s5
o Cb
o
25o/o s5 test
vdi
khdc img vorZSYo
25Yo sd test cdn lai rmg
: b : c : l; ffi, n I tOO;?
Oi6m criabdi c6 a: b: gm,nSl00;
25o/o s6di6m cria bdi c6
sO diOm crla
a
bii
v6i 25% s6di6m cria bdi c6 m. n < 1000.
ndt
a
Th[ sinh khdng tfuqc su d4ng tdi liQu.
a
Ciin
bQ
c6 m, n < 100;
coi thi khdng gidi thich gi thAm.
L
{ .i'
/?\
t I l"-rl *," \
n,l
I
j;
\-r'
/
td
'/
.r}\
--Trang 5/5
GrAo DUC vA EAO r+o
BQ
rY rm cHeN Hec srNH cr6r eu6c crA THPr
NAM zors
ot rnr cnimn rl{tIc
MOn:
TIN HgC
Thli gian: 180 phrit (khdng tri thdt gian giao cld)
Ngdy thi thf hai: lzl0l?Al8
(E6 thi c6 05 trang, g6m 03 bii)
rONc QUAN NGAY THI THTIHAI
TGn
Bii
4
bii
Phdrn
thu&ng
BAi 5
Ngulid{c
Bai 6
Diy xdp xi ting
Diu * ilugc thay th5
bi?t
qui
File chuong trinh
File dO liQu vdo
File k6t
BONUS.*
BONUS.INP
BONUS.OUT
SPECONE,*
SPECONE.!NP
SPECONE.OUT
SEQUENCE.*
SEQUENCE.INP
SEQUENCE.OUT
btfii PAS ho{c CPP cria ngdn
ngt l$p trinh ituqc srfr dgng trmng tng lir Pascal ho{c C++.
Hdy lQp trinh gidi ctic bdi todn sauz
Bei4. PhAn thu&ng (7 tti6m)
Vinh
li ngudi thEng cuQc trong mQt cuQc thi "Tim hi6u ki6n thrtc v[ trp" vd duo. c nh$n c6c phAn
thu&ng do cdng ty AZ tdi trg. TrCn m6i 6 cria mQt ludi kich thu6c
nx nd vudng c6 cpnh dQ ddi
tlcrn
vi, Ban tO chrlc xi5p mQt m6n qud. C6c ddng cria b&ng dugc cl{nh sO ttl t ddln n, tir tr6n xu6ng dudi
vit citc cQt cria bing dugc d6nh s6 & 1 d6n n, ti trdi qua ph6i. O nam tr6n giao cua ddng i vd cQtT
tlugc ggi la 0 (i,j) vd m6n qud tr6n 6 d6 c6 giri tri ld a;1 Q < i, j < n).
Ban t6 chrlc cho ph6p Vinh chgn mQt trong ft phuong rin nh$n pnan thucrng. PhAn thu&ng hong
phucmg 6n thri s (s : 1, 2,... , k) iltrcr. c xdc tllnh nhu sau: Vinh dugc nhfln c6c m6n qud tr€n cac 6 cria
ludi thuQc mQt trongp hinh vudng kich thudc r x r, trong d6 hinh thtr hxirc itinh b0i 6 g6c h6n tr6i
c6 tga dA
VWril, h: 1,2, ..., p. Chf ), li c6c hinh vu6ng ndy n6m tren vgn trong ludi vd c6 thti c6
c6c hinh vu6ng li giao nhau.
Y6u cAu: HEy gitip Vinh chgn phucrng 6n nh$n phAn thu0ng vdi t6ng gi6 tri cfr_ cdc m6n qud nh0n
dugc ld lcrn nhAt.
Dif liQu: Vdo tir flle vin ban BONUS.INP:
c
o
.
Ddng
tht
nhSt chfa b5n sti nguyEn duong n, k, r,
p;
Ddng thrl i trong sii z dong titip theo chfia n s6 nguydn ducrng,
1,2, ..., n; j : l, 2, . .., n);
sO
theo chta2xp s5 nguydn duong
x6c tlinhp hinh vu6ng trong phuong 6n thri s (s : 1, 2, ..., k).
Ddng thrl s trong
sO /. dOng tii5p
ttrrtT ld aii(aa < 106;, 1i
xstt lsl,xs2t
!s2t ...,
xsp,
:
lsp
Hai sti li6n ti6p tr6n cing ddng tluoc ghi c6ch nhau bOi d6u c6ch.
Trang 1/5
Kdt qurf,: Ghi ra file vin ben BONUS.OUT mQt s5 nguy6n duy nhSt h gi6 tri lon nh6t cria t6ng gi6
tr! c6c m6n qud mi Vinh c6 th€ nhfln tlugc.
Ring buQc:
o C6
25Yosi5 test (mg
o C6 25o/as6
o C6
o
vdi 25% s6di6m cria bii c6 n <
test khric
25Yo s6 test kh6c
50;
k<
50
25Yo si5 test cdn lpi img
v6i
/
fr
<
10s;
p : 2;
25o/o sti ei6m cria bdi c6 n < 500; fr
<
105;
p
img voillYosO Ai6m cria bdi c6 n <500;
img v6i
p < 5;
25% sd di6m cria bdi c6 n < 500; k
:
3;
< 10s; p < 5.
Vi dg:
BONT'S.INP
BONUS. OUT
4223
1111
1111
1111
1111
L72233
111331
L2
Giii thich:
C6c hinh vC dusi c16y m0
trong m6i phuong 6n:
C6c 6 thuQc phucrng 6n
T6ng gi6 tri
giii
I
ti
2 phuong an gi6i thu&ng trong vi dp vd tdng gi6 tri crla gi&i thuong
le c6c 6 t0 n6n
den.
10.
thucrng theo phuong 6n ndy ld
C6c 6 thuQc phuong
T6ng gi6
6n2ldcfc
ffi giii thuong theo
6 t6 nAn den.
phucrng 6n ndy ld 12.
Bai5. Ngu&i d{c biQt (7 di6m)
Trong trudng hgc md S
gpo titip vdi nhilng hgc sinh eti ld ngudi d{c biet.
dinh ai trong s5 c6c
k6 vd cac lAn trao d6i tin nt An rren
mpng xE hQi. Chring ta kh6ng cAn quan t0m d6n vi$c Son ttd lim th6 ndo dti c6 rluo. c bing thSng kO
ndy. Vi ban! th6ng k0 ld qu6 l6n n€n Son cAn dtin sy trg girip cria mdy tinh. Theo qui t,6c, n6uiqt
hgc sinh chua lA tt{c bi-Ot mi trao OOi tin nh6n vdi it ra ld K ngudi da lA d6c bigt, m5i ngudi it nhdt
hgc sinh
r.ong
Scrn mui5n x6c
m6tlAx,thihgcsinhd6s€tr&thdnhngudia4cui6@6ngthuthspth6ng
tin n€n Som chi ghi nhfln
c c6c tin nhiin dE
x6c chfing du-o. c thgc hiQn O c5c thdi ttiOm ndo.
tlucv.
c trao d6i gifra hai ngudi
mi kh6ng bi6t
chfnn
Trang2lS
