VIETBOOK
Trang 1
Olimpic lËp tr×nh
I.1. C¸c bµi to¸n Olimpic
Trong Olimpic Tin häc Mat-Xc¬-va, ng−êi ta ra cho häc sinh phæ th«ng mét sè nhãm bµi to¸n. Sè
c¸c bµi to¸n dao ®éng tõ 5 ®Õn 11 bµi. C¸c bµi to¸n lu«n lu«n cã møc ®iÓm kh¸c nhau, xÕp theo trËt tù dÔ
dÇn vµ khi tÝnh ®iÓm chØ lÊy 3 lêi gi¶i tèt nhÊt. C¸c thÝ sinh ®−îc b¸o tr−íc tÊt c¶ nh÷ng ®iÒu nµy. Nh÷ng bµi
®Çu tiªn cã thÓ lµ kh¸ khã, cßn nh÷ng bµi cuèi cïng mang tÝnh chÊt khÝch lÖ. Kú thi kÐo dµi 4 giê, lêi gi¶i cã
thÓ viÕt trªn bÊt kú ng«n ng÷ nµo. Tr−íc khi gi¶i nhÊt thiÕt ph¶i viÕt thuËt gi¶i b»ng lêi. §iÒu nµy lµm cho
viÖc ®äc ch−¬ng tr×nh dÔ dµng. TÝnh râ rµng cña thuËt to¸n, viÖc tiÕt kiÖm sè c¸c thao t¸c, tÝnh ng¾n gän cña
ch−¬ng tr×nh ®−îc cho thªm ®iÓm, cßn viÖc lËp tr×nh sö dông m¶ng thõa vµ cã lçi bÞ h¹ thÊp ®iÓm.
Trong ph¸t biÓu c¸c bµi to¸n vµ tr×nh bµy thuËt to¸n qui −íc dïng c¸c ký hiÖu sau ®©y: C¸c m¶ng A1,
A2,..An ®−îc ký hiÖu lµ A[1:n] víi A[i] lµ c¸c phÇn tö cña nã. Còng nh− vËy kÝ hiÖu A[1:m,1:n] vµ A[i,j]
cho m¶ng hai chiÒu..v.v...
Sè l−îng c¸c phÇn tö cña m¶ng vµ chØ sè c¸c phÇn tö cña m¶ng lµ c¸c sè tù nhiªn, cßn l¹i lµ c¸c sè
thùc ( nghÜa lµ sè víi dÊu phÈy ®éng), nÕu kh«ng cã −íc ®Þnh nµo kh¸c.
NÕu ë ®Çu bµi nãi r»ng “ Cho m¶ng A[1:n] th× häc sinh cÇn viÕt ch−¬ng tr×nh tù nhËp sè n, t¹o m¶ng
n phÇn tö vµ nhËp gi¸ trÞ cña c¸c phÇn tö nµy. NÕu trong ng«n ng÷ ( VÝ dô ng«n ng÷ Pascal...) kh«ng cã
m¶ng ®éng, th× cÇn chÊp nhËn n<100 vµ lËp m¶ng 100 phÇn tö, nh−ng chØ nhËp gi¸ trÞ cho n phÇn tö cho
tr−íc. Còng nh− thÕ ®èi víi m¶ng 2 chiÒu vµ nhiÒu chiÒu h¬n. Tuy nhiªn thÝ sinh ®−îc phÐp gi¶ thiÕt phÇn
ch−¬ng tr×nh ®−îc viÕt lµ mét phÇn cña ch−¬ng tr×nh bao nã trong ®ã m¶ng ®· ®−îc t¹o lËp vµ c¸c phÇn tö
cña m¶ng ®· ®−îc n¹p tõ tr−íc. Nh−ng thÝ sinh cÇn nãi râ ®iÒu nµy. TÊt c¶ c¸c c©u tr¶ lêi ®Òu ph¶i ®−îc ®−a
ra mµn h×nh hoÆc m¸y in. Mét lÇn n÷a cÇn nhÊn m¹nh r»ng lêi gi¶i ph¶i lµ ch−¬ng tr×nh, kh«ng thÓ thay
ch−¬ng tr×nh b»ng bÊt cø lËp luËn nµo.
Olimpic 80
C¸c thÝ sinh ®−îc giao 11 bµi chia lµm 3 nhãm. C¸c nhãm ®−îc s¾p xÕp theo thø tù dÔ dÇn, trong
mét nhãm c¸c bµi to¸n ®−îc tÝnh ®iÓm nh− nhau. Tõ mçi nhãm lÊy kh«ng qu¸ mét bµi ®Ó tÝnh ®iÓm thi.
80.1.1 . C¸c sè nguyªn tè kh«ng v−ît qu¸ M
H·y in ra tÊt c¶ c¸c sè nguyªn tè kh«ng v−ît qu¸ sè M cho tr−íc.
80.1.2. Ho¸n vÞ :
Cho tr−íc m¶ng A[1:n], chøa c¸c sè kh¸c nhau tõng ®«i mét. H·y in ra toµn thÓ c¸c ho¸n vÞ cña c¸c
sè ®ã.
80.1.3 . N©ng lªn luü thõa nhanh :
N¹p sè thùc A vµ sè tù nhiªn k. H·y tÝnh vµ in ra Ak víi ®iÒu kiÖn sau ®©y: Kh«ng ®−îc sö dông
phÐp tÝnh n©ng lªn luü thõa, k ®ñ lín ®Ó kh«ng thÓ thùc hiÖn k phÐp nh©n.
80.1.4. C¸c phÐp tÝnh sè häc :
Trong biÓu thøc (((( 1 ? 2 ) ? 3 ) ? 4 ) ? 5 ) ? 6 . H·y thay c¸c dÊu ? b»ng mét trong c¸c phÐp tÝnh sè
häc +, -, *, / sao cho kÕt qu¶ tÝnh ®−îc lµ 35( khi chia phÇn d− ®−îc bá ®i)
ChØ cÇn t×m mét lêi gi¶i.
80.2.1 . T×m kiÕm c¸c phÇn tö b»ng nhau :
Cho m¶ng A[1:2,1:15], cã chøa ®óng hai phÇn tö b»ng nhau. H·y in ra chØ sè cña hai phÇn tö ®ã.
VIETBOOK
Trang 2
80.2.2 Tæng b×nh ph−¬ng
Cã thÓ viÕt sè tù nhiªn M cho tr−íc d−íi d¹ng tæng c¸c b×nh ph−¬ng cña hai sè tù nhiªn hay kh«ng ?
H·y viÕt ch−¬ng tr×nh gi¶i bµi to¸n nµy.
80.2.3 C¸c sè kh¸c nhau
Cho tr−íc m¶ng sè A[1:m]. T×m vµ in ra sè c¸c sè kh¸c nhau trong m¶ng nµy.
VÝ dô trong m¶ng 5,7,5 cã hai sè kh¸c nhau ( 5 vµ 7 ).
80.3.1 Sè cã tæng c¸c ch÷ sè cho tr−íc
ViÕt ch−¬ng tr×nh in ra tÊt c¶ c¸c sè ë hÖ c¬ sè 10 cã ba ch÷ sè mµ tæng c¸c ch÷ sè b»ng mét sè tù
nhiªn cho tr−íc.
80.3.2 M + 1 ë hÖ nhÞ ph©n
Sè nguyªn kh«ng ©m M ®−îc cho bëi m¶ng c¸c ch÷ sè nhÞ ph©n lµ a0, a1, a2,...an-1 : M = an-
1.2n-1 +......+ a1.2 + a0
Trong ®ã ai b»ng 0 hoÆc 1 ( i = 0,1,2,...n-1 ) H·y viÕt m¶ng c¸c ch÷ sè nhÞ ph©n cña M+1.
80.3.3 Cùc ®¹i cña c¸c cùc tiÓu :
Trong m¶ng X[1:m,1:n] tÊt c¶ c¸c sè kh¸c nhau. ë mçi dßng t×m mét phÇn tö nhá nhÊt, sau ®ã trong
sè nµy chän ra sè lín nhÊt. H·y in ra chØ sè cña dßng cña m¶ng X chøa sè ®· ®−îc chän.
80.3.4. Ho¸n vÞ 0, 1, 2.
Trong m¶ng X[1:n] mçi phÇn tö b»ng 0, 1 hoÆc 2. Ho¸n vÞ c¸c phÇn tö cña m¶ng, sao cho ®Çu m¶ng chøa
c¸c sè 0, sau ®ã lµ c¸c sè 1 vµ cuèi m¶ng lµ c¸c sè 2 ( kh«ng ®−îc dïng m¶ng phô ).
Olimpic 81
C¸c thÝ sinh ®−îc giao 5 bµi to¸n s¾p xÕp theo thø tù dÔ dÇn. ChØ ®−îc tÝnh ®iÓm 3 bµi.
81.1 Hµm sè :
Hµm sè f(n) víi c¸c sè n nguyªn kh«ng ©m ®−îc x¸c ®Þnh nh− sau :
f(0) = 0 , f(1) = 1 , f(2n)
= f(n) , f(2n+1) = f(n) + f(n+1).
Víi N cho tr−íc x¸c ®Þnh vµ in ra f(N).
§iÒu kiÖn b¾t buéc : N ®ñ lín ®Ó kh«ng thÓ m¶ng gåm N phÇn tö ( hoÆc khai b¸o m¶ng cã chiÒu dµi t¨ng
theo N ).
81.2. CÆp bèn sè .
H·y n¹p sè n vµ lÊp ®Çy m¶ng hai chiÒu kÝch th−íc n2 b»ng c¸c sè 1, 2, 3,.. theo h×nh xo¾n èc (
h×nh vÏ ).
81.3. C¸c sè lËp tõ c¸c ch÷ sè kh¸c nhau:
In ra tÊt c¶ c¸c sè tù nhiªn cã 4 ch÷ sè mµ biÓu diÔn ë hÖ thËp ph©n cña chóng kh«ng cã hai ch÷ sè
nµo gièng nhau.
81.5 Lo¹t c¸c sè kh«ng.
VIETBOOK
Trang 3
Cho m¶ng sè A[1:n] . H·y t×m ®é dµi cña d·y con lín nhÊt gåm c¸c phÇn tö liªn tiÕp toµn sè kh«ng.
Olimpic 82
C¸c thÝ sinh ®−îc giao 6 bµi to¸n theo trËt tù dÔ dÇn. ChØ tÝnh ®iÓm 3 bµi.
82.1 H×nh ch÷ nhËt .
Trªn giÊy kÎ « khæ 100 x 100 «, cã vÏ mét sè h×nh ch÷ nhËt. Mçi h×nh ch÷ nhËt ®−îc t¹o tõ c¸c «
nguyªn vÑn, c¸c h×nh kh¸c nhau kh«ng chång lªn nhau vµ kh«ng tiÕp xóc nhau.
( h×nh 1.2 )
Cho m¶ng kÝch th−íc 100 x 100, trong ®ã phÇn tö A[i,j] = 1 nÕu « [i,j] thuéc mét h×nh ch÷ nhËt nµo
®ã, cßn A[i,j] = 0 trong tr−êng hîp ng−îc l¹i.
H·y viÕt ch−¬ng tr×nh tÝnh vµ in ra sè c¸c h×nh ch÷ nhËt.
82.2 C¸c ph©n sè ®−îc s¾p thø tù
In theo trËt tù t¨ng dÇn tÊt c¶ c¸c ph©n sè tèi gi¶n trong kho¶ng (0, 1) cã c¸c mÉu sè kh«ng v−ît qu¸
7.
82.3 Tæng theo tËp con :
Cho tr−íc m¶ng sè nguyªn A[1: n] vµ sè M . T×m tËp hîp c¸c phÇn tö A[i1], A[i2], ......A[ik]
1<=i1<=i2<=....<=ik<=...<=in
sao cho A[i1] + A[i2] +....+A[ik] = M
Gi¶ thiÕt r»ng tËp hîp nµy tån t¹i.
82.4 Nh÷ng ch÷ sè kh«ng ë cuèi .
Cho tr−íc m¶ng mét chiÒu. H·y viÕt l¹i m¶ng sao cho tÊt c¶ c¸c phÇn tö kh¸c kh«ng n»m ë ®Çu
m¶ng, c¸c phÈn tö b»ng kh«ng ë cuèi m¶ng vµ vÉn gi÷ nguyªn trËt tù tr−íc sau cña c¸c phÇn tö, kh«ng ®−îc
thiÕt lËp mét m¶ng míi
82.5 §iÓm yªn ngùa :
Cho tr−íc m¶ng sè A[1:m,1:n]. Ta gäi mét phÇn tö cña m¶ng nµy lµ ®iÓm yªn ngùa nÕu nã ®ång thêi
lµ phÇn tö nhá nhÊt trªn dßng chøa nã vµ lín nhÊt trªn cét chøa nã.
H·y in sè thø tù cña dßng vµ cét cña mét ®iÓm yªn ngùa nµo ®ã vµ in ra sè kh«ng nÕu kh«ng cã
®iÓm nh− vËy.
82.6 Tõ trong mét v¨n b¶n :
Cho tr−íc hai m¶ng sè nguyªn X[1:n], Y[1:k]. Cã thÓ lùa chän ®−îc hay kh«ng trong m¶ng thø nhÊt
k phÇn tö liÒn nhau
X[i+1], X[i+2],.......X[i+k] , sao cho
X[i+1] = Y[1], X[i+2] = Y[2],......., X[i+k] = Y[k]. ?
H·y viÕt ch−¬ng tr×nh gi¶i bµi to¸n nµy vµ in ra c©u tr¶ lêi Cã hay Kh«ng.
VIETBOOK
Trang 4
Olimpic 83
C¸c thÝ sinh ®−îc giao 5 bµi theo trËt tù dÔ dÇn. ChØ cã 3 bµi ®−îc tÝnh ®iÓm.
83.1. §¶o bit :
Sè nguyªn m ®−îc viÕt trong hÖ c¬ sè 2 theo trËt tù ng−îc l¹i. Sè nhËn ®−îc viÕt trong hÖ thËp ph©n,
®−îc coi lµ gi¸ trÞ cña hµm B(m).
H·y in gi¸ trÞ B(m) víi m=512,513,514,...1023.
ThÝ dô, ba gi¸ trÞ ®Çu tiªn cÇn in lµ :
1; 513; 257;...
83.2. H×nh tam gi¸c vµ ®iÓm :
Cho tr−íc trong hÖ to¹ ®é vu«ng gãc c¸c ®iÓm (X1,Y1), (X2,Y2),(X3,Y3) lµ ®Ønh cña mét tam gi¸c vµ
X,Y lµ to¹ ®é cña mét ®iÓm. H·y x¸c ®Þnh xem ®iÓm ®ã cã n»m trong tam gi¸c hay kh«ng ( bá qua sai sè
cña phÐp tÝnh)
83.3. Mª cung :
Du kh¸ch cã thÓ ra khái mª cung ®−îc hay kh«ng ? NÕu cã thÓ h·y in ®−êng ®i tõ lèi ra ®Õn vÞ trÝ ban
®Çu cña du kh¸ch. Mª cung ®−îc cho bëi m¶ng A kÝch th−íc 40 x 40, trong ®ã :
A[k,m] = 0 , nÕu « [k,m] ®i qua ®−îc (« th«ng)
A[k,m] = 1 , nÕu « [k,m] kh«ng ®i qua ®−îc (« cÊm).
VÞ trÝ ban ®Çu cña du kh¸ch ®−îc cho ë « th«ng [i,j]. Du kh¸ch cã thÓ chuyÓn tõ mét « th«ng nµy ®Õn «
th«ng kh¸c nÕu chóng cã chung c¹nh. Du kh¸ch ®i ra khái mª cung nÕu r¬i vµo « biªn giíi ( tøc lµ « [k,m],
trong ®ã k hoÆc m b»ng 1 hoÆc 40 ).
83.4. C¸i c−a :
Cho tr−íc m¶ng X[1:m]. H·y t×m ®é dµi lín nhÊt cña d·y liªn tiÕp c¸c sè “h×nh c−a” (cã r¨ng
h−íng lªn trªn )
X[p+1] < X[p+2] > X[p+3]<........>X[p+k].
83.5. Rót gän ph©n sè :
Cho tr−íc c¸c sè tù nhiªn m vµ n . H·y t×m c¸c sè m1, n1 nguyªn tè cïng nhau vµ m/n = m1/n1.
Olimpic 84
C¸c thÝ sinh ®−îc giao 7 bµi theo trËt tù dÔ dÇn. ChØ tÝnh ®iÓm 3 bµi.
84.1 NghÞch thÕ.
Gi¶ sö P = (p1,....,pn) lµ mét ho¸n vÞ cña c¸c sè 1,2,...,n. Ng−êi ta gäi d·y T = (t1....tn) lµ b¶ng nghÞch
thÕ cña phÐp ho¸n vÞ P, nÕu ti lµ sè l−îng c¸c phÇn tö cña phÐp ho¸n vÞ P, n»m ë phÝa tr¸i i vµ lín h¬n i. VÝ
dô, ®èi víi phÐp ho¸n vÞ P = (5,9,1,8,2,6,4,7,3) cña c¸c sè 1,2,...,9 th× b¶ng nghÞch thÕ sÏ lµ T =
(2,3,6,4,0,2,2,1,0).
H·y viÕt ch−¬ng tr×nh sao cho theo b¶ng nghÞch thÕ cho tr−íc phôc håi ®−îc ho¸n vÞ ban ®Çu.
84.2 Con ®−êng:
Cho tr−íc c¸c sè tù nhiªn n>=2 vµ m¶ng c¸c sè thùc A[1 : m,1: m,1: n-1]. H·y t×m gi¸ trÞ nhá nhÊt
cña tæng [ R= A]i1,i2,1]+ A[i2,i3,2] + ...... + A[in-1,in,in-1] víi c¸c bé sè nguyªn tè cã thÓ cã 1<= i1,
i2.....in<=m.
VIETBOOK
Trang 5
Chó ý : Gi¸ trÞ c¸c sè m, n kho¶ng vµi chôc, v× thÕ kh«ng chÊp nhËn lêi gi¶i víi sè thao t¸c mn
84.3. Nh÷ng sè hoµn thiÖn.
Sè tù nhiªn ®−îc gäi lµ hoµn thiÖn, nÕu nã b»ng tæng tÊt c¶ c¸c −íc sè cña nã, kÓ c¶ 1. H·y in tÊt c¶
c¸c sè hoµn thiÖn nhá h¬n sè N cho tr−íc.
84.4 Chu k× cña ph©n sè :
N¹p c¸c sè tù nhiªn m vµ n råi in chu k× cña ph©n sè m/n.
VÝ dô : ®èi víi ph©n sè 1/7 sÏ cã chu k× ( 142857 ). NÕu ph©n sè h÷u h¹n th× chu k× b»ng 0.
84.5 Trén c¸c m¶ng :
Cho tr−íc hai sè m, n vµ hai m¶ng ®· ®−îc s¾p A[1]<=A[2]<=.....<=A[m] ;
B[1]<=B[2]<=.....<=B[n]. H·y trén hai m¶ng trªn ®Ó cã m¶ng còng ®−îc s¾p thø tù C[1]<=C[2]<=....
<=C[m+n].
ChØ dÉn : Chó ý ®Õn sè phÐp tÝnh cña ch−¬ng tr×nh khi m vµ n kh¸ lín.
84.6 LÞch :
Cho tr−íc 3 sè A, B, C biÓu thÞ ngµy, th¸ng, n¨m. H·y t×m sè thø tù N cña ngµy trong n¨m tÝnh tõ
ngµy ®Çu cña n¨m Êy.
ChØ dÉn : N¨m nhuËn lµ n¨m chia hÕt cho 400 vµ nh÷ng n¨m chia hÕt cho 4 nh−ng kh«ng chia hÕt
cho 100.
84.7 . Nh÷ng h×nh vu«ng :
Cho tr−íc m¶ng A[1:m,1:n] mçi phÇn tö cña nã b»ng 0, 1,5 hoÆc 11. H·y tÝnh sè l−îng c¸c bé bèn
A[i,j], A[i+1,j], A[i,j+1], A[i+1,j+1] trong ®ã c¸c phÇn tö ®Òu kh¸c nhau.
Olimpic 85
C¸c thÝ sinh ®−îc giao 7 bµi, theo trËt tù dÔ dÇn. ChØ tÝnh vµo kÕt qu¶ 3 bµi.
85.1 D¹ng tæng :
In tÊt c¶ c¸c c¸ch viÕt sè tù nhiªn N d−íi d¹ng tæng c¸c sè tù nhiªn. ViÖc ®æi chç c¸c sè h¹ng kh«ng
®−îc coi lµ mét c¸ch míi.
85.2. C¸c phÇn tö b»ng nhau :
Cho tr−íc m¶ng sè nguyªn A[1:m, 1:n]. Mçi dßng cña m¶ng ®−îc xÕp theo thø tù t¨ng dÇn, nghÜa lµ
A[i,1] <= A[i,2] .... víi tÊt c¶ c¸c
i = 1,2,3,....,m.
H·y t×m vµ in sè cã mÆt ë tÊt c¶ c¸c dßng vµ in ra " Kh«ng" nÕu sè nh− vËy kh«ng cã.
85.3. Sè kh«ng thÓ t¸ch ®−îc .
Cho tr−íc m¶ng sè tù nhiªn P[1:n]. H·y t×m sè tù nhiªn nhá nhÊt kh«ng thÓ viÕt d−íi d¹ng tæng c¸c
phÇn tö thuéc m¶ng P. Tæng cã thÓ chØ gåm mét sè h¹ng, nh−ng mçi phÇn tö cña m¶ng chØ ®−îc tham gia
vµo ®ã mét lÇn.
85.4. Tø diÖn.
Trªn c¸c mÆt cña hai tø diÖn ®Òu b»ng nhau M vµ N cã viÕt c¸c sè M1, M2, M3, M4 vµ N1, N2, N3, N4
theo trËt tù ®· chØ ra trªn h×nh 1.3
h×nh 1.3