HO sT DAM (chri bien)
DO DUC DONG - LE MINH HOANG . TRAN
NcuyEru THANH
t\\JL.rtEt\
Iftrll
utrtrtc

\

o6

HUNC

AA

TAI IIEU
CHUYEN TIN H0c
I
I
\rl

BAI TAP n

QUYENJ

nHn
xuAr sANr orno ouc vrEr runvr
t,
.

HO SI DAM (chri bien)
DO DUC DONG - LE MINH HoANG - TRAN
NGUYEN THANH HUNG

,

Do HUNG

lA/i

TAI IITU
CHUYTN TIN HOC
l1
\

/'l

'{3

BAI TAP
OUYEI

(Tai bdn ldn thn nhtir)

NHA XUAT AAN CIAO DUC VIET NAM


'

Lor Nor oAu


Bo siich Tditiau chuyanTin hoc - Bdihap Quydn 1,2,3 duoc vidt kdm vdi b6
Tdi li4u chuyanlin hpc - Quydn 1,2,3 ruong rmg dd du-o.c xuat brin. G4c tac giA
tham gia biOn soan b0 s6ch ld nhirng thdy gi6o dd vl dang d?y o c6c rrudng chuy6n,
ldp chon hodc tham gia cdc kh6a bdi dudng thi tin hoc qudc td, bdi dudng gii{o vion
tin cho ci{c trudng chuy6n theo chuong trinh crja BO Gir{o duc vd Dho tao, mong mudn
xAy dung du-o. c c6c tdi 1i0u c6 tinh h€ thdng phUc vU t6t cdc ddi tuong thuoc llnh vuc
chuy€n tin hoc.
C6c cudn Tdi li4u chuyan Tin hoc - Bdi tdp ddu c6 cdu trfrc nhu nhau, g6m hai
phdn:

Phdn I - Bii tQp bao g6m tat ch cdc bei mp rrong nhfrng chuyOn dd cira s6ch Tdi
Hau chuyan Tin hoc fiong rlng vh c6c bdi mp bd sung, duoc sap xdp tD d0 den
kh6, til don gi6n ddn phrlc tap,
Phdn II - Hudng dAn giii bii tAp c6 the IA nhrrng huong ddn chi tidt dd girip ban
doc tim duoc ldi giii hoac chi ld doan chuong trinh chinh girip ban doc hidu vd tim
du-o. c ldi giii hoac chuong trinh ho)n chinh dd tham khio. Ddi vdi m6t sd bli tap
th) c5 thd chi ld d5p 6nhay huong d6n ngin gon.

Hai bo

s6'ch Tdi liaw chuyan Tin hoc vd, Tdi liau chuyan Tin hoc - Bdi tdp tao
thhnh h€ th6ng tdi liOu kh6 hodn chinh theo dinh huong Chuong trinh ciic chuy€n
d€ chuyOn tin hoc dd duoc Bd Gir{o duc v}r Ddo tao ban h}rnh. Do vdy cDng vdi b6
s6ch Tdi li0u chuy0n Tin hoc, b6 sSch Tdi liAu chuyAn Tin hoc - Bdi ttlp sd ld tdi
liOu thiet thuc phuc vu cho gi6o viOn, hoc sinh c6c trudng chuyOn, l6p chon ci
Trung hoc phd thOng vd Trung hoc co s&. Ngodi ra, b6 silch cdn lh tii lieu tham
khdo bd ich cho vi€c tap huan sinh viOn cdc trudng Dai hoc, cao d&ng rham gia
ciic k) thi olympic Tin hoc Sinh viOn Tobn quoc vd Ki rhi lap rrinh vi0n eudc te.


Ltru

!

\Iac

dD cdc tdc gi6 vd Ban.biOn tap dd cd gSng hobn rhiOn nhung ch6c chSn b0

khi sft dqng

bQ

sdch: cdc bdi tap ffong b6 s6ch ndy

ddnh sd nhu trong
sdch li thuydt; c6c bhi tap bd sung duo. c dd & muc ri€ng vd drinh sd tidp rheo.
du,o.c

sdch cdn nhidu thidu s6t, c6c tdc gia mong nhan duoc nhidu kien ddng g6p dd
sdch s€ hodn thiOn hon, phuc vq ban doc duoc hi6u qu6 hon. Cdc g6p
i,xin giri vd:

f

BanTodn-Tin, Cdng ry t'o pldn Dich vu xuat bdn Gido duc Hd N6iNhd xudT bcinGido ducVi€t Nam, lSTB,GicingVd, Hd NOi.
C6c tirc gih


1


tl

I
X

r1

C

p

V

t

I

8.

Tr

In

ca.

d6

Or

ph,


Vf

t--

I-T

t;

tq
l-

t

Qro"


Bei t+p
rixu roAx

cHUYnx on

8. HiNH Hoc
8.1. Tim d0 dai doqn ttring nim trong tam gi6c

Tr€n m[t phing cho tam gi6c ABC vd do4n tning DE. Tinh d6 ddi cira phAn doan
thing DE nim trong tam gi6c.

Input:


BAI0I_C8.INP g6m hai dong: Dong thri nhAt c6 s6u s6 thuc XA, yA,
XB, yB, Xc, yc. lAn luot tung cdp ld toa dO tucrng fng cira ba dinh A, B vd C. Dong
thf'hai ld b6n s6 thuc XD, yD, Xe, yE lin lugt hrng cdp ld toa d0 hai di6m D vd E. (-)
output: TOp BAI0I_c8.our chi c6 m6t dong duy nh6t ghi so thuc ld dq dai
phAn doan thing DE nim trong tam gi6c ABC.
Vi dq:
BAIOl CB. ]NP
BAIOl CB.OUT
TQp

422442
4233

3.

r6228

8.2. Tim di6n tich phan chung c0a hai tam gi6c
Tr€n mdt phang cho hai tam gi6c. Tinh didn tich ph6n chung cria hai tam gi6c d6.

Input:

BAI02_C8.INP g6m hai dong, m6i dong c6 s6u s6 thuc lAn lugt ttmg
cflp ld toa dQ tuong ring cira ba dinh cira mOt tam gi6c. c6c toa d0 c6 gi6 tri tuyQt
eOi tnOng vuot qu6 l0r.
TQp

output: T€p BAI02_C8.ouT chi c6 mQt dong duy nhAt ghi s6 thuc ld di€n tfch
phAn chung cira hai tam gi6c ndy (chinh x6c dr5n


l0-').

vf dg:
CB. INP

' .\'€tr khdng

cht' dinh gi th1m thi trong sach nay xin ilu'o'c hi€u rdng cac s6 trOn cilng ddng
.ivoc ghi c'ach nhau it nhtit m6t diiu cach.


8.3. Tinh diQn tich

phin ph0 b&i N hinh chir nhft

I

Cho hai hinh chfr nhflt v6i c5c cpnh song song v6i c6c tryc toA dg. M6i hinh cht
nhit x6c dinh bcri to4 dQ hai dinh.d6i. Tinh diQn tich phan m[t phang dugc phu boi
hai hinh chfl nhQt vd diQn tich phdn chung ctra chring'
Tt bei to6n ndy ta suy ra bdi to6n t6ng qu6t tinh diQn tich phAn phri boi N hinh

8

chf

s€

nh0t nhu sau:


c6c
Tr€n mat phing toa d0 xOy, cho N hinh cht nh4t c6 c6c c4nh song song v6i
tryc toa d0.
a) Tinh diQn tich phAn mflt phing dugc phri bdi N hinh chir nh4t niy.
b) Tinh dign tich phAn chung cua N hinh chfr nhit ndy'
Input: TQp BAI03_C8.INP c6 dong diu ghi s6 nguy6n N (1 < N S 10000). Trong
N do.rg ti6p theo, dlng thf i co b6n sO nguy€n Xir, Yir: xtz, Ytz th6 hiCn (xir; yl) ld
i
toa d0 dinh tr6i-du6i vd (xiil y,z) ld toa d0 dinh ph6i+r€n cria hinh chir nh4t thu

(

yit < Yiz<30000)'
Output: TQp BAIO3-C8.OUT c6 hai dong tucrng ung ghi k€t qua cau a) vd cdu b);
,
t . .. ,l
r\
cac so ghl tu oau oong.
(0 < xir < xiz S 30000, 0

BAI03

BAIO3 CB. INP

0123
1032
1034

iir


CB . OUT

di

In

ti(

o

da

Vi
t--

L_

I4
l0
la
t14
L__:

8.;

1

m6

Inl


hai di6m xa nhau nh6ttrong N di6m

Input: TQp BAI04_C8.IM c6 ddng dAu ghi s6 nguy€n N (1 S N < 10000); trong N dong
<
<
ticp ttreo, ddng thir i c6 hai s6 nguy€n xi, 1li |d toa d0 di€m thir i (0 xi , yi 30000).
Output: TQp BAI04_C8.OUT ghi khoing c6ch hai ditim xa nhau nhAt chinh x6c

Nr
<3
Ou
thor
thur

Vir

I--

t6i
Vi dq:

10-4.

BAIO4

BAIO4 CB. INP

00
a2

30
44

l,

10

Tr€n mit phing cho N di,5m. Tim hai di6rn xa nhau nh6t trong N di€m d6.
Gqi j/: Hai diOm cAn tim ld hai dinh cua da gtitc bao 16i'

4

Si

lo

Vi ds:

aa

T

5.6569

CB . OUT

l4
t^
lu
l4

lo
la


8.5. Phdn hoqch N di6m thdrnh K tap c6

duung kinh t6n ntrdt dqt ntin

Tr€n m{t phang cho N di€m. Hdy phdn hopch N didm thdnh K tap Sr, S2,..., Sr
sao cho ducrng kinh lon nhAt cria K tflp ln nho nh6t, trong d6 ducrng kinh ctra tOp Si
ld khodng c6ch l
8.6. ircn mflt phing cho N diiSm doi mQt kh6c nhau. Hdy tim hai trong N di6m
sao cho ducrng thing di qua hai di6m d6 chia mflt phEng thdnh hai phAn md s6
di6m thuQc hai nria mflt phing ch€nh lQch nhau it nh6t.

Input

BAI06-G8.INP c6 ddng dau eh ro nguyOn N (l s N s 10000). Trong N ddng
ti6p theo, dong thri i c6 hai s6 nguy€n xl, y1 ld toq dQ ditim thu i (0 < x; , y, < 30000).
TQp

output: T€p BAI06-G8.oUT ghi to4 d0 hai di6m tim dugc, m6i eiem tr€n mQt
dong.

Vi du:
BAIO6 CB. INP

BAIO6 C8.OUT

4

00
40
04
44
8.7. Tr€n mat phing cho N di6m. Hdy rim tap it nh6t c6c ducrng thing sao cho
m6i Cicm tron! N di€m da cho thu6c it nhAt mQt duong thing.

Input:

BAI07-C8.INP c6 dong dAu ghi s6 nguy€n N (t < N s 10000). Trong
N dong ti6p theo, dong thir i c6 hai s6 nguy6n x;, y; lir toa dQ rti6m thf i (0 < x; , yl
s 30000).
TQp

output:

TQp

BAI07_c8.our c6 dong dAu ti6n ghi

so k ld so dudng thing it nhAt
thod mdn y€u cAu ae uai. Ti6p theo ld k dong, m6i dong ghi s6 hiqu ciic di6m cirng
thu6c m6t ducrng thing.

vf du:
BAIOT CB. INP

BA]07

2

0
0
4
4

T2
34

CB . OUT


8.8. Noi N di6m

thinh m?ng li6n thong

Tr0n m[t phing cho N di0m. Hay nOi N di€m thinh mQt m4ng li€n thong bdng c6c
doan thing nOi .a. c[p di6m sao cho t6ng dQ ddi c6c do4n thing dugc n6i h nh6 nhat'

8.9. tr€n mflt ph6ng cho N hinh cht nh4t c6 c6c c4nh song song v6i hai tryc to4
d0. Hinh thri i x6c dinh boi hai dinh dOi (xi; yi) vi (zi; ti). Toa d0 c6c ditlm ld
nguyen, c6 gi6 tri tuyQt eOi nrOng vugt qu6 104. Khi t6 c6c hinh chir nh?t ndy
Uing *au xanh, ta nh{n dugc mQt sO phAn m4t phing dugc td xanh. Tinh tOng dO
ddi c6c ducrng bao quanh c6c vr)ng mdu xanh'

Input: TQp BAI09_C8.INP.
Output: TQp BAI09-C8.OUT.
Vi dg:
BA]09 CB. INP

1

t

I

k

n

v

BAIO9

CB.OUT'

AQ

d

It

0-250
-2 -1 1 3
5166
0225
L456
3045
1153
8.10. Tim nhin

((

\

s(

hi
L(

o

th

Tr€n mdt phing cho N do4n thlng (l S N < 1000). Toa dO c6c ddu mirt cua c6c
do4n thing ld c6c s6 nguy6n kh6ng 6m khdng vugt qu6 20000. C6c ducrng thdng
thu dugc bing c6ch k6o ddi cdc do4n thing d6 cho ludn c6t hai truc toa d0 vd hai
giao di6m cirng g6c toa d0 tao thdrnh mQt tam gi6c vu6ng cAn. Kh6ng co hai-doan
thing ndro giao nhau.
Ta n6i m6t doan thdng ld nhin thtiy dwqc tit g6c toq dQ O, n€u tim ra di6m X t€n
n6 sao cho doan thdng OX kh6ng cat biit cu dogn ndo trong s6 cdc doqn thdng dd
cho.

Hdy vitit chucrng trinh dtim s6 doun thing nhin th6y tu gr5c toa

d0'

th

ct

I
---:

z

i

*

8.

Input: TQp BAIl0-C8.INP. Dong dAu ti6n chria s6 do4n thing N. M6i m6t trong Di
sO N ddng ti€p theo chira b6n sO nguy€n khong 6m Xr, Yr, Xz, Y2, phdn c6ch boi
nq
toa
d0
(Xz;
le
Y2)
con
nhAt
thri
mrit
dAu
dQ
cua
(Xr;
ld
toa

Yr)
d6
trong
dAu c6ch,
C;
cua dAu mtit thri hai cira do4n th6ng tuong

I

img.

dir


Output:
Vi dq:

TQp

BAI10-C8.OUT ghi s6 dopn thing nhin th6y dugc tu g6c to4

BAIlO

dQ'

BAI1O C8.OUT

CB. INP

4

I

3 13 11 5
L4 1 10 5
1014204
5610 1
8.11.

[h6i phgc tla gilc

Blm

vE trdn mflt phing mOt hinh da gi6c t6ng qu6t (ducrng g6p khirc khep kin
khdng tu cit) vdi c6c canh song song v6i c6c truc toa d0 vd c6c dinh c6 top dQ
nguy€n. Sau d6, v6 ;i Bom dd xo6 mht tdt ctt chc canh thlng dimg (canh song song
v6i truc tung) cria da grhc. B4n hdy tim c6ch girip Bdm tinh di6n tich cira da gritc
dd vO ban dAu tir nh.irng th6ng tin con l4i.

rg

Input: Tpp v[n bin BAII l_cS.INP. Dong dAu ticn chira N ld s6 c4nh nim ngang
(canh song song v6i truc hodnh) cria da gi6c il6 cho (N < 1000; Ha6i dong trong s6
N dong ti€p theo chira th6ng tin vd mQt canh nim ngang cria da gi6c bao g6m b6n
A^
s6 nguy6n X, y, u, v duoc ghi c6ch nhau boi ddu c6ch, trong d6 (x; y) vd (u; v) ld
hai cflp toa dQ cua hai dAu mrit cira cpnh nim ngang. Gi6 thi€t ring cdc to4 dQ li
c6c s6 nguy€n c5 gi|trl tuygt OOi ktrOng vugt qu6 100.
output: TCp vdn ban BAII l_c8.our. Dong dAu ti€n ghi diQn tich da gi6c. Dong
thu i tong s6 2*N dong ti6p theo chua toq dQ dinh thri i crta da giac dvgc li6t kd

theo thri tg di vdng quanh da gi6c rheo chidu kim d6ng h6 (dinh bit dAu duqc
chqn tuj,li).

ai

Vf

,

Ic

pn

dqr:

BAI11 CB.INP

BAI11 C8. OUT
4

11

An

l_J

33
31

VA

8.12. Dinh nui
Dinh nrii c6 thd nhin thAy duoc o chdn troi chi khi n6 kh6ng bi che khu6t boi mQt
ngon nui kh6c hay ld ducrng vi6n cua n6 kh6ng bi dn trdn n6n mQt ngon nrii kh6c.
Cho bitlt tdt cilc6c d6c nrii ddu c6 g6c nghi€ng ld 45o vii cho bi€t toa d0 vi'd0 cao
dinh cria t6t ctt circ ngon nfi. Xrlc dlnh sO luqng dinh nrii nhin th6y dugc.


Input:

BAII2-G8.INP: Dong dAu tidn chria si5 nguyOn N (1 s N <
10000). v5i dong trong N dong titip theo chrla hai sti nguy€n x, y dugc ghi c6ch
nhau boi d6u'c6ch, lAn luqt ld top d0 vd d0 cao cria
s

TQp vdn bdn

10000).

output:

vin bin BAI12 c8.our ghi
BAI12 C8. INP

TQp

4

nfi nhin th6y dusc.

BAI12 C8.OUT

so lusmg itinh

C

2

k

OJ

123

C

1,6 9.

si

2t4

nl

v

8.13. Ddi phun

nu6c
i

lim

dgp c6nh quan try sd, ban Gi6m rt6c mQt c6ng ti quytit tfinh xdy dung o
sdn ti6n sinh try s0 c6ng ti m0t dei phun nu6c. Ddi phun nu6c c6 d4ng mQt hinh
trdn vdi kich thu6c lcrn nh6t c6 th6 dugc. Nhe thi.st ki5 dugc bitit ld sdn tidn sdnh
DC

ti c6 d4ng hinh chf nhft kich thu6c xxY. Tuy nhi€n, khi lpa chgn vi tri
cho dii phun nu6c, nhd thi6t kc gap phii mQt v6n d€ phric t4p: Trong sdn ridn sinh
c6 N cQt hinh try trdn xoay kh6ng dugc phdp di chuyi6n. vi vfly vdn d6 d6t ra cho
cira cong

thitlt t<6 ta can dflt ddi phun nu6c o vf tri ndo ttti n6 c6 b6n kinh lcrn nh6t c6 th6
duo. c, dbng thoi kh6ng dugc c6 diQn tich chung kh6c 0 voi c6c cQt. Bpn hay lap
trinh giirp nhi thitit k6 giai quy6t v6n dC tr€n.

Tri

Input:

phr

nhd

.
.

l0

TQp vdn b6n

BAII3_C8.INP;

D.ong dAu d€n chfa hai s6 thgc x, y (l < x, y < l0o). Gie rhi6t
ti6n sdnh ld hinh chii nhgt c6 roa d0 cdc dinh ld (0; 0), (X; 0), (X;

Y).

ring

J)

s6n

vd (0;

Ddng thir hai chria s6 nguyOn N (0 < N < 10) las6luqng cQt trong s6n tidn
s6nh

&'

rnl
ri6

v6i
Ou
du(

.

Dong thri i trong st5 N dong dtlp theo chfa ba sO thyc Xi, Yi vd Ri cho bi6t
toa dO tdm vd b6n kinh cria cOt thir i (Ri ( Xi ( X - Ri, Ri < Yi < Y - Ri, 0.1

(

-irr.I.I).
t2'2)'

-xj)'?+Gt

C6c sd trdn mQt dong trong tQp

Output:

TQp vdn

dt

2Ri+\vdimeiilj).

liQu ttugc ghi c6ch nhau

bin BAI13-C8.OUT ghi ba sO thgc XF, YF,

boi d6u c6ch.

Rn ld toa d0 vd b6n

lrlI

kinh cua ddi phun nu6c.
Chil !,: Ddi phun nu6c phii dugc d[t trong sdn, dugc phdp titip xric v6i tudng cria
sdn hoflc cQt nhung kh6ng dugc c6 diQn tich chung kh6c 0 vdi c6c cQt. N€u c6
nhi€u vi tri cirng cho b6n kinh lon nh6t chi cAn dua ra mQt trong s6 chirng.

Vi dg:

r0

20

BAI13 C8.OUT
5.000 s.000 s.000

20

r0.000 10.000 9.314

BAI13 C8. INP

0

20

:
222
18 2 2

2LB2
A

18 18
20 20

2

:

9.510

'7

.054 7.053

A

222
18 2 2
311 2

T6164

BAI TAP BO SUNG
8.14. Tinh dign tich

phin ph0 c0a N tam gi6c

r.3

m{t phdng
to4 dQ xOy, cho N tam gi6c. Tinh
phir boi N tam gi6c ndy.

TrOn

Input:

diQn

-:

tich phdn, m{t phing dugc

BAI14_C8.Ii{P c6 ddng dAu ti6n ghi s0 nguy€n duong N (2 < N < 10).
Tiiip theo ld N ddng, m6i ddng c6 s6u sO thgc lAn luqt tung cap ld toa d0 ruong img
vdi ba dinh ctra mQt tam gi6c. Circtoa d0 c6 gi|tri tuyqt eOl ttrOng vugt qu6 103.
TQp

Outputr T€p BAIl4_C8.OUT chi c6 mQt dong duy nh6t ghi s5 thqc ld diQn tich
dugc phri boi N tam gi6c ndy (chinh x6c d6n l0-2).
11


Vf dg:

nl

BAI14

BAI14 C8. OUT

CB. INP
7.00

2

dr

hi

022442
032543

G

d(

Ir

8.15. Tinh s6 hinh vu6ng
X6t tdng th6 mQt khu d6t hinh vu6ng A c6 kich thudc NxN (don vi) dugc,chia
thdnh ludi 6 vu6ng dcrn vi boi nhi6u hing rdo. Gi6 sri c6c cQt m6c cta hdng rio
.a
dugc scrn mdu trdng ho{c den. Y€u cdu x6c dinh sO luqng c6c hinh vu6ng trong
khu A c6 cdc dinh ld c6c cQt m6c cirng mdu. Vi dp, khu ddt qx4 nhu trong hinh I
chi c6 m6t hinh vu6ng nhu dugc chi ra trong hinh 2.

5(

hc

dr

o

gir

ph

vi

a

Hinh

Hinh 2

1

BAII5_C8.INP. Dong ddu ti€n chria s6 N ld canh cria khu dat A (l S
N S 50). N dong sau, m6i dong chua N sO thuqc tap hqp {0, l}, the hien c6c c6t
l ,.
m6c hdng rdo trong khu ddt. NOu di6rn c6 to4 d0 (i, j) ld cQt mdu trlng thi sd thri j
cua dong i bdng 0, cdn nOu Id cQt m6c den thi bdng 1.
Output: TQp BAII5-C8.OUT, ghi s6 lugng hinh vu6ng tim duoc.
Vi du:

Input:

TQp

BAI15
4

0100
0011
1000
0111

BA]15 C8.OUT

CB. INP
1

8.16. Ghia ddt
MOt nguoi cha; khi m6t di, A6 tai mQt mdnh dAt cO hinh d4ng m6t da gi6c l6i ldm
cria thua kii cho hai nguoi con cria minh. Trong di chric 6ng y€u cAu ring hai

l2

8.'
DC

ph(

qn

dfll
cua

chu


nguoi con phei chia m6nh d6t ndy thdnh hai phAn c6 diQn tich bang nhau theo mOt
duong ranh gioi thing dgc theo phucrng Nam-B6c. Ban ld nguoi dugc giao giirp
hai nguoi con thqc hiQn bdn di chirc ndy. Hdy vi€t chuong trinh tim c6ch chia.
Gia su mdnh e6t ta da gi6c l6i voi c6c dinh ld ArAz...A,,, ni- tr€n m{t phdng toa
d0 c6 truc Oy nim theo huong Nam-86c, tryc Ox theo hu6ng TAy-Ddng.
Input: T€p BAI16_C8.INP: Dong diu ti€n ghi N ld s6 dinh cua da gi6c (N <
5000). Trgng N dong ti€p theo, dong thu i ghi hai s6 nguy€n x;. y; lin luhodnh dQ vd tung d6 cria di€m thri'i trong sO N dtnh da gi6c (c6c dinh oia da gific
duoc li6t k€ theo chi6u xu6i ho{c ngugc kim d6ng hO).

Output: T€p vdn brin BAI16_C8.OUT ghi mQt sO thuc x6 v6i if nghTa dudng ranh
gidi dung d6 chia e6t ta duong thing X : Xo (xo vitit voi b6n chfr' sO phAn thap
phAn).

Vi du:
BAI16-CB. INP

BAI16-C8.OUT

4

1.0000

00
20
22

02

8.17. Khuon thep (De thi hec sinh gidi 2005- Bdng A)

)t

j

De chuAn bi cho le hQi ki ni6m 30 nim ngdy Chi6n dich H0 Chi Minh todn thing, giiii
.l
phong mi€n Nam, th6ng nhdt ddt nuoc, nguoi ta cdn gia cdng c6c loai khu6n thdp c6

l6i M dinh. V6i khu6n thdp duoc tniet te trOn m6t t6m thdp cirng c6
.
da gi6c loi N dinh, kh6ng c6 canh ndo cua khu6n th6p nam gon tr€n mdt canh

dang da gi6c
dang

.1,,,

cua t6m thdp. D0 ti6n cho vi6c gia c6ng, khu6n thdp dugc v€ sao cho hai clucrng thang
chua hai c4nh kh6ng kd nhau cua n6 kh6ng

cit nhau o b6n trong t6m thdp.
Y
6

l
m

ai
1a
l-l


C6ng viQc chinh cAn ldrn trong qu6 trinh gia cdng ld sri dung mdy cat dti cit duqc
.,i
khu6n thdp tu tdm rh6p ra. R6 rdng ld cAn phii thuc hiQn M nh6t c6t. vtSi nhft cit

duoc thuc hiQn b[ng c6ch chon m6t canh ndo d6 ctra khu6n th6p vd cit theo
., J
dudng thdng chria canh dy chia tdm thdp thdnh hai phdn, mQt phdn chria khu6n
thdp cAn gia c6ng. Chi phi cit khudn th6p ld t6ng chi€u ddi cua c6c duong cit.
- . ^ tdm
,(
Tr0n hinh t va 2,
thdp ld tir gi6c dugc td nhat, khu6n thdp ld hinh vu6ng duoc
tO bing c6c ggch ddm. C6c ndt gach dut ld ciic duong cit uoi t6ng chi phi bing 6.5
don vi.
YOu cAu: Cho bi€t hinh dang t6m thdp vd khudn thep cdn gia c6ng. HEy tim
phuong 6n cit khu6n thep c6 chi phi nho nhdt.

Input: T€p vdn ban BAIIT_C8.INP: Dong dAu ghi s6 N 1: S N S 2000) ld sO dinh
cua tAm thep; N dong ti6p theo, m6i dong ghi hai s0 thuc x va y (-100. *,y.
104), le to4 dQ N dinh cira t6m thep dugc liCt ke theo chidu kim d6ng h6. Dong
ti6p theo ghi sO M (3 S M S 2000) ld sO dinh cria khu6n thdp. M dong ti6p theo,
i.
:
moi dong ghi hai sd thuc x vd y (-10' < x, y < 10") la to4 dQ M dinh cua khu6n

thdp duoc liQt kO theo chiAu kim d6ng h6. C6c s6 t.Cn mQt dong c6ch nhau it nhdt
mQt dAu c6ch.

Output: T€p vdn bin BAI17_CS.OUT ghi chi phi nh6 nh6t tim duoc voi d0 chinh
x6c t6i 4 chfi s6 sau dAu chAm thdp ph6n.
Vf dq:
BAI17-C8. ]NP
4

2I
25
5 3.s
52

BAI].7 C8.OUT
6. s000

4
JJ

34
44
43
8.18. G6c tia laser
Trong mQt bu6i trinh diSn 6nh s6ng, c6 N tia laser duoc chi6u l€n troi nho c6c cldn
,.i
i..
chieu co cong su6t r6t lon vd c6c tia laser ndy c6 th€ di rdt xa. Circ tia laser n[m
tr6n cung mQt mdt phdng thang dring nen ndu hai tia laser kh6ng song song voi
nhau thi s€ c6t nhau. Ban t6 chuc bu6i trinh diSn mu6n nhd ban cho bitit v6i c6c

IA
IT

8.

i*r

B:

ba'

Inl
it)l
grd

gia

'Ou

dar


tia laser dugc chi6u nhu trong kd ho4ch thi hai tia laser ndo cit nhau tai di€m cao
nh6t..
C6c tia laser duoc bi6u di6n bang ba sd nguy€n: Mdt sd lir toa dd x o duoi ddt cua
',4
ngon den chi€u,
hai sO con lai ld toa d0 cira mQt di€m ndo d6 thudc tia laser ndy.
Bi6t rSng kh6ng c6 hai tia laser ndo song song vd cfrng kh6ng c6 tia laser nho
-. dat

-^.,(m[t ddt duoc coi ld duong thdng y:0).
trung voi mdt

Input: T€p vdn b6n BAIl8_C8.INP:
Dong dAu tiOn ghi N ld so tia laser (2 s N s 10000). Tii5p theo ld n dong, m6i do.rg
A
r.t
^
ghi
ba so nguy€n
xi, Zi,ti vdi 1f nghia tia laser thf i di qua hai di0m (xi, 0) vd (z;,

t')(l*,1,

I

i
,

I

t

lr,l

<106;

0
1,2,...,N).

Output: TQp vdn bin BAI18 C8.OUT nhu sau: Trong trudng hqp kh6ng c6 hai
tia laser ndo cit nhau thi ghi duy nh6tmgt s6 -t. XCu t,On tai hai tia laser.a, ntuu
thi dong thir nh6t ghi s6 dQ cao l6n nhAt (duqc ghi v6i dQ chinh x6c b6n chfr's6
sau d6u thdp phan),cua giao di€m cua hai tia laser c6t nhau. Dong thu hai ghi hai
sd nguy€n le thri IU (theo thit t.u trong t€p dt liQu vdo) cira hai tia laser cdt nhau c6
d0 cao lon nhdt d6.
Vi dq:
BAIlB C8.INP

BATlB-C8.OUT

2

-1

-1

-a

A

234

BAIlB C8. INP

BAI18-C8.OUT

4

8.0

-r-24
011
304
44L

13

8.19. Cho N da giitc l6i thoa mdn c6c tfnh ch6t sau: V6i hai da giacbdtki lu6n c6
m6t da gi6c md moi di6m cua n6 nim trong da gi6c kia; cttc.canh cua chfng
khdng c6 di6m chung.
Bdi to6n d'5t ra ld: vdi m6i d,a gi6c i, c6 bao nhiOu d,a gi6c trong N d,a giitc n6i tr€n
,J
bao no (da giac i ndm trong bao nhi6u d,a gi6c)?

Input:

)n

v[n bdn BAIIS_C8.INP: Dong ddu tien ghi s6 tg nhi€n N (3 < N <
i + I ghi th6ng tin vd cta giiic thir i, bao g6m S; la so dinh cua da
t'
gi:lc; Si cdp so nguyon tiOp theo l6n luot ld hodnh d0 vd tung d6 c6c dinh cira da

m

gidc. C6c

0r

output: T€p vdn b6n BAIIg-cS.our

tc

da giilc bao da gi6c i.

TOp

10000). Dong thu
sO

tr6n cung dong c6ch nhau it nh6t mQt d6u c6ch.
gOm

N dong, dong thri i ghi s6 luong

c6c

l5


Vf dg:
BAI19

BAI19-C8. INP

0

4

4 r 1 15 1 15 8 1
493964643
4 3 2 11 2 L1 1 3
3848568

8.20. BQ vdng

C8.OUT

8

)

1

3

1

io thuqt

io thu4t co eicn. Nhd 6o thuat gi6i thieu cho
kh6n gii xem xdt mQt s6 vong th6p d[c 16ng vio nhau tuong chimg kh6ng th6
thrio roi chring ra. Sau d6, nhd io thuflt 1i6n ti6p n5i va th6o c6c vong truoc sg
ng4c nhi€n cira kh6n gii. Nhirng c6i vdng dflc xu6t hiQn c6 v€ nhu tu tu l6ng
qua lin nhau. Cao di6m cira trd 6o thuflt ld di6n vi6n tach rdi t6t ctt c6c vong
BQ vdng Trung Qu6c ld mQt dung cq

I

^uyen
thanh tung chi€c mQt.

Trong bdi to6n ndy, b4n clugc cho mQt t4p hqp nhirng vdng trdn. Hai vong c6t
nhau dugc coi ld lien k6t nOi lOng vdo nhau. Chuong trinh cria ban cin xic dinh
khoing cich t6i da c6 th6 dat duqc bing c6ch k6o hai vdng ndo d6 theo hai hudng
ngugc nhau. Do b4n kh6ng phii ld mQt nhd 6o thuflt n€n c6c vdng vdn con li6n k6t
voi nhau vd gi6 dfnh rdng tht citc6c vong vdn ti6p tgc li nhirng vdng trdn;
V6i nhfrng c6i vong dugc cho nhu hinh I c6 th€ dugc k6o c[ng theo m6 ti tr6n
dugc khodng c6ch t6i da le 856 (hinh 2).

.JEE*

lr

t---ri?--+

[*
t

Input: TQp BAI20_C8.INP ghi s6 N (s6 vong li€n tet voi nhau). M6i dong trong
N iong ,uu,ta Ua # nguy€n mO ti mQt vong. Hai sO tlAu trong ba s6 ndy ld toa dO
A ,t ,- rt! t-z-- 1!t,-1- ^
n6. Chc s6 c6ch nhau it nhdt mQt ddu
t6m vong trdn, s6 thu ba ld b6n kinh cria

I e-,

lci

i

Ph'

c6ch.

vu(

t6

2- Tl


Bi6t rdng so c6 khdn g qu6 500 vong vd tdt cir toq dQ vd brin kinh trong pham
vi I
d6n 1000. Dt lipu vdo bio drim kh6ng c6 vong ndo nim ,.on* uon*"tnil.
n""
nta, b6o dim ring todn bQ ciic vdng ld n6i voi nhau. Khoeing .a.fr tOl Au duoc han
cne la so nguy€n.

Output:
Vi du:

TQp BAI2O_C8.OUT ghi

khoing c6ch t6i da dat duoc.

BAI2O ,C8.IN

BAI2O C8.OUT

856

5

680 4L1 64
812 314 712

ho
Itrc

rzt

ng

ng

CHUYNX OT g. Li THUYET TRO CHOI

tit

9.1. Trd

nh
ng
(et

*Tr€n

:6n

f,J_l 55

191 297 156
569 282 100

su

choi Ldy b6t qu6n co

bdn c6 C qudn co. Hai nguoi choi lAn luot, m6i lAn nguoi choi tt6n lugt s6
l6y rakhoi bdn tu I drin M qudn co. Nguoi thdng ld nguoi t6y duqc qu6n copu6i

cing". vi6t chuong trinh thgc

tro choi ',Ldy bort qu6n cd,, nhung vdi quy
dinh nguoi c6 luot l6y cu6i cung thi thua. chuong trinh nhdp hai so cuong c va
M tu bdn phim (l s c s 104, I s M s c) vd t4o giao di6n tr6n mdn hinh quri trinh
nguoi choi v6i m6y (uu ti€n cho nguoi rli truoc) khi m6y rlp dung thu6t to6n gidnh
thing. Cu6i cung th6ng b6o nguoi thing.

9.2. Tro choi

hiQn

tru din

Tim tfp hgp cdc vi tri p AOi vOi rro chol tru dAn, nriu t4p tru ld:

a) S:{1,3,5,7).
b) S:{ l, 3, 6}

c) S:{ | ,2, 4,8, 16,... } ld 6p
ng
d0
lau

cric

lu} thua cfia 2.

9.3. Trd choi Ghomp! (Bd mi6ng so-co-la)
Cin di chuy6n nh&ng 6 vu6ng trong bing hinir chfr nfrit gO* mxn 6 vu6ng. M6i
ph6p di chuy6n ld ley di mQt 6 vu6ng vit citc 6 vu6ng 0 b€n phai n6
cing c6c 6
w6ng phia ti€n chiing' Hai nguoi chcvi lAn luot di chuy6n, nguoi ndo chon ph6i 6
2. TLcTF{BTQ3.A

T7


(1,

l) thi thua cuQc (6 ndy coi nhu bi nhi6m

doc).

vi

du choi v6i bang 3x8. Nguor

I

A lay di 6 (6, 2) cung c6c 6 b€n phii vd c6c 6 phia tr€n (l6y di mQt hinh chfr nhat
c6 tAt c6 s6u O). Sau d6 nguoi B l6y 6 (2, 3) vd c6c 6 ben phai (lAy di hinh cht
nhflt c6 t6t ca bOn 6). Khi d6 c6c 6 vu6ng con l4i tren b6ng nhu hinh duoi:

(

a) Tim ra m6t phep chuy6n ti€p theo gidnh chiOn thdng cho A.

b) C6 th6 chung minh A c6 thu4t to6n gidnh thing trong bting tong qudt mxn

6

vudng hay kh6ng?

9.4. Tro

choi Ph6p tru

dQng

C6 th6 m0 r6ng thOm lop trd choi tru dAn bing c6ch tao ra t4p tru S phU thuQc vdo

lin di chuy€n truoc

cua COi ttru.

C6 mQt cgc N th6, ngudi choi dAu ti6n c6 thti l6y bao nhi€u the tui;f nhung it nhAt
ld mQt th6 vd kh6ng dugc ldy tAt cd. Sau d6, dtin luqt nguoi thu hai vd hai ngudi
thay nhau tAn lugt choi. M6i nguoi choi kh6ng duoc phdp lAy sO th6 nhi6u hon sO

the md eOi ttru vua l6y.

thf nh6t di chuydn nhu th6 ndo d6 thang ntiu s6 the N :
b) Vdi gi|trindo cua N thi nguoi choi sau th6ng?
a) Nguoi

44?

choi Fibonacci Nim
C6 mQt cgc N the (l < N < 100), nguoi choi dau tien c6 th6 lAy bao nhieu the tui,

9.5. Tro

nhung it nh6t ld mQt the vir kh6ng dugc l6y t6t ca. Hai nguoi choi lAn luot' m5i
nguoi choi c6 the l6y sO tfre nhidu nhAt bing hai lAn sO th€ md dOi thu l6y trong
luot Cli truoc. Lpp trinh tro choi gita nguoi vd m6y, 6p dqng chitln thu4t gidnh
:i,

..:
thang cho m6y, bi€t m6y di truoc.

C,

nl':

9.6. Tro chcpi Porker Nim
Ddy ld trd choi voi c6c cgc ld c6c chdng hQp go. Cfing nhu trd Nim chuAn. ngoai
tru m6t di€u la co th€ gidm kich thuoc cua mdt vdi cgc vd phdp di chuy6n ld c6
th€ girim ho[c t[ng th€m kich thu6c cira mQt v]ri coc bing cdc hQp g5 dd chi6m

l8

9.

2, TLCTHBTQ3.B

rl\l.

do

Hi


i
t

duoc trong cric buoc di chuy6n truoc. Trong hinh v€ duoi ddy ld tro choi o thoi
di€m ba ch6ng hOp g6 c6 kich thuoc \d3,4 vd 6 sau khi hai nguoi choi dd di

i

.-huy€n mQt s6 buoc vd thu dugc mQt s6 hOp (d€ b6n canh h9). B6y gio d6n luot
r;

..r

ddu thu ben trdi (goi ld A). v0y chi6n thuQt cua
choi kh6ng cho phep kdo ddi mdi).

9.7. Tro chcyi

it
Ti

o

A nhu th6 ndo d€ thdng (n6u tro

Lft rua (Turning Turtles)

Tr€n cluong thing nim ngang c6 n con rua dang bo hopc dang nim ngua. M6t
nhep chuydn ld ldt m6t con rua dang bo thdnh nim ngua vd ndu mudn con co th€

iit

m6t con rira khrlc o b€n tr6i n6 (tu bd thenh nim ngua hoic tu nim ngua thdnh
bo). Nguoi choi ndo c6 phdp di chuy6n cuOi cung thi thing.
',J

t chung to rdng tro choi ndy ld Nim n6u m6i con rua dang bo o vi tri n ld mOt
.rrC c6 n qudn.
.i

.'l
:tN€u

'

ry
ol
tg

^t)

lh

r?1

co
rm

a) dung. tim chi€n thuat gidnh thdng cho trang th6i n€u o hinh vd sau:

@@#"ffiw"&ffir"e@n@
9.8. Trd choi Moore's Niml
Co n coc v6i s5 qudn tuong ung ld Xl, X2,..., xn vd qu6 trinh choi nhu trong Nim
nhtmg m6t phep chuy€n la nguoi choi c6 th6 chuy€n so qudn tuj'yjr tu k coc b6t ki
, k Li s5 co cintr cho truoc) vd it nh6t phrii c6 mOt qudn chuy€n di tu m6t cgc ndo
dtr. Tro choi

Nimi voi k : I chinh ld tro choi Nim chu6n voi n coc.

Hd1'ldp trinh tro choi Nimp gifra mriy vd nguoi, cho m6y di truoc.

19


BAI08*C9:INP: m6i dong.cho mQt c6u hinh cria trd choi: dAu dong ld
sO k nguyQn duong sau d6 ld n sd nguy€n duong th€ hien s6 qudn hOn n cqc (1 Sk < n).

Input:

TQp

I

I

output: Tpp BAI08 C9.OUT c6 s6 ddng tuong ring. Dau m6i dong ghi s6 I ho4c
0 the hien m6y c6 th€ dat chii5n thdng ho[c kh6ng chic thing. Ni5u ghi s5 I thi sau
d6 ghi ra n s6 th6 hien si5 qudn con l4i tr€n c6c cgc l, 2,...,'nsau bu6c di thri nh6t

t

cira m6y.

!

9.9: Gi6

tri

I

l

hdrm Sprague-Grundy

Tinh gi6 trihim Sprague-Grundy t4r chc dinh ctra

I

<16

thi sau:

I

a

b
c

d

cl

:

I

'Tt

I
r)

Ir
Input: Tgp BAI09-C9.INP md ta dO thi tr€n theo d4ng
BAIO9 C9. INP
15

440568

SZrO

622'7
713
UJOIY

g L'l'
10 3 4 11 13
LL281,2
1229L4
L3 2 rr 1,4
L4 I9

sau:

(}

G

9.'

Tn

h
hir

vfu
9.1

Chr

chi
qua

z0


Ddng diu ghi so dinh N : 15. ttl6i aong sau: s6 thri nh6t la so rrigu dinh x, s6
thri
hai ld s6 nx d6 ld so luqng c6c dinh y c6 cung tu dinh x t6i dinh y, nx s6 ti€p theo
h sO hi€u c6c dinh y.

output: TQp BAI09_c9.our, g6m N ddng, m6i ddng ghi hai si5 x vd g(x) ruong
rmg h sO hiQu dinh vd gidtrihim Sprague-Grundy cria dinh d6.
9.10. Tim

him sprague-Grundy cho trd choi tru din voi

tQp

tru

Tim hdm Sprague-Grundy cho tro choi tru dan v6i tflp tru sau d6y :
a) S: {.1,3,4}
b) S le tdp cric sti nguydn t5 le.
c) S ld tdp c(rcs6 nguy6n td.
d) S ld tdp citc

sO

.

Fibonacci.

b) S la tdp c6c sO Lucas (tQp s6 Lucas dugc dinh nghia dQ quy: Lr
= Lirr+ L1 (i :1,2,...., 100).

:

I

,

L2:

3, Ltz

9.11. Trd choi At-Most-Haft
Tro choi At-Most-Haft ld tro choi tr€n m6t cgc v6i quy luflt: ph6i chuy,Sn it,nh6t ld
m6t qudn vd nhi€u nh6t ld nria sti qudn trdn cgc (t6t nhien vl tri kt5t thric ld 0 hodc

l)- vict chuong trinh xdy dpg hdm sprague-Grundy v6i tro chcri ndy.
lnput: T€p BAIIl_cg.lNp g6m r0 ddng, m5i dong ghi mQt giri tri cria N (l
s 10000).
output: TQp BAII l_cg.our g6m l0

ddng, m6i dong ld gi6 tri hdm sprague-

Gnrndy cria N tucrng img vdi dong input

9.12. Trd

choi Dim*

Tro choi Dim* ld tro choi tr€n mQt coc chfta n qudn, hai ngucri chsi lAn luot. trrt6i
luqt choi lo4i b6 di c qudnrtr cgc v6i di6u kiQn c ld u6c cira n (k€ c6 I vd n). Tinh
h.'im Sprague-Grundy cria c6c

vi tri trong tro choi ndy v6i n : 20 vd ghi

J<6t qu6

vao tQp BAII2_C9.OUT.

9.13. Tro choi Chin-Ld
cho m6t coc chua n qudn. euy tac chuydn qu6n khoi coc ld: c6 th€ b6t di mOt s6
chin qudn nhung khdng phdi ld todn b6 qudn tr€n coc ho{c c6 th6 b6t di todn b6
quin trdn cgc n6u cgc c6 sO qudn 16.


Chung minh quy n4p c6ng thuc: g(2k)

: k-

I;

g(Zk- l)

:

k voi rngi

k:

0

1'

I

9.14. Tro choi At-Least-Haft
Tro choi chi c6 mQt cgc vdi quy lu4t choi ld phdi di chuy6n it nh6t ld mQt nua
. the tr€n coc. Vi tri k€t thirc duy nhdt ld 0.
Chirng minh (quy npp) gi6 tri him Sprague-Grundy g(x)

:

min{k:

2u

sd

k
a

t *}'

Lru y: Nguoi thu nh6t trong trd choi niy ddnh chi6n thang rat d€ ddng (d6 ld l6y

htit mgi qudn ngay tu ph6p di chuy6n dAu ti€n). Nhrmg viqc tinh hlrm Sprague-

b

mi At-Least-Haft ld mQt trd choi

9

Grundy c6

;iz

nghia phuc vp cho trd choi chinh

,r

I

thdnh phdn.

C

9.15. Trd choi Wythoff

b:

Tr€n bdn co vua kich thuoc 8x8 dat mQt qudn h4u.
Hai ngucri lAn luqt di, m6i lugt di s€ di chuy6n qudn

h4u

.,
a

v

voi s6 budc tuy y theo hudng thdng xu6ng,

j

ngang sang tr6i, ho4c di ch6o xu6ng g6c tr6i-duoi.
Khi con hflu di d6n g6c trfi-duoi thi trd choi k6t thtic

l

.'

(dinh kdt thuc). Vi6t chuong trinh tinh gi6 tri hdm
u;r
Sprague-Grundy cira c6c vi tri trong trd choi ghi vdo
tQp BAI15-C9.OUT theo khu6n d4ng: ghi 8 dong, m6i dong 8 sd.
Dong thri nhAt

lin lust ld chc gi6 tri g(7; 0), g(7; l),...,

g(7

riiii:

,7).

Dong thri nh6t lAn lust ld c6c gi6 tri g(6; 0), g(6; 1),..., g(6,7).

ill

Jl

9.

\t,

r&
Dong cu6i cung lAn lugt ld c6c gi6 tr1 g(0; 0), g(0; 1)'.. ., g(0, 7).

ftr
\ot

9.16.

,,-ht

Tim phdp chuy6n t6i uu tu vi tri ban dAu cua trd choi t6ng ba trd choi sau:

rai

- Tro choi chin-le vdi cgc 18 qudn;

ote

- Trd choi At-Least-Haft vdi cgc l7 qudn;

Ha

- Tro choi Nim chuAntrng,.n. 7 qudn.

22

ngr


9.17. Trd choi Grundy
Tro choi ndy c6 phdp chuy6n hqp lQ ld chia m6t coc thdnh hai coc c6 kich thudc
kh6c nhau. Nguoi ndo c6 phdp chuy6n cu6i cung thi thing.

a) Vi6t chuong trinh tinh gi6 tri hdm Sprague-Grundy cho trd choi ndy v6i mQt
cgc ban ddu c6 kich thudc n qudn (v6i n = 1,2,3, ..., 13).
t

.

'.,(

ry

b) Xdt tro choi Grundy vdi ba cgc ban dAu c6 si5 qudn ld 5, 8 vd 13. Tim c6c phdp

e-

chuy6n t6i uu dAu ti€n n6u c6.

0i

9.18. Tro

(

choi Kayler

C6 13 ki (kegen) trong trd choi bowling sap thdnh mdt hdng, nhung ki thri hai dd
bi ha dO (xem hinh vE).

a)

Chfng to vi tri ndy ld N.
,i

b) Tim phdp chuydn gidnh chi€n thing. Khi d6 ki ndo

9.19. Tro

sE

bi ha?

choi Rims

\{Qt vi tri cira trd choi Rims ld mQt tap

.

l.

htu han chdm trdn tr€n mdt ph6ng c6
thC bi ngdn c6ch boi mQt viri duong
r

a.

ong kin kh6ng cdt nhau. MQt ph6p dr

chuy€n ld vE mQt vong kin di qua mQt
,t
.,1
vdi cham
di€m ndo d6 (it nhdt ld mQt

I rl

diem) nhung kh6ng cht c6c vong dd c6.

,

.).

Hai nguoi choi l6n luot thuc hi€n di chuy€n, nguoi c6 phep chuy6n cu6i cung ld
n-uuoi chi6n th6ng.

a) Chung t6 trd choi ndy ld m6t dpng cria Nim.

b) V6i vi tri cho nhu hinh v€, tim phdp di chuyOn giinh chitin thing n6u c6.

LJ


9.20. Ccr Dawson
C6 hai hdng qudn tdt den vd tring
i.
+(.
r
ddi
diQn nhau, moi hdng c6 n qudn.
c6ch nhau mQt hdng tr6ng (hinh
bdn). MQt qu6n t6t chi c6 the di len
^A tr6ng phia tru'6c hodc buQc
rn6t o
phni bit mQt qudn cia d6i phucrng

tttttttt
& + & + + + + +
JI A A A A A A A

dd dirng o 0 ke chdo b€n tr6i ho6c b6n ph6i cua 6 chria qu6n t6t ndry.
, ,,.i.

a) Vi€t chuong trinh

tim

gia tri hdm Sprague-Grundy cria trd choi Dawson.

b) Hay tim budc chuy6n chi6n thang khi n

:

18.

9.21. Tich Nim
LQp chuong trinh tinh tich

9.22. Tro
r!

Nim cua hai s6 x vir y.

lr

choi lft xu Twins

^1
Cho
ddy n +

t

I

*l

dong xu d6nh s6 tu 0 d€n n, d6ng xu n ngtra, c6c d6ng xu kh6c sAp.

M6t lugt di ld lat dOng xu ngua thdnh sdp vd mQt d6ng xu khdc tuj,f o b€n tr6i

tl
clang sdp thdnh ngira. Xdy dgng hdm Sprague-Grundy cho c6c vi tri cua tro chor

o

nay.

:_

9.23. Tro

"-..

'":

choi l6t xu Ruler

:i

;.
gom

,r
-;. xu, d6nh sdL..tu I, d€n
-).
Cho rnot hdng
n ctOng
n, d6ng
xu n dang ngua, cdn c6c
d6ng xu kh6c thi sAp. MQt luqt di ld lpt d6ng thoi mQt sO dOng xu voi diOu kiQn

, +l
c6c d6ng xu ld liOn ti€p vd cl6ng xu b6n phii nhdt dang ngua bi l6t thdnh s6p. Vi6t
chuong trinh tinh gi6 tri hdm Sprague-Grundy cho c6c vi tri trong tro choi ndy.
l__

choi l6t xu Grunt
x
-l
Cho m6t hdng gdm n +l d6ng
xu, d6nh s6 tu 0 d6n n, d6ng xu n dang ngua, cdn
9.24. Tro

c6c cl6ng xu kh6c.thi sdp. MQt luqt

di ld lat b6n ddng xu c6 vi tri d6i xung qua vi

tri chinh giira cira d6ng xu b€n tr6i nh6t vd d6ng xu b6n phrii
, ,. i.

nhAt.

Viet chuong trinh tinh gi5 tri hdm Sprague-Grundy cho cdc vi tri trong tro choi

nay.
.\A

-+

t

,


9.25. Tro choi Turning Corners
Ban co vu6ng kich thudc nxn dugc chia thdnh c6c 6 vu6ng vd d6nh toa d6 nhu.
=au: o g6c tr€n-phiii c6 toa d0 (0, 0), hodnh dQ tdng dAn il phii qua tr6i, rung d6
ung dAn tu tr€n xu6ng du6i. Tr€n m5i o vu6ng c6 th€ dar mQt d6ng xu (ngri,a ho6c
sip). Hai nguoi choi l6n luqt. MQt luqt di ld chon mQt hinh chir nhdt nh6 trong
ban co c6 g6c phii-du6i ld (x, y) md d6ng xu tai 6 ndy ngria vd ba d6ng xu d ba
goc con l4i cria hinh chfr nh4t nho ndy rip. Sau d6 nguoi choi cAn lat d6ng xu dang
ngua thdnh thdnh rip vd lat ba dOng xu o ba g6c con lai cria hinh cht nhat thdnh
:ruua. Ngudi choi ndo rip dugc d6ng xu cu6i cung thi th6ng cuQc.

i r Ldp.trinh tinh c6c gitt, tri hdm Sprague-Grundy cia c6c vi tri trong trd choi.
: r Ldp trinh cho bi6t trang thdi ban d6u cira bdn co ld N hay p. N€u trang th6i ld
\. hdy tim m6t buoc di gidnh chi6n thing
Input: T€p BAI25_C9.INP chua trang th6i ban dAu cua bdn cd:
Dong dAu ti6n ld sd nguy€n duong n

Tiep theo ld n +

:iin

I

dong the hien bdn co, m6i dong c6 n
d6ng xu up, sO t ttr€ hi€n d6ng xu ngua).

+t

so 0 hodc

I

(so o tne

output: Ghi vdo tQp BAI25_C9.our. Dong diu ghi s6 t .rcu trang th6i ban dAu
:ua bdn cd ld N, ghi so 0 n6u trang th6i ban dAu ld p. N6u ftangthiliban ddu ld N
::i dong thu hai ghi toq d0 (x, y) o g6c ph6i-du6i c0a hinh chir nh6t nh6 trong
:uoc di chi0n thang. Han ch6: n < 21.
)ttc

9.26. Truy tim toi phAm

iQn

ict

ion

Toi pham B l€n tdu tu Hd Noi v€ Hii phong cc tron sr,r truy nd cua c6ng an A.
cong an A c6 th6 lOn tdu nhanh, uat e tai Hai phong. Tai ga Hai Duong, B c6 thO
rudng d6 tAu tho6t. Tuy nhi€n cdng an A cfrng bi€t di€u ndy vd co th€ cfrng xu6ng
tau tai HAi Duong dc truy tim. Sau d6y ld bing luqng giri tri cho c6ng an A trong

ki

ho4ch truy tim tQi ph4m B:

vi

TOi pham B xu6ng ga

COng an

A xu6ng

ga

Hdi Duong

Hii

Hii Duong

r00

-50

Hii Phdng

0

100

Phong

25