SGK BT Chuyên Tin Quyển 1 [PDF]

Zitiervorschau

HO

ffi

Ho Si DAM (Ch0 bi6n) DO DUC DONG - LE MINH HOANG

. NGUYEN THANH HUNG

TAI IIEU CHUYTN TIN HOC .rl

I

H BAt TAPa

OUYEN

1

(Tdi bdn tdn th* nhiit)

runA

xuAr

eAN

ctAo ouc vtEt

ruRnt

Lor NoI uAu lieu chuyAn Tin hoc - Bdi tQp Quydn 1,2, 3 duoc viet kdm vdi bO C6c t6c gih Tdi liQu chuyAn Tin ioc - Quydn 1,2,3 tuong tnrg dd du-o.c xuAt ban'

BQ sdch Tdi

chuyOn' tham gia biOn soan bO s6ch ld nhtrng thdy gi6o dd vh dang d4y o c6c trudng gi6b vi6n ldp chon hoac tham gra c6c kh6-a bdi dudng thi tin hoc qudc tq bdi dudng mudn tin cho cilc trUong chuy0n theo cfruong trinh ctra BO Gi6o duc vh Dho tao, mong vuc linh thu6c tuong xAy dtpg duo. c c6c tai tieu c6 tinh h0 thong phqc vU t6t c^c ddi chuy€n tin hoc. nhau' gdm hai C6c cu6n Tdi lidu chuyAn Tin hoc ' Bdi tQp ddu c6 cau tnic nhu

phAn:

! Phdn I - Bii t4p bao gdm tat chc6c bdi mp trong nhfrng chuyen dd ciia sSchTdi d€ ddn hAu chuyAn Tin hoc firon' rmg vd cr4c bdi mp bd sung, duoc s6p xep tir kh6,.til don gi6n ddn Phfc taP. gifp ban Phdn II - Hu6ng dan giii bii tap c6 thd ld nhfrng huong d6n chi tidt dd hidu v)r tim doc tim duo. c ldi gi6i hoac chi li doan chuong trinh chfnh girip ban doc Ddi v6i m6t sd bdi tAp duo. c ldi giii hoac chuong trinh ho)rn chinh dd tham kh6o. thi c6 thd chi ld ddp 6n hay huong dAn ngan ggn' Hai bQ s6ch Tdi tiQu chuyan Tin hoc vit Tdi liau chuyan Tin hoc - Bdi ttfrp t'ao chuy6n rhinh h0 th6ng tdi liOu kh6 hodn chinh theo dinh huong Chuong trinh c6c vdi b6 dd chuyen rin hoc da duo. c 86 Gi6o duc vh Ddo tao ban hdnh' Do vay cung 'sdch Tdi liQu chuyAn Tin hoc,b6 s6ch Tdi liAu chuyAn Tin hoc ' Bdi tqp sE ld tdi ca li€u thidt thuc phuc vu cho gi6o viOn, hoc sinh cdc trudng chuy0n, l6p chon tham Trung hoc phdlhong vb Trung hoc co s&. Ngodi ra, b0 s6ch cdn lh thi lieu gia kh6o bd ich cho viec t4p huan sinh vien c6c trudng Dai hoc, Cao ding tham vi€n Qudc td' c6c ki thi olympic Tin hoc Sinh vion Todn qudc vd Ki thi lap trinh Luu y khi srt dqng bQ sdch: C6c bdi tap trong b6 siich ndy du-o.c d6nh so nhu trong theo' s6ch li thuydt; c6c bdi tap bd sung drro. c dd 6 muc riOng vd dr4nh sd tidp b0 Mac dD c6c t6c gia vd Ban biOn tap da cd gang hohn thien nhmg chdLc chan dd g6p d6ng s6ch cbn nhidu thieu s6t, cdc tdc giA mong nhAn duoc nhidu f kiea g6p f 'xin gui vri: s6ch sO hohn thiOn hon, phuc vu ban doc du-o.c hiOu qui hon. C6c

BanTodn-Tin, COng ry cd phdn Dich vu xud't bdn Gido duc Hd NOiNhd xudt bdnGido ducVi€t Nam, l87B,Giringv6, Hd Noi' CAc tilc giir

P] 1.

t.

a

,rs

t.:

1.,

Bai t?p cHuytN DE 1. THU4T roAN va, pnAN ricn THUAT roAn Phdn t{ch thdi gian thttc hi€n cita d6qn chucng trinh 6 cdc bdi't* 1.1 d€n 1.9. 1.1.

for i::1 to n do if i mod 2:0 then c:=c+l; for 1:=1 to n do if, i nrod 2:0 then c1::c1+1 else c2:=c2+I; for i::1 9o n do if i mod 2:0 then for ir=1 to n do ci=c-f1

a.

1.5.

while 1>0 do begin _ i . =i .l .=.1 + i. end; 1

l:6. ri r. -v, -n .

repeat, i

.

=i +T L

'

lf

.

if i- mod 3:0 then d:=d + i; until i>n;

,for i-::1 to n-1 do for j:=i+l- to n do d:=d+1; 1.8.

d: :0;.

l

.

for i::1 to n-2 do for j:=i+1 to n-1 do for k': j +1 to n do d::d+1; 1.9.

while n>0

do

begin

n::n div 2; .l . =.1+1

. J

end,.

1.10. cho mQt ddy s6 g6m r sr5 nguy€n duong, xdc dfnh xem c6 t6n t4i mQt d6y con li€n titip c6 t6ng bing k hay kh6ng? a) Dua ra thuat to6n c6 thoi gian thgc hiQn O(nt). b) Dua ra thuet to6n c6 thcri gian thpb hiQn O(n'). c) Dua ra thuet to6n c6 thcrigian thqc hiQn O(n).

cnuvtx on 2. clcrrnx rHUc co BAN 2.1.

nguyen kh6ng cho s li mot x6u chi g6m hai ki tu'0' hopc'1' m6 tA mQt s6 a- O ftQ co s6 Z, hay chuy0nrsO d6 sang hQ co sO t0 (d0 ddi xiu s kh6ng vuqt qu6 200).

Vi

dg:

101011002: ACro 1010 101 1 I 10000010010001

2.2.

Cho

sO

rz:

ABCL23

rc

nguy6n ducrng N (N < 10).

a) Ph0n tich N thdnh thira s6 nguy6n t6'

b) DOm sti u6c cria N. c) Tinh t6ng c6c udc cira N' tra tinh nguY6n to 2.3. Dua ra nhirng sd nho hon ho{c bing 106 md c6ch'ki,5m cfra Fermat bi sai. t6 trong doan [t, R]. 2.4. Sir dung sdng s6 nguyen t6 liet k6 c6c s6 nguyen gqi ld sO 'Agp n6u N thoi 2.5. \guoi ta dinh nghTa m6t s6 nguyQn ducrng N dugc ian *Ot trong hai dt€ukiQn sau:

N bing 9; Gqi (1g h ti5ng c6c chfi s6 ctra Nthi (M) cflng ld sO dqp'. N co phii ld s6 dqp Cho s6 nguy6n duong N (N < 10'oo), hay kigm tri xem

-

kh6ng?

Dtng

(sign: I sO

l6n bing xdu ki tU vd th6rn th6ng tin i16u d€ xu li s6 lcrn le s6 thOng dm, sign: -l ni5u sO l6n ld sO am)

cSch biOu di6n s6 nguy€n ni5u

nguy€n lon c6 dAu nhu sau:

tlpe bigNum = record sign: longint; num: string; end; *ay dgng c6c him xir U s6 nguy€n 16n c6 ddu' phan Dirng c6ch bi6u di6n s6 nguyen lon bing ming (m6i

iay 2.7.

mQt nhom c6c chfi s6).

a) Hdy,xdy dgng c6c hirm xu

li

s6 nguy€n l6n'

tt

cria ming ld

2.8.

b) st'dung hdm nhan s6 nguy€n ldn vdi s6 nh6 dii tintr M v6i TirnKchfi's6 cu6i cung ciaArf (0=r, then exit; e

I

L

+

end,'

I

I

=t- i m 1i

=chiadoi (i, x)

temp:=x*p-sum1 [i,p] - x.* (n-p) fsum2 [irp+1]; p:=chiadol (j, x) ; temp:-temp + x*p-suml't j,pl - x* (n-p) +sum2 [j,p+l] ;

i l.

;

r20

k:=aIi, (1+r) shr 1]; I I .

.

-t

f) i:r

;

repeat

while (a Ii,1i] k) do dec(jj); if i-ialjl then trao(alil,aljl

*. -n

.

for i-::1 to n-l- do for j:=1+1 to n do begin 1nc (m) ;

w[m]::aIi].+aljl; 4,22

);

idIm, 1] ::r;

1dIm, 2l :=l ;

end;

qs(1,m); dem: =0 ;

for p::1 to n do begin s::a[p] ,' s::s*3; for j ::1 to n d,o

begin

for k::i downto 1 do if (w Ik] g ^l

/a'rf nrrf \ . \ UU UlJU L / ,

3.20. Nhqn xdt lt Ddy d sau til sau phAn c6 dg ddi nho hon hoic bdng m.

tt

thri m +

|

s€

di vdo chu ki, chu ki

Mgc ti6u le liet k€ c6c gi6 tri d[.] kh6c nhau vir s6 Dn xuat hien cua m6i gia tri. Vi du, hai dopn'dQ ddi l; b6n do4n dq ddi 2;ba doqndo ddi a;.... Nhqn xdt 2: Chi cdn giir lai ba dopn dq dai I mi kh6ng 6nh huong t6i sd tam gi6c, nhu v4y n6u n> 4m thi r:: 4m + | (m+ l do4n dAu ti€n dugc giit,3m do4n titip theo cfrng giir, cdn l4i bo t6t, chu ki chi cho lqp 3 lAh h du). a

EQ phuc t4p: O(n').

3.21. KhAo s6t tim ra chu ki cua todn bQ ddy, tu d6 tinh dugc chu ki cho do4n u. v.

r23

3.22. Tgp sii

vi s6 n c6 toi 20 chfi s6, do d6 phdi luu trfr bing x6u ki tu. LiQt k€ tAt ctt c6c s6 nhan dugc bdng c6ch thir tit citciic cdch.xod mQt hodc m6t vdi chir sO lien

v

(nhung khong xo6 hdt tht chc6c chfi s6 cua n). Lgcbo c6c s6 khong chia htlt cho 3, viQc kii5m fia c6 chia h6t cho 3 kh6ng thuc hi0n don gi6n bing cSch ki€m tra t6ng c6c chfi s6 c6 chia hct cho 3 hay kh6ng. Sip x6p c6c s6 tdng dAn, dE ddng d6mdugc sO lugng s6 kh6c nhau. titSp cua n

Mo r6ng: Thay aol cieu ki€n "xod mQt ho4c m6t vdi chir s6 li€n ti€p cua n (nhung khdng xo6 h€t tdt. cit c6c chf s6 cua n)" thdnh "xo6 mQt hodc m6t vdi chir s6 cian (nhung kh6ng xo6 h6t tht cit c6c chfi s6 ctra n),'. Bdi to6n mo rong ndy kh6 hon bdi to6n gdc trong vidc liQt kc t6t c6 c6c so nnan dugc, cdn vi0c ki€m tra s6 chia hct cho 3 vd d6m s6 tuqng so kh6c nhau kh6ng thay d6i. oe tigt k€ tat cit chc so nh4n dugc, thwc hiQn bing c6ch liQt ke tdt ctr chc ddy nhi phdn d0 dai / (trong d6 / ld s6 hgng chir s6 cia n). na6i day nhf ph6n tuong ring t4o duoc m6t s5, ki tu thri i cua d6y nhi phdn bing 1 thi cht so ttrir i cta n duo. c giir lai, bing 0 n6u bi xo6 di.

I

I

el

3.23.

Dulng thing

P:

Chia n ducrng thang thdrnh hai loai:

vi

1: Circ ducrng thing c6 dqng Ax + Q:0 (B:0), chon dugc m6t ducrng thing trong tAp ndy. . Loai 2: Cdc duong thing c6 dang Ax + By C 0 (B + 0), sip x6p c6c drri'rrir rhing theo h€ s6 g6c dc acm so lugng gi6 trikh6c nhau, s5 lugng girl tri khdc nhau chinh ld s6 tuqng ouurig Lirarrg iii;o. c chun irong r6p niy

'Logi

t

:

l

br

D6 phuc tap thuqt totn: O(nlogn). 3.24. Hinh chir

nhit b6n miu

progran Col_orRect.s; const InputFile : ,, i OutputFile = " ; maxxy : 200;, tl4)e Tl,ist. = record p, c: array[1..maxxy * 2 + 1] of Integer; num: Integer; end,'

var f: array[-maxxy..maxxy] of TLrst; n : I nteger,' res : Cardinal; 124

I

I

I

Ec En

E r9 N6

I

procedure Enter; var f: TextFile; v. A.

Tnf aaar.. | f IrUgVg!

begin AssignFile (f, InputFile) ; Reset(f)

begin

Ii lt

Read

li.

lv ln

I

;

try for x :: -maxxy to maxxy do 1[x].num := Readln (f, n) ; for i := 1 to n do

n

)n

|

i: Integer;

0;

(f, x) ; l- [x] do

with

begin Inc (num)

;

Readln(f, pInum], cInum] ) ; c [num] := l- shL (c Inum] - 1) ;

end; end;

finally

CloseFile ( f)

end;

; ?

end;

g p

fi

procedure Solve,' var count: arraytZ0000..%11111 or L,, egier; mark: array[-maxxy .. maxxy] of Byte; i lz i. Tnl- aaar. lr,J.trruvYvr, rr: I rra. . Tni6^6r. rrr uvYvr /

begin rae

.=

n'

for i :: -maxxy to maxxy

do

begin

E i I I f-ha r \!r,q!l:/ lmarV

Qi zoAf

lmarlz\

|

n\ vt

with I [i] do for j :: 1 to num do marktptjll for k :- i + 1 to maxxy do

t

:= ctjl;

begin

FillChar (count, SizeOf (count) , with llki do forj:=ltonumdo '

0) ;

begin

value ::

c [l I or mark tp tf I 1 ; (count lnc lvaluel ) ; Inc (res, count [%1111 xor Value] ) ; end; 'end; end;

125

end,'

procedure PrintResult,. var f : TextFil-e; begin AssignFile (f, OutputFile) ; -Rewrite (f)

try

r^l'i vvrrus+^ /€ (r,

r9D,/ -^^\

frnally

I

tACAts

1 t6

lfv

D6

;

XtI

.

/

| i I .

CT

\r/,

end;

4.1

end,'

qu)

begin Enter,'

the

Sol-ve,'

end.

t.

v 3.25. PhAn tfr chung

r

AA

Tt

m6i phAn tu trong m6i diy tpo ra bQ g6m hai thdnh phAn: gid tri phAn tir vd chi s6 day, nhdn duoc n bQ. SAp x6p c6c bQ ting ,l , : ddn theo gi6 tri phdn tir,-n€u gi6 tri phdn tu b[ng nhau thi sap x6p theo chi sd day (chi phi O(nlogru)). DuyQt day dd sip x6p, trong m6i vung gi6 tri bing nhau ki6m so6t xem c6.dtr ft chi sO kh6c nhau khdng, n6u c6 thi d6 li gi6 tri cAn tim (chi phi O(,r)). DQ phuc t4p thuQt tohn: O(nlogn).

Goi

la tOng

Trong vi du

sO phAn

tu.

P

v

b,

l:

, Dd,y I g6m 3 sO t 23,t4o ra 3 b0 (7,1), (2,1), (3,1). r Ddy 2 g6m + s6 q A

l2

-7,t4o ra 4bQ (4,2), (3,2), (2,2), (-1,2).

. ^! Sdp x€p c6c bQ: el,2), (l,l), ,

DuyQt dayda

(2.11. (2.21, (3.1). (3"2), (4,2).

sip x6p, wng gi6 tri2 c6 dit2 chi sO kh6c nhau, gi6tri

cAn

td2.

tl d6n 2;

function tj-nhThoician (t1, L2:strlng) :longint; var p1, p2 :longint; begin

p1:= ( (ord(t1t1l)-48)*10 + .(ord(t1 t2l)-48)) * 50 * +((ord(t1t3l)-48)*10 + (ord(tlt4l)-48)) * + ( (ord(L1[5])-48)*10 + (ord(tlt5l)-48) );

60

( (ord (L2l7l )-48)*10 + (ord(E2l2l )-481 ; * 60 *

60

t26

",

P

v

b

3.26.Xdy dpng hdm tinh thoi gian tir thoi di6m

p2::

tim

60

+ +

exit

((ord (L2[3] )-48)*10 + (ord(t2 t4l)-48) ) * ((ord (t2l5l )-48)*10 + (ord(t2 [5])-48) );

60

(p2 -p1 ) ;

end; D6nh s6 thir tU c6c s6 diQn thopi tuong ring tu --" ',.\ Xu li l6n 'luot tung cuQc ggi.

I

d6n n dd d6

quin li;

Chuy6n dC 4 4.1. Dqc danh sfch hoc sinh vdo m6ng dsHSfl,nlof string. Dung m6 hinh dQ quy dii sinh tAt cir, cdc t6 hqp ch\p k cua n, v6i m5i tO hqp khi ghi ra thi ghi theo danh s6ch hgc sinh (xem thir tuc ghi nghiQm o chucrng trinh duoi ddy).

const MAX =20; tl1)e vector :arrayt0. .MAXlof longrnt,' var x :vector; n

lz

.lnnainl-

.

dsHS :array[1.

procedure

.MAX]

GhrNghiem

var i :Iongint;

of st.ring; (x:vector) ;

begin

for i:=1 to k do write

wri teln; end;

(dsHS

[x[i]1, ' ');

procedure ToHop (r: longint) ; var I : Iongint; begin for I := xli .]. 1+1 to n-k+i do begin xIi] := j; if i=k then GhiNghiem(x) else Ioflop(1+1);

r

end; end;

procedure nhapDl;

var i :longint;

begin

write ('Nhap n, k:') ,' readl-n (n' k) ; for i::1 to n do readln(dsHS[i]); end,' '

BEGIN nhapDL,'

xIO]::0; ToHop(1);

END.

121

4.2. Dung m6 hinh dE quy d6 sinh tat cit ctrinh hqp r[p chap chinh ld c6c ddy nhf phdn dQ ddi n cAn het kC.

2

cua

n phAn tu

4.3. Gqi ru ld d6 ddi cua xdu s, dirng m6 hinh dq quy d6 sinh t6t c6 chinh hgp kh6ng lap chip t (v6i k n) ctta n phAn tu chinh ld c6c ho6n vi d0 ddi n. Tucrng tu nhu bei 4.l, khi ghi tung ho6n vi thi ghi ra ki tu tucrng ung.

:

4.4.r{hai

toin cuc s (ki6u xdu) du,o.c khcri tao g6m n d6u c6ch; sria d6i mQt chrit trong m6 hinh d€ quy sinh tdt cit chinh hqp lip chQp 2 cin n phdn bii5n

nhu doan chucrng trinh dudi day.

procedure l1etKe (i: longint)

var c: char,.

:hi kh

-1.:

ng '^b

du

tin

sa bi(

;

bi(

begin

if i>n then begin writef n (s) ; exit,.end.; for c i='A' to ,B, do if s Ii-1]+s Ii],BB/ then begin q I i I . =n

:h

tll' It

.

l-ietKe (r+1); end,'

end; 4.5. Dung m6 hinh dq quy d6 sinh tat cit chinh hqp lap chQp k cria n phdn tir, v6i m6i chinh hqp l?p chQp k c'J,a n phAn ttr (tuclng ring ld m6t cdch chia n phdn tir thinh t nh6m). Ti€n hdnh ki6m tra c6 ld c6ch chia rhdnh t nh6m md c6c nh6m c6 t6ng bing nhau hay kh6ng? Hdm ki6m tra dudi ddy ki€m tra m6t m5i chinh hqp lap chdp k cta n phAn tu (luu trft trong miing x) c6 fa c6ch chia thdnh t nh6m md cdc nh6m c6 t6ng bing nhau hay khdng?

function laKnhom (x : mang) : booJ_ean,. var tong[1. .MAXK]of longint; i:longlnt,.

begin

L D

cl

'l

nl

N

f i-f lchar (tong, sizeof (tong) , O ) for i::1 to n do tongtxtlll::t.ongtxtill+a[1]; for 1::2 to k do if tongIi]tong[1] then exit (fal-se) ; exit (t.rue)

4

end,'

T

,.

Si

p

,'

4.6. Gpi n ld dQ ddi cria xdu s, dung m6 hinh dE quy d6 sinh t6t cit c6c xdu nhf phdn dQ ddi r (chinh hqp lbp chdp 2 cta n). yoi mQt x6u nhi ph6n dQ dii n, ki tp thri i bing n6u ki tu thri I ctra xdu s duoc gifr lai, ngugc lpi ki tlr thri i

'l'

bing '0' ndu ki tu thf i cua xdu s bf xo6 di. Nhu v0y, {n0t x6u nhi phdn tuong tng voi mot xhi con cia x6u J. Tuy nhi€n, c6c xdu con ndy co the xuat hiqn

n

c

U

S

t

128

nhi€u lAn. Do d6 luu tht cit c6c xdu con (c6 2n xdu con), sip x6p c6c x6u theo thu tu tu di6n, lo4i bo trung lbp, loai bo xdu r6ng d6 nhan dugc cdc xAu cotr kh6c nhau cria S.

4.7.Truoc tien x6y clqlng rnQt hdm ki€m tra rn6t xau co phai ld mot bi€u thuc ngo{c dtng hay kh6ng? c6ch ki6m tra nhu sau: Di tu dau x6u v6 cn6i rau, duy tri mQt bi6n d6m s6 lucrng d6u mo ngodc tru di so luong d6u d6ng ngodc tinh tu tr6i sang ph6i d$n vi tri hiQn t4i (ban ddu dugc khoi t4o bing 0), n6u gap ki tu'(' thi tang birln d6rn, cdn n6u gap ki tu ')' thi giim bi6n dern. MQt bi6u thirc ngopc dung n6u bitin d€m tpi moi vi tri d€u kh6ng 6m vd cu6i ctrng bi€n ddm bing 0.

I

function bieuThucNgoacDung var i, dem :Iongint;

(s : string) :boofean,'

begin dem: =0;

for 1::1 to length(s) if sIi1:'('then . else begin

do inc(dem)

dec (dem) ; if dem0 then begin if btil:1 then begin inc (sl-)

;

for j:=i+1 to n do begin if " (a Ij, 1]0) then

dec (b

end; end;

if btil=2 then begin inc (sl,2) for j:=i+1 to n, do begin if (a[j,I]0) if (alj,1l0)

tj

I);

,'

then dec(btjl ) ; then dec(btjl ) ;

end; end,'

end; wri f cl n /c el |) \Y t- eL

end,'

: '

BEGIN

' assign(f, fi); rese!(f); . assign (9, fo) ,' rewrite (g) ; docdl; xuI

i;

close (f) ; close (g) ; END.

ltr.':

{,N' tim K l6n nh6t kh6ng vugt qud M mdK ld u6c cira N, M_K '' , ti€P tPc Phdn tich Phdn s6 -ph6ntichl4=L*M-K t/ N I N 5 3 2l l VIOU. "6-=-f-=-+-. 6 6 2 3 4.25.VOiphAn sd

,

t39

,

I

,l

Tuy nhi€n, thuat toan trOn s6 kh6ng dring v6i truong hqp thudt to6n tr€n

thi

4

=!*1*1*1. \\\\\

n€u ldm theo

C6 th€ cai ti6n thu6t to6n bing c6ch,

tru6c khi t6ch nhdn cri tir vd m5u v6i m6t

vlou, "

1,

s6.

4853111 _=_-_+_=_+_+_. 5 l0 10 l0 2 5 r0'

4.26.

const max:.1

000,.

TlrTD t .

f i

=rPT fn.=tDT

alll].r

L

'

var n/ start, cur, k : longrnt; v :array[1..max] of boolean; s : st.ring; .f ,g :text

1.

+ l-

function nhan (s: strinq,. i: Iong::.: var ;, nho, tich: longrnt; t : string;

: =-_:::_;,.

Lr

'

begin

.

nho:=0,'t:="; for j::length (s) downto 1 do tich:= (ord (s Ij I )-48) *i+nho,. nho::tlch div 1O; t ::char (tieh mod' 10+48) +t;

V

I' beg.i-o

4.

end;

while nho>O do begin t::char ( (nho mod 10) +48) +t; nho::nho drv 10;

T

end,' nhan : =t,. end,'

(t

4,

+

begin

assign(f , f i) ,. reset (f ) ; assign (9, fo) ; rewrite (g) while not seekeof(f) do begin

\,(

+

,.

read (f, N) ;

for start:= 2 to 3 do begin ( v, si zeof (v) , f al-se f lllchar l N) and v[cur-N] then begin

v Lcur-Nl :=taISe,'

end;

ifcur:N

then break;

end,'

for k:=2 to max do if vIk] then s:=nhan(s,k) writeln (9, s),'

,'

end;

close (f) ; close (g)

;

end.

4.27.Tn ,l/, tim cdch bi6n d6i ve + Chia 2, n6uN chin;

1 dua tr€n hai thao t6c:

+ Nhdn 3 r6i cong l, nOu N le.

' ' bi€n ',' d6i nhdn duoc bi€u thuc cdn tim. Ldt nguoc c6ch ,

Vi dg: 6 -+ 3 -+ l0 -+ 5 -+

16

-+ 8 -+ 4 -+2

+ l, bi€u thfrc cAn tirn ld

1*2*2*2*213|€213+2.

4.28, Ba6'c 1: Tao ra ddy s5 FIB g6m c6c sO kh6ng vugt qu6 N.

Btroc'2: LAp l4i buoc 2. I va2.2 Baoc 2.1:TlmsO Btro'c'

2.

nn;4

Sau

ciru.t6n khi,A/:0.

l6n nhAt nho hcrn N.

2: Tru N di FIB[t].

ThuBt to6n trOn cfrng ld cdch phdn tich N thdrnh c6c s6 FIB d6i m6t kh6c nhau (bdi 2. r l).

4.29. Tuang tU bdi to6n lpp lich giAm thi6u tr6 han ta c6 hai nhdn xdt: -^ vi6c x6p lich cho c6c c6ng viQc hohn thdnh dirng hpn, + Chi quan tdm d6n cdn c6c c0ng viec bi tr6 h4n c6 th€ thgc hiQn theo trlnh tU bAt ki.

.'

; k, c6ng viQc (md cd k c6ng vi€c ndy d6u c6 th0 thuc hi9n + Gia suTs ld t6p g6m cho d,,

o:

(h, i2,..., itr) ld mQt ho6n vi cria cic c6ng vi€c trongT's sao di,3 ...= dir thi thu ty o' ld thu tU dO hoin thdnh dring hpn dugc ci ft

dring h4n) vd = cdng vi€c. .

'.,1 Su dgng chi€ri luoc tham lam, ta xdy dqng tAp c6ng vi6c 7s theo ttrng bu6c, ban dAuTs : A.Him chgn dugc xdy dqng nhu sau: t4i m5i buoc ta s€ chgn

141

.

c6ng viQc jobimd c6 ti€n c6ng lcrn nh6t trong sd c6c c6ng viQc con lai cho vdo t4p

I

7s. Ntiu sau khi k6t n4p job7, c6c c6ng vi6c trong tQpTs ddu c6 ttrtj thr,rc hiQn dirng hpn thi cO Ointr viQc k€t n1p jobivdo tQp7s, nr5u kh6ng thi kh6ng k6t napjobi.

4.30. Bei to6n ndy gi6ng bei 2.8, tuy nhi6n // rAt l6n, thuat to6n trong bdi 2.8 kh6ng d6p fng dugc. c6 thti sir dung kI thu4t chia d6 tri c6 dQ phric tap O(log,$ nhu sau: ,N l(Ur M'rnodA:1"

l(Ur

d'u'

mod

A)x(MN

o'u'mod

A)x(MN

function luythua var w : int64;

(M, N:

o'ut

mod diu'mod

l))

mod A,n€u N chin

A)x M)mod.A,ndu N

16.

longint) : int.54 ;

begin

w::Iuythua (M/ N div 2) ;

,q.: (\^/*w) mod 1OK; . if N mod 2=1 then r;=1w*M) mod

exit

1OK;

(w) ;

end,'

I

4.31. St dqng hdm luythua cua bdi 4.30. 4.32. Ap dqng ki thuer chia d6 tri, voi hinh kich thudc 2k (k> l) bikhuy€t m6t 6, ti6n hdnh chia ldm 4 hinh w6ng kich thu6c 2k- | bingcit ngang vd cit doc. Ki6m tra xem 6 bi khuy€t nim o hinh w6ng ndo thi titip tuc giii quytit bii to6n vdi hinh w6ng kich thu6c 2k- | co khuy6t m6t 6, l6t 3 hinh vudng con lAi nhu bdi l6t n€n da trinh bdy trong phAn H thuy6t.

4.34. Su dpng phuong ph6p quy hoach dQng tim ddy con don diQu giim cira

or. Ggi LLil ld d9 dei ddy con don diQu gi6m lon nh6t cira ddy et, a2,..., cti. Tuong tu, str dung phuong ph6p quy hopch dQng tim ddy con ddy a1t o2, ...,

- t, ..., et . Ggi R[i] ld d0 dAi ddy con dcrn diQu girim l6n nh6t cua ddy an, an - t, ..., ei. Dg ddi ddy con l6i dai nh6t h gi6 tri lon nhAt cua Llil + R[r] - I (l : 2,3, ..., n - l). 4.35. Su dung phucrng ph6p quy hoach dQng, gAi 41,71 h s6 ki tg it ntr6t cAn don di€u gi6m cria ddy ar,

ctn

th€m d6 xdu con li6n tirSp u i d6n7 tao thdnh m6t x6u d6i xring.

+ Truong hqp 1: neu S[i]

:.t[i]

thi F[i,

j] :

FIi+t,

j -tl

+ Trucrng hgp 2: ndu S[i].t}l thi F[/,7J=min{FIi+l,i]+1, fl.i, j -11+1 }.

t42

I I

4.: tA

oo

Tir

t:

\,

uses math,.

const

MAX =200;

var f :array[1. "MAX,1..MAX]of longint,. s .: string,. n : longint; function qhd (r, j : longrnt) : fongint; begin

if fli,jl>-1 then exlr(fti,jl); if i>:j then

begin LtLt

)).*vt

exrt (0); end,' r! iLI =stjl then fIi,j] :=qhd(i+1/ j-1) else f i, j I :=math.min (qhd (i+1/ j ) +1, qhd (i, j-1)+1);

end,. BEGIN

f il-f char (f , sizeof (f ) ,255) s:=tacbcdt,. n: =length (s) ; writel-n (qhd(1,n) );

;

END.

Llijlld

p0t

4.36. Gqi

lgc.

d6ng.

bdi

rinhLti jt:'no'n'"j;:;^:#;i;i"i"il,l;,)lll,i,

rQi

(i Dta

tdv )on l9u

tri tan

Sk
-1 then exir (f ii, j I ) ; if i:j'then begin LLLt)J.-w,

exit (0); end; f [1, j ] ::qhd(1+1, .

for k::r*l

j) +s Ij ] -s ti-11 to j-1 do begin

;

t43

!i.=qhd (r, k) +qhd.(k+l-, j ) +s Ij ] -s ti-11

if w (tinh (c, b) +tinh (a-c, b) ) then res :: (f' Ic, b] +f Ia-c, b] ) for c::1 to b-1" do if res> (tinh (a, c) +tinh,(a, b-c) ) then res: = (f Ia, c] +f b-c] Ia, ) f Ia,b] :=res,. exlt (f Ia, b] ) ;

end;

BEGTN

assign (input, f i_) reset(input); assign(output, fo) i rewrite (output) readln (m, n) ; ,.

10. TLCTHBTQl-A

,

145

€i l lnl-r:r !f,IIurIoI

lF \r,

sr2tkl then k to ); if sr2 [k] < 2 then exit (sum); srZIk] := sr2 [k] div 2; sum := sum. + sr2 [k],'

end,'

exj-t (sum); end;

procedure truyvet i

x

h(

D

tt

var i/ j: longint;

begin

ans := 0; for i :: '1 to tt. do if frlil < time then

.

begin

for;::ltomdo if andbir(i. j) > 0 then sr2l)l := srIj]

else

sr2[j] := O; ans :: max(ans, dem(time _ frlil)

end,.

);

end;

procedure gnkq; begin writel-n (fo, . ans) ;

end,.

.Begin

assign(fi; 1nputf11e) ; reset(fi) ; assign (fo, outputfi1e) ; rewrite (fo)

nhap; f loyd,'

taodothi,. kho

i tao,.

thd;

gopdd,.

truyvet,. gnkg;

close (fi) cl-ose (f o) End.

,. ,.

4.48. Mgt khdu ThuQt toan

I: EQ phric tap O(n3).

X6c dinh-vector nghi€m: (x1, x2) trong d6 I c[p chi sO (i,/). .,

< x1l-y21 length(.!

tuong ung ld

Xric dinh rdng bu6c: Trong xdu

E tu vi trf x1 d6n .vi tri x2phrii xudrt hi6n chir in hoa('A'..'Z'),m6tchfr'cdithucmg (,a,..,2,),m6tchg.s61,0,..,9,;vdx2_x1 )J. oe'tipt k€ t6t cit citc khri nang ta c6 th6 su dung hai vong ldp r6ng nhau, cu th6 'thu tgc liet kC nhu sau:

1

1. TLCTHBTQl.A

161

Procedure try,'

var x1, x2, n :longint; begin

n.:lanath/C\ f vrrY

9rr

\ v /

count : =0;

' '

for x1::1 to n do foc x2::1 to n do if isOK (xI , x2.) then count ::count+1; end,'

Trong thi tuc tr6n, bi6n S h bi€n todn cgc, luu xdu S dfr li€u vdo; bi6n count ld bitln todn cqc dung d6 d6m s6 luqng cpp thod mdn; hirm isOK(xl,x2) nhQn hai tham s6 dAu vio li hai chi sd cria xdu S c6 nhiQm w ki6m tra rdng buQc, tri vO TRUE n6u thori mdn rdng buQc, FALSE trong trudng hqp ngugc l?i. Trong hdm ndy ta s€ ph6i ki€m tra c5c di6u kiQn sau:

l)

xz-x1

)

5;

' vitri tztl vi frir.x2 cira r:r'rA x6u rrArr S S c6 ki tu trr fhrrAc lta'..'z') thuQc l'a' 3) Tu vi tri x1 d6n Tu vi tri x1

t, t\

='O' )and(SIi1:c1)and(SIi] 5. DQ phuc

truong hqp phdi thit O(n2) nhdn v6i chi phi ki€m tra

O(r), do d6 dq phuc tgp thqat todn tr€n ld: O(n3). Chucrng trinh tr€n c6 bi6n S thuQc ki6u

dt

li€u ansistring (ki6u xdu ki tg cho

phdp dQ ddi lon hon 255) vi dg ddi xdu vdo l6n toi l0o, bi6n count thu6c ki€u ,61A? int64 (mi€n gi6 tri -2"" d,An2""-l) vi s6 lugng c6 the vu6 qu6 ki€u'longint

khi d9 ddi xdu l€n tdi 10o. Ki6u ansistring vd int64 ld hai ki6u dfr' liQu c6 trong FreePascal

Thuqt toan 2; EQ phuc tqp O(n2).

loi gidi trdn ld O(r3) voi r ld d9 ddi xdu,S. D6 giarn dQ phirc t4p thiphai giam sO trucrng ho.p ph6i thir hofc gidm chi phi phAn ki6rn tra. D6 nhdn th6y c6 th6 giam chi phi ki6m tra theo nhdn xdt sau: vi€c ki€m tra DO phirc t4p cira

164

(xt,

xz) c6 thO ki6m tra nhanh trong

dQ phric tap thuQt to6n

ThuQt roan 3: DQ phric

chi con O(n2)

(.,r1

,

x2) thoh mdn

-

xmin+

tht

t*

O(r2) ve O1r; bing nh4n xdt sau:

thi (*t, x2 + 1) cfrng thoA mdn, nhu vpy v6i m6i x1 ta x6c

dinhx,.,.,;n nho nh6t d6 (x1, xrnin)

lt

.

tap O(n).

Ta c6 th6 gi6m sti trucrng hqp phdi n6u

,

t t- l.A O(l) rkhi da ki€m tra (xt, xz - l). Nhu v4y

I vi trithori

thoi

mdn thi x2

€ lrrnin, r]

d€u thoa mdn, c6

mdn cho x2. Nhu v4y chi cAn thir x1, s6

luqng x2thoit

mdn (tuong img v6i x1) d6 ddng tinh dugc.

Vdixl

cdch xilc dinh in,,;n nhu sau: rrnin= max{x1 + 5, xHAZ, x1_u7, xggl trong

d6 xu|z ld vi tri nho nh6t l6n hon x1 mlr tu x1 d6n xssT c6 xu6t hien ki ttr thu6c l'A' ..'Z'l,tucrng tV xLazld v! tri nho nh6t lon hori x1 md tu x1 d6n xya7a6 xudt hi6n ki tu thu6c f'a' ..'z'l,xg9 ld vi tri nho nh6t t6n hon x1 md tir x1 d6n x69 c6 xudt hiqn ki tu thuQc l'0' . .'9'1. Vi0c x6c dinh xgur, xLaz, x09 c6 ttrti x6c dinh bing cdch chudn bi truoc.

cac

)ng hftc

tra

Chuong trinh hodn chinh const, laAX =1000000;

fi

='MATKHAU. INP' ;

fo

=TMATKHAU. OUT' ;

var next :array[1..MAX,'1r..'3']of s : ansistring,. n : longl-nt ; ^^,rhr

;ho .i

reu Tint

)ng

longint.;

r';^+CA, f rrLv:t

procedure readFil-e; var f : text,. i : longint; c : char,' begin assign(f , fi); reset(f ).,. readln(f,s); I n : :length (s ) close (f ) for i::1 to length(s) do if ("[i]>:'O') and (sIi]='a')and(sIi]j then j::nextli,cl; if (jlmin do begin xl :: ( Lmax+Imin). d)v 2; if isOK(x1) then begin res : =xl; lmin:=xl.+ ,1 ,'

end

else Imax:=x1 -

1;

end,' end,.

4.50. Lucky Numbers

Lipt k€ tdt cdcdc s6 c6 dang g,..g6...6 t6ng d6n theo gi6 tri bing hai vong lap l6ng nhau: vong s6 luong cht' s6 tdng dAn (l: 1..200) ua so t*qnjcht s6 s"ru"L dan (r = 0..0. Xdy dung hdm chia ro rlt cho'sd nrro ac r.ie.1ru tiJ chia h6t.

4.5t. ACM Brin ch6t bdi to6n rd can chia tgp l chon phu tr6ch m6t t6p.

l

chri d€ thdnh ba tQpdc rn6i hoc sinh duoc

Bto'c I'chu6n bi dfr ri€u, cu th6 voi m6t

tQp con (c6 z1t t[p con, k€ qatqp rSng) do mdt hoc sinh phu trrich thi d4t duo. c di6m ldn nhat u bao nhi6u. Bu'rc 2 DuyQt c6c chon ba hoc sinh, cu th6 duyQt tdp x (do hoc sinh thu nh6t " phu tr6ch), duyQt tap y (do hoc sinh thri' phu hai tr6ch), tQp z lirt6p con lai (tap 1 I chu dC loai tru tap x, tqp y).

168

[oan

const MAX =1000,. LIMIT :1000 * 1000 * fi ='bonus2 . inp' ; fo:'bonds2.out' long

bsE [hay

1000,.

var a/s :array[0..MAX,0..MAX]of longi_nt; u,d, ], r :array[1. .MAXJof longlnt; ;1nnainr' n

1z . f vrrYarru/ . I nnni n+ .

hac1-

procedure docf;

var f :text; i, j : longint,.

begin f rl-l-char (s, si-zeof (s) ,0)

assign(f, readfn (f, for i: =1 for j ::1 begin

fi) ; reset(f)

;

;

n, k) ;

to n to n

do do

read(f,aIi,)l); sli-, jJ::sti-1, jl+sIi,)-I)-sli-1

end; cfose end;

,)-\)

+ ali, j];

(f);

procedure tim,.

var i, j :'1ongint,. elrm

. l nnni .4vrrY+rrL,

nf

.

begin Iap

lng

for i:=L to n

begin u Ii] :=-LIMIT; d Ii] :=-LIMIT;

do

I r.i l.=-T.TMrr.

. rlil 3:-LIMIT; end;

pc

lop A.

fur 0p

for i::1 to ,n-k+1 do for ;:=l- to rn-k+l do begin sum::s Ii+k-1, j+k-1] -s'[i+k-]- , j-I)-s Ii-1, ]+k-l_l+s [1-1 ,)-I]; if sum>u Ii+k-1] then u Ii+k-1_] ;=sum; if sum>d Ii ] then d Ii ] ::sum,. if sum>l- tj+k-11 then I Ij+k-1] ;=sum; if sum)rljl ttren rIj]::sum; end;

for i:=2 to n do begin if u Ii]0) and (ztjl>0) then begin if odd(ztil) and odd(zlt)) then begin dec (z til); dec (z tj l); tmp:=(tmp + qhd(zl) mod NMOD; end;

zlil ::x [i] div 2 ; zll I :=x [j ] div 2; tmp::(tmp + qhd(z)) mod NMOD,'

end,' end,'

f fy t0l, y[1 ), y [2], y [3], yl4l I :=tmp; exit (tmp);

end;

procedure xuly;

var i :longrnt;

begin f -il-lchar (f , sizeof (f) ,255)

172

;

chl

f [0,0,0,a,0] :=r; fillchar (s, sizeof (s) ,0) ; readl-n(ft,n) ; for i::O to n-1 do read(ft,sIi]); writeln (gt, qhd (s,r ,r ,.

end;

BEGTN

chuanbi;

assign(ft, fj_); reset(ft) ; assign (gr, f o) ,. rewrite (gt) xuly;

;

c-lose(ft),. close (gt); END.

4.54.

Ki lgc tl6 ddmino

Cdch giai cho c6ng doqn l; eudn d6min6 v6i tr4ng thai (i,/, .r) c6 nghia ld ri ^ x€p d€n 6 (i, j) (x€p ldn luot tu tr6n xu6ng du6i, tu tr6i qua phrii) voi s ld d6y

gomn bit0, I mdtii trqngthilij- l6dAuodong ivit(n-;i rl6cuoiodong i - L DdthupntiQn l.ru trf, s s€du-o.c md ho6 ld mQt s6 nguydn r(0 < r .2r - t) md trong bi6u di6n nhi phdn cua r ld d6y s. Cdch'giai cho c6ng doqn 2: Qu0n d6min6 v6i trang th6i (i, t) co nghia ld x€p cl€n hdng i co trang thdi hdng trucrc ld t voi t ld day n bit 0, I tho6 mdn tich chdt mdu tr6n mdt dong (voi R : 8 rhi I < 55). Dung nhdn ma tr6n d6 tinh nhanh.

const

MAXN

:8;

MAXN2 =15; MAXSL =55,.

fi:'DOMINO.INPT,.

fo :'DOMINO.OUT'; tlpe dsType :array[1...MAXN]of ]onglnt; matrrxType :array [1. .MAXSL/ 1. .MAXSL]of J-ongint,. var m/ n, nMod, SL : longtnt,. ds :ariaylI..2,L..I sh1 MAXNlof dsType; count : array ll . ,21 of ' longint,. A, B, AB :matrixType; x : dsType; sum ilongint,. f,g :Lext; dp :array[1. .MAXN2+I,I. .MAXN2, 0..1 shl MAXN2]of w :array[1. .MAXN2, 1. .MAXN2]of longint; mu2 :array[1. .MAXN2]of longtnt; function check (t: longint) :boolean;

I onci

nj-

.

t73

var l.

: J_ongr_nt,'

begin

for 1 t:2 to n do begin if ( (i+t) mod 2 : 1-)and(xlilxtf-11) then exit(false),'

end;

exit (true)

,'

end;

procedure try (i

var c : longint;

:

longrnt

)

,'

begin

if i>n then begin for c: =i to 2 do if check(c) then begin inc (count Ic ] ) ,' ds Ic ] [count

Ic ] I : =x;

end; end

else begin for c::0 to 1

do

begin

vf i l.:n.

J:

L!J

'

try (i+1

);

end; end; end;

function ghep ()7, )2, i : l-ongint) :boolean,' var j : longint,' begin

for j:=1 to n do begin if ((i+1+j) mod 2:1)and(ds[(i+1) mod 2+1)[r1] tjl>dsIr 2+71 ll2ltll) then exit(false),' if ( (i+r+1) mod 2:O)and(ds[ (i+1) mod 2+I)lj1] tjlcdsIi 2+Il l)2) tll) then exit (false);

mod mod

end; g^r ^.,i

+u /+-,,^\ . \ L! ug,, t

end;

function mufMatrix (X, Y: matrixType) :macrixType,' var 1, j, k : longint; .

7 4

.--+-i..m"*^. .lLraurr^f

yIJs,

begin fil

lnhar(7

\4,

1 then begin . AB:=expMatrix(AB,m div 2); if m mod 2: I then aB:=mul-Matri_x(AB,A) el1m.:n

v,

;

'

for i:=1 to SL do for ;::1 to SL do Sum::(sum + ABti, jl ) mod nMod; end else sum: =SL,. end,'

procedure xuly2;

begin readln(f,n,m);

,

chuanbi; qnat;

writeln end,.

(g, sum) i

function checkl (i, ), L,c : longint) begin

:boo1ean,.

t75

(i+;1 mod. 2: t (j>1)and(c:0)and(t u,-,J mu2[j_1]>O)and(wli,1_r1:g1 then (false) ; (r>1)and(c=0)and(t and mu2 [j ] >0) and (wii-r, j l:o) rhen (faJ-se) ; end else begin if (j>1)and(c:1) and(r and mu2 t j -1 I :O) and (w f i, j -1 I =O ) tlren exit (fatse),. if (i>1) and(c:1) and(t and mu2 tjl:0)and(wIi-1, j]:O) t]ren exrr (fa]se) ; end; exit (true),.

if if exit if exrt

end,.

function tinh (i,J,L :Iongj-nt) :Iongint,. var c : longint.; sum: longrnt; begin

dpli, j,tl>=0 then exrr (dpli, j,rl if1f i>m then begin dpIi,],tl:=1; exrt (1);

);

end,'

if w[i,j]=i then begin if jwli, jl then w[i+1, j] ::wIi,j] ; if wli+1,j+1l>nexrlwli,jl /ali+11 I then begin if j+1>mk then mk.:.j+1; w Ii+L, j+1] ::next [w Ii, j ], a Ii+1] I ;

end; end,'

end;

exit

end;

(mk) ;

BEGIN

assign (f , fi) ; reset(f),' assign (9, fo),. rewrite (9),. -^^Il!ed.qJ-rl

-m^^!\ (/€t, nIesE,

;

while nTest>0 do begin' dec (nTest); tong:=O; cntrnl-

.:O'

alpha::0;

read]n (f , T) ; ra:dln

/f \Lf

l-r\ v,

.

,

nl'r: =l+vr]Y cnnl-9r1h /h\ \v/

.

,

,'2, ) ; while T>0 do begin readl-n.(f , a) ; na: =length (a) ; makeNext (t At dec (T) i kq: =tinh; if kq>al-pha

then alpha:=kq;

end,1

178.

12. TLCTHBTQl'B

writel-n (9, alpha)

,.

end,'

c.Iose (f ) close (9) ;

,.

END.

4.56. C6 phi6u Gqi

L[d,

i2, fu] ld so tiOn nhi€u nh6t den h6t ngdy d vit d.angc6 i c6 phi6u 1 loai 1, 12 c6 phi€u loai2, t3 co phi6u loai 3 (n€u chi c6 m6t loai c6 phi6u thi

Qz: Qt:

i1,

0; n6u chi c6 hai loai c6 phi€u thi e3

Hdnh dQng b6n c6 phi€u:

Lld,

i1,

iz- l,i3l

ho4c

Ti Lld,

Lld,

\,

iz,

i1,

i2,

: 0).

\lchuy6n

nhdn cho

Lld, i1- l, i2,

i3),

h- ll.

Ti Lld, i1, i2, fufchuy6n nhdn cho Lld, i1 * I, i2, fl; Lld, i1, i21 1,z31 hopc Lld, i1, i2, fu +ll Hinh

dQng mua c6 phi€u:

.

chuycn nhdn sang ngdy mcri: Ti L[d,

Tuy nhi6n kich thu6c ming

r

i1, i2,

fi]chuy6n nhdn cho Lld +

l,

i1, i2, i3l.

qu6 l6n, th6ng thucrng sir dung m6ng niy chi cAn dung m6t m6ng truc

L10..1, *, *, *] tinh cho nhau. Trong bdi to6n ti€p m6ng Ll,*, *, t, *J . EO phric t4p thu4t to5n: O(D.

const max:100; fi :'stock. inp' fo =tstock. outt

A .ez.e).

; ;

var l- :array[0..max, O..max, O..max]of int.64; q :array[1..3]of longint; ' cost :array[1..10000,1..3]of int54; n, m, t : int 64'; procedure Readln;

var f :text; i,f :longint;

,

begin assign(f , f i); reset(f ).' readln (f , nrm, t) ,'

for i::1 to n do read(f,qlil ); for i::1 to t do for j ::1 to n do read (f, cost ti, j I ) ; clqse ( f) ; for i:=n+l to 3 do q[i]::O; f

BTOl.B

r19

n : =,3;

end;

procedure Process;

var i1 ,i2,i3,k m.oney : int 64 ,'

:J-ongint.,'

begin

for i1:=0 to q[1] do for i2::0 to ql2l do for i3::0 to q[3] do 1[iL'i2,i3]::-1; 1[0;0,0]:=m,'

for k::1 to t do begin

/ / r^^ ^^ *L; ^,, { I UAll UU Prrfsu

for iL::qtll downto 0 do for i2t:ql2l downto 0 do for i3::q[3] downto 0 do begin money:=I Ii1 , i2, i3]; if money > . l" then

begin

(i1>0) and (1 ti1-1 , i2, i3l < money+cost Ik,1] -1) then [i1-1, L2, !3] . :: money+cost Ik, 1] -1; if (i2>0) hnd (1ti1,i2-1",i3) < money+costIk,2]-I) then I [11; i2-1, i3] :: moriey+cost Ik, 2l-1'; if (i3>0) and (1lr]-,i2,i3-11 < money+costlk,3l-1) then 1 [i1, i2, i3-I] ;= money+costIk, 3]-1;

if 1

end; end;

// mua

co

phieu

for i1::0 to q[1] do f>x L2::0 to q[2] do for i3:=0.to q[3] do begin .-'r Lf Il;1 f LL ," I LJ i3];J , money > -1 then

r(Lvlrgy

if

, -f

begin if (i1 cost tk,1l) money-cost Ik;1] -1) then L Ii1+1, i2, L3] :- money-cost Ik, 1]-1;

and (I ti1+1 ,i2,i3)


=1 95""

'

tg:=maxtrai (i); tg::maxkq(tg,maxphal(i)); I Ii, j] ::maxkq(1 [i. j], I Ii-1, j-1] +tg) ; end; : 2: if i>=2 g1t"tt begin l-an(i); I tg::nem2 .1ti, jl ::maxkq(1ti, j 1,1[i-1- ,)-2)+tg) end;

;

end; end;

u

end;

'

Procedure ghikq;

var i

begin

:

longint;

kq: =0,. luu ::O i

for i:=l- to c do. if l- [w, i.] >kq then. 185

begin

kq::1 [w'i]; l-uu: =i,'

end;

wrlte]n (g, kq, "

r

luu)

Ch;

M(

;

end,' BEGIN

d6r

assign(f, fi); reset (f ) assign (9, fo) ,'

rewrite(g); ranoa

;

,

:

r

docdl; if (w:0) and (c:0) 3ni '(1=3) then break;

xuli;

ghikq;

until false; close (f); close (9) ; END.

l.oo. Niii ei6m Cdch I: Quy v€ bii to6n tim ddy con chung dai nh6t nhung v6i quan niQm thr? i cria ddy A bing sd thriT cira ddy B h ABS(I[t']-BUl)St. DQ phric t4p

sO

thuft to6n O(.t')

Cdch 2: Quy v€ bdi to6n tim ddy con tdng dni nh6t. T4o ddy E g6m 3n phAn til tu dly D nhu sau: Vdi m6i sO D[i] ttu-o. c thay bing ba sO O14+ l, Dlil, Dlil-|. Tim ddy con tang ddi nh6t tr€n ddy E. DQ phric t4p thudt torin O(MogN).

4.61. XAu

f(p,

i,

gin nh6t

j, k):

true

:lalse

c6

!

nghia

li c6,'khotg ff rtlog

v6i x6u thu *ir f r i /c. Dga vdo b6ng quy hopchdQng d.i tin ra tA.Fi md c6 kho6ng c6ch hiQn tpi

E6 phtic tpp thu4t to6n O(Na).

186

dugc xdu d€n vitrt p

fti hai ld7, xdu thri ba ld

' Chil

tra

i; cd th6 giam thoi gian tfnh to6n xu6ng bing c6ch gidi lan i,j, k < | +

-l |

L3j

MQt c6ch cdi d4t bing m6 hinh duyQt de quy c6 ng6t nh6nh., ' . ,1 ., r* ^,-4. d6nh ddu nhfrng tr4ng th6i dA gap cfing cho rlQ phuc tap O(t/-).

const f i

Aung m6ng

MAX =100;

=lacl:tcqj-

fn

r,i

r

LtLy

r

nrrf vs!

innr

'

,

l.

t

va! s :array[1..3]of string,. cs :array[1. .MAX]of string,. n : longint ;

.lnnnin+. hacl. f vrrY+arLt hael-lza lea ..cf rj ng; vevvi,:r,!1 -l ---f Mz\v n . alal .rrrrrrf ."-\X, 0.

!ur ra.

Mlv .MAX,

n .MAX, rrrv 0. 0. .MAXlof byte;

procedure docf,.

var f :text; i

.l nnai

nt- '

begin assign(f , f i);

reset(f ); for i::1 to 3 do read]n(f,stil); close (f); n'=lanaflr/ct11\. \U L4J /

in s6

for i::1 to n do' cslil::s[1-,i] + s[2,J-] + s[3,i] + ,A' ;

end; [n

tri

il-1.

procedure capnhat (kq: string; cI, c2, c3: Iongint)

var min :longint;

;

begin

min: =c1;

if mln0) \LrLr[-L,e!t then exit; if i>n then begin capnhat ( kq,

c1 , c2 , c3) ;

r87

exft; end;

for c:=rAt to tz'do if pos (c, cs til ) >0 then begin kq::kq + c; if c:st1l til then e1::c1 else e1:=c1+1; if c:s l2l til then e2z--c2 else e2:=c2+L; if c:st3l tfl then e3::c3 else e3':sJ+l; diiyet (i+L, e1, e2, e3) ; delete (kq' i' 1);

end; dd

Ii, cI , c2, c3 ] : =1,'

end;

procedure ghikq;

var f :text; begin

assign(f, fo) ; rewrite (f) writeln (f, bestkg) ; close (f);

;

end; BEGIN

docf;

best:=(2*n) div3+2; kq::rr,' duyet (1,0,0,0L' write]n (bestkq" ' , best)

,'

qhikq;

END.

4.62. Password

const l4AX:100+10; fi ='password.inpt; fo =rpassword.out';. tfrpe mystr :ansistrlng; var num :arraY[1..MAX]of longint; s :array[1..MAXiof mYstr; 1 :array[0. .MAX, 0. .MAX, 0. .8]of Eystlt d :a5ray[0. .MAx, 0. .MAX,0 o.8]of longi-at; .

lrtrtr

.l. rvrrY!rr!/ nnni

nl-

.

T : longint; proeed,ure docfile;

var irj,p:longint; tmp : string; begin

for i::1 to n do begin

188

rFe.'l ln lnrrml-i I ):

str(numIi],stil); end,' for i-::1 to n-1 do for j::i+l to n do if s Ii] +s tj I O do begin dec (T) i read]n (n, m) ;

docfil-e,' t.im;

if d In, $, 0 ] :0 then writeln else writeln (l- [n, m' 0 ] ) ;

(-1

)

end; ^t ^^^ UIUDE

/i -^,,F\ \trryuL,,

,

^t ^^^ uruDE

/^.,rn,,f

\

\vuuyuL,,

. o

t

END.

4.63.

const nfin ='eLKHO.INpr i nfout :IeLKHO.OUT,; maxn :1010; oo =1000000010; vat f :array[0..maxn. 0..maxn] of longint,' p:array [0. .maxn] of longint; rI,. 12:Iongint; rrrt €in !fr!,

n. . rvrrY l nnai +r1e nJ- t. rr fnrri.teXt;

function

min

(x' y: l-ongint) : longint;

begin

if xO then begin p1:=qhd (x-1, y) shr cs; p2::w Ix-1,Y] and LIMIT; Lf p2+a>:Imid then begin p1 ::p1+1 ; P2::0; end

else p2:=P2+ai if (p1 shl cs) + p2 > w[x,y] t]en w[xry];:1p1 shl

cs)+p2;

end;

if y>0 then begin " p1::qhd(x,y-l) shr cs; p2:=wIx,y-1] and LIMIT; if p2+b>:Imid then begin p1::p1+1i p2z:0,' end else p2 z--P2+b; if (p1 sht cs)+p2 > wIx,y] t]ren wlx,yJ:=(p1 shl cs)+p2; l end; exit.(wlx,.yl); end;

Procedure tim,' begin :O ; . lmin: l-max:: (x*a =0;

rlst:

+ y*b) div

m;

while lmin:m then begin rf st : =l-mid; ' fmin:-lmid + 1; end else lmai:=lmidt -1;/ end,' writeln ( f2 ' rlst) ;

end,'

BEGIN

assign(f l-' fi); reset(f1); asSign (f 2, f o') ; rewrite (f 2 ) ; readf n (ft,4, di Yr.b'm) ; -

re?-

f1m. LllLLt

readfn (f1, x, a, y, b,m) tim,'

;

close(f1),'

.

cfose (f2

);

END.

4.6s. {

$M 10000000

uses math;

const fi : fo =

}

'palpath. inp'

;

'palpath.out',

= 55; tx : array l0 . .2I of longi-nt: (0 , I , O) ; ty :array!0..21of longint:(0,0,1) ; Tlpe dinh : record x', y: longint; maxn

1

end; VAR

a :array[1..maxn]of string; f :array[0. .maxn, O. .maxn, O,,maxn, 0. .maxn]of longint,. tr :array[1. .maxnr 1..maxn,1..maxn,1..maxn] of dinh; kq:array[1. .maxn*4] of dinh; , m, n, nt : longint ;

Procedure enter;

Var i: longint Begin readl-n

;

(m, n) ;

,for i:=1 to end;

m

do readln (a[i]);

/

Funct,ion f ind (i ,) ,k, h: longint) : longint;

.Var urvrw:longint; Begin

if f ti,),k,hl=-1

then begin if (kf

Ii,],k,hl

tJ|en

r93

'

'

f [i,i,k,hj:

- tylu.l'k-txtvJ,n-.o7;; with trli/j,k/hl do begin x::u;y,:rrr"id,

end,.

"

(* * ** * ** * * * * ** * ** * * * * * * * ** * ** . \7':n

\

for u:=1 to 2 do

ir

i#iJt-:"Iu], j+tvIu], k,h)>rIi, 3,k,h] rhen

f [i, i , k, hJ ::f Ii+tx Iu] +t y[u]'k-tx[vJ,h-tylv1]; ,i with trIi,j,k,h] do begin x::u;y:=v,.end;

' (* 11

end;

******.****** *** *** * ******* .

':n

for v:=1 to 2

tt

i#lJt,

\

do

j, k-txIv],h-rvtvr )>rli, j,k,hr

then

+tv rur , k-rx rvr h-rv , '*iil*llii, rvr r ; fjil;i';l', begin x:=u;y:=v;end;

I

;

end,. end,.

f

ind: =f Ii, j , k, h; -.'

end,.

Procedure

var

"L,

,.

pr:.nj-,,.

), k, hru, V, p: longint,.

nho : dinh,.

Begin

i : =1,. j : :1,. k : :m; h nt:=f[1,.1 ,m,nj,. ::n,.

P:=1;

while true begin

do

if_ a Ii, j j:a fk, h] then begin * v: :j ,'end,' I: tl: !o- feqin ' :',' do besi"' J ;t:k;v'-lr''r"rra, i"" tplltnt'p+l

;ill end,.

'

nho:=trIi,l,k,h); with nho do begin

if (I:9) and 1y=g; rhen break; i: =i+t1 J;a1 ;

I

::j

+ry Ix] ;

194 13. TLCTHBTQl.B

. k:=k_rx Iy] ; h::h_tylyl; e4d; wri-tel_n (nt); for i::1 to nt do with. kq I i ] do wrlt.eln (x, ,

'

end;

,.

,

y) ;

i ,

BEGIN

assign (input, fi) ;aFsign ioutput, fo) reset (input) ;rewrite (output) ; .

enter,.

f ill-char (f., sizeof (t) find(1,I,m,ri); hrl y!

+rr

hf

(input)iclose (output.) i

EIID.

{

,2SS) i

. L ,

cl-ose

{

;

9r+, q+ 9m l-0000000 1

const

MAX

f f

var f.y I

}

= 100i

i ='option. inp.' ; o ='option . out t.;

: array [ 1. .MAX, 1. .MAX] of longint.i :array[1..MAX.0..MAX]of longrnc; Vrrn :array[1. .MAX]of longint;

n, k,

hAct-

start: longlnt; . 4vrrYrrrL, I n^^.i -+

.

Procedure docf,. var f :text; i, j, ,: longint; begin ; issign (i,tj); reset(f) i . readl-n (f , n, k) ; for i:=1 to n do begin read(f,vIi],mlil ); for j:=1 to mt1{ do read(f,keyti,jl); :

end,.

close (f);

end;

funbtion var w i,),L begin

(node, s: longint) :longint; :array[0..MAX,0..MAX]of 1ongint,. :Longint;

qhd

195

if

l- lnode, s]:-1 then begin if s:O then begin l-[noders]::0; exit (0) ;

end;

if mInode]=0 then begin Itnode,sl::i7[node]; exit (v lnode] ) ;

,

end;

for i::1 to m[node] do if key Inode, i] start then for j :=0 to s-1 do qhd (key [node, i] , j ) ; fillchar (w, sizeof (w) ,0) ; for i::1 to mlnode] do begin

if

r

]:start then be.gin wlil:=wli-l1; 'continue;

key [node, i

end,'

for j::O to s-1 do for t;=0 to j do if wIi,j] < wIi--1,t] + 1[keylnode,i],j-tl then wli,jl :: wli-1,t1 + 1[keYInode,i],1-tl; end;.

I Inode, s] :: v[node] + w[mlnode]' s-l1

;

end;

qhd::1 [node, s];

end;

Procedure l-am,' begin best : :0;

for start;:1 to n do'begin f il-Ichar (1, sizeof (I) ,255) ; qhd (start, k) ,' if best

'Thuflt to6n dugc thpc hiQn trong thoi gian O(r). 5.8. Phdn tich:

aarg,i1

: Zn6,e1B' (u,i) =1a6,e1B(i,e) eeE

N6u i :

N€u i *

j, ta c6 B(i, e).B(/, e) :

J

eeE

(B(r,

.))'" :

ft.

tt

ndu e di vdo hoic di ra dinh

i

t;, ;;;;.

i, tac6 B(r, e).B(/, ., :{1, ::: : ;*jJff:ffijij],

3,

f,

nou. r.

t(

liO n thu6c v6i i, ndu i = i r ISO cung"., VQyBB'(i,j):4_. j,n€u j.

fSd cung kOt ndi i

T

i*

u6

5.9. MO hinh cdi dfit

ttri dudi d4ng danh s6ch kC, m5i dinh z ring v6i mQt danh sdch list[r/] ld danh s6ch c6c dinh ndi tit a.

Bi6u di6n

,

OO

Xdy dgng hai hdm:

Removefirst(a): Hu! bo dinh ttung ttAu danh s6ch list[a].

Khi d6 thuft to6n DFS kh6ng

traaeIs] :=

dQ

quy

bit tlau tt dinh s c6 thiS vii5t nhu

0;

repeat

Arrtnrr{vuLPuL

a r

rr. ut

while (u I O) and (first(u) rr

.:

l-Llsvv raao

ifu#0then

begin

v ::

ramnrraf

end;

f

irst i rci

ltrl LsJ,

,

(u) ; e

until u : 0i

202

.

/rr\ \e/

.

t

: 0)

do

Vl

sau:

5.10. Ph6n vi du:

5'll.

Thuc hiQn thudr to6n DFS. Khi r,i dinh uxdt mQt dinh v kd z, n6u v chua thim thi di thdm v, n6u v d6 thdm, v * u vitv kh6ng ph6i nrit cha cria u thi truy v6t duong d.i tir u vC y n6i th€m canh (vt, u) nirad6 duqc chu trinh don. 5'12' Ddp dn: c6'c dinh sd duqc riQt k6 theo rhri tp t'ng dan cua nh'n a[.]. BFS v6i noi xu6t phdt rd cric 6 bi€n dti tim duong di

lli;f*|rffi*iljf" Truy v6t

c IAid6 tim duong di. { $MoDE oe,lrpC } {$INLINE ON} program Escaping,. nguo.

'-

const fnputFile = ,LAByR. TI\TD ' ' OLitputFile = ' LAByR. OUT maxMN : .t non. dx: arrayt1..4l of Integer : (1. -I, 0, 0); dy: arrayt1..4l of -Lnceger (0, = O, !, _1); var a: array[0..maxMN + ]., 0..maxMN + ll of Char,. trace: array[1. .maxMN, i: :;;;J of rnreser,. array .maxMN * maxMN] of rnreger,. ?I:-lO: rronL/ rear: f[1.. nteger,. m, n: fnteger; f i, fo: TextFil_e; sX, sy: fnteger,. ,

procedure Enter; I""-t, jr rnteger,. begin Readln (fi, m/ n); FrffChar (a, SizeOf (a), 'X,); fori:=1 tomdo begin

for;:=1

begin

tondo

Read (fi, a [r, i ]); 1f a[i, j] : 'E' then

203

begin sx :: 1; end; Readln end; end;

sY

(fi);

procedure Push(x, y: Integer); inline;

Legin rnc(rear); q;trearl := x; qyIrear] :: y;epd; piocedure Pop (vat x, y: rnteger) ; inl-ine; tegin * :: qTIfront]; y := qytfrontl; rnc(f;ont);end; procedure rnrt; var i, j: Integer; begin

rittctrar(trace, Sizeof(trace), $Fr) ; //-L; front z: 1; rear :: 0; for i :='1 to m do

begin

if ali, 1l = 'Ot then begin trace ['i, ]" I :: 0; Push (i ' 1); end; if (n > 1) and (a Ii, n] : 'o') th'en begin trace[i, n] := 0;' Push(i' n); end; end;

forj::2|uo

n-1do

begin.

if a[1, j] : 'O' then begin trace[1, j] :: Or' :eu9hj1, j); end; 'O') then if- (m > 0) and (alm, jl begin trace [m, j ] :: 0; Push (m, j ) ; end;

end; end;

procedure 'So1ve; Vaf UX.r UY, VXr VYt begin . 'if trace Isx, sY] repeat Pop (ux, uy);

ford::1t64do begin vx :: ux + dx[d]; vy := uY + dy[d]; if (a Ivx, vY] begin

;. u.

Tn..adar! 4r,revYv-,

- 1 then Exit;

'

traceIvx, vY] :: d; if '(vx = sx) and (vY : sY) then Exrt; Push (vx, vY) ; U^f

204

u,

end; end,'

until front > rear; end;

procedure PrintResul-t var r1v v..,

rrir -r,

I an.

;

a{. *..-.jgef Thi-c

Tnl-6^ar. rlr LvYvl

,

"

begin

ux := sx; uy := sy; 'lan .:

1.

repeat

d := trace[ux, uy] ; ifd=0thenBreak; Inc (l-en)

,'

Dec

dx tdl ) ;

(ux,

l-\an /rrrr vvv \sJ,

until-

I^lri rr!+ev!rr faT.n

. Arr v! l-A rvJ l \t ,

Fal-se; f f^

| an ) ;

\!vt

ux :: sxr' uy :: sy; repeat

Writeln (f.o, uX, ' t , uy) d := trace[ux, uy] ; ifd=0thenBreak; rnc

;

t_Len) ;

(ux, dx Id] ) ; (uy, qy tql , ; until Fal-se; Dec Dec

end,'

begin AssignFlle (fj-, InputFile) ; Reset (fi) ; AssignFile (fo, OutputFile) ,' Rewrite (fo)

try

;

Enter;

Init;

Sol-ve;

PrintRe sulrlnaJ_ly

L,'

CloseFile (fi) ; CloseFile (fo); '

end; end.

5.14. DuyQt DFS tr6n G, gqi f[r/] ld thoi di€m duyQt xong dinh a.

o':>" N€u G c6 cung ngugc thi G c6 chu trinh:

-.

205

Vi m6i cung nguo c (u, v) n6i tu , l€n mQt dinh v ld ti6n b6i cua u tr€n cd.y DFS, duong di chu trinh.

tin

xu6ng z; theo cdy DFS r6i n6i th€m cung (2, v) sd t?o ra

'o0) and (]kt j I >lk In]+w Ij, i, begr"roIt ] ::rktir +w[ ), L, rr ; .

1

1]

)'

!h"n

tilj,2!z=L;

_r!i, rafse,' -_:ili unEar end;

Frocedure

denCoQuan;

var i, j , imin, l-min : longint,' begin

f if Lchar (d, sizeof f,or i:=1 to n do ]n Ii] ::1imit; In lnl : =u,'

(d) 0) i '

repeat

Imin': =1imit; for i:=1 to n do if (ln ti-l 0)and(lh tj I >Inlil +wtj,i,2l ) then begin

. lnIj]::lntil+wtj,r,21i' trlj,3l:=i; end;

unti]. falsb; end;

216'

Procedure ghikq.;

var f :text; i, ibest : longint.;

begin assign (f, fo) ; rewrite (f) best ::maxl-ongint;

;

for i::1 to n do if (11 til+IktilI1 [i]+lnlil begin

) then

best::11[i]+fn Ii]; I L^^+ rvgD

"end;

. L . -4, -l

.

writeln(f ,best); cfose (f); end; BEGIN doc f i l-e,'

tuNha; denCoQuan; Aan'Frrrnnn. gvrrY,

gh

i kq;

END.

5.33: V6 xe mi6n phi Thudt toan I;

. X6y dgng ming Itd le dq dai duong di ngin nh6t tt I ddn i (i:1, 2,..., M, mdng RI4 h d9 ddi ducrng di ng6n nh6t tir N d6n i (i :1,2, ..., Af. Thoi gian chuAn bf ming L vd R b[ng thu4t to6n Dijkstra Heap trdn d6 thi g6c mAt O(MogN + M. . Thir ldn lugt ttrng c4nh d0 chgn c4nh (i,7) me I[i]+RUl ld nho nhAt. Thudt todn 2:

. Xdy dr;ng d6 thi mdi tt dO thig6c nhu sau.: v6i m5idinh i ctra db thig6c t4o hai ttinh cira dO thi m6i (i, 0) vi (t, 1). Tu dinh (l, l) sang dinh (7, l) c6 trgng sd bing trgng s5 c4nh (i,7), tu dinh (i, 0) sang Q, I) c6jtqng sO.bing O' . Xdy dirng m{ng Lli, tl h d0 dei duong di ngdn nhat tt I d6n i (i: 1,2, ..',10 dd str dsng (r : l) hay chua sir dsng (r : 0) vd khuytin mpi bing thu{t to6n Dijkstra Heap tr€n dO thirn6i v6i d0 phirc tap O(Mog// + Al). Chf :i, thuflt to6n I chi c6 thii giai v6i sd v6 khuy6n mpi ld l, nhung vdi thuQt tohn2 c6 th6 gi6i cho bdi to6n mo rQng v6i sd vd khuy6n m4i ld k, khi d6 do thi m6i c6 (k + l)Ndinh.

2t7

5.34. Hexgame ThuQt todn

l: vdi m6t trang thdi cua trd choi, l6y c6c s6 tt

trcn xu6ng du6i, tu trdi qua phrii r6i thay so o eau ti€n thanh s6 9, tu dugc mQt hodn vi ctra 0, l, ...,9. rrr X' ^ moi Nhu vay trang th6i cua tro choi tucrng ring v6i m6t ho6n vi cira 0, l, ..., 9 (vi dp trang th6i ban dAu ld ho6n vi 1,2,3, 8, 9, 0, 4, j,6, 5). X6y dung d6 thi,' trong d6 m6i dinh tucmg ring ld m6t ho6n vi, cuhg gifra hai dinh cria d6 thi dugc x6c dinh bing cdch ki6m tra c6 t6n tpi ph6p bi6n eoi gita hai hodn vf hay khdng. Sft dpng thuet toan BFS tr€n d6 thi vua xdy dr,rng d€ tim c6ch bi6n d6i it nh6t. . ThuQt todn 2; NhAn th6y, v6i mQt trang th6i chi c6 hai c6ch bi6n aoi ma gioi h4n 50o/o so uq tiem thu cua bii to6n ld s6 ph6p uien doi kh6ng vugt qu6 15, duyQt nhi phdn gi6i h4n dQ sdu. ThuQt toan 3; Khao s6t bdi todn vd nh6n th6y s6 phdp bi6n d6i kh6ng wqt qu630.SudpngmQttronghaithu4tto6ntr0nnhungtimki6mtuhaidAu.

5.35.

Nhin tin

coi m6i hoc vi€n ld mQt dinh cria d6 thi, u c6 th€ rihin tin cho hoc vi6n v.

canh

(u, v) ung voi quan hQ: hoc vi6n

DuyQt DFS, duyQt xong dinh ndo dAy dinh d6 vrio mQt danh s6ch L. E6nh d6u crlc dinh ld "chua nhdn tin". X6t c6c dinh trong danh s6ch z, tu dinh ,.chua cu5i danh s6ch t6i dinh dAu danh s6ch, m5i trri x6t t6i

-9t

einn a

nhfln

tin", ding BFS hoflc DFS [9t k€ tAt ctr cilcdinh t'chua nhdn tin" d6n dugc tu z thdnh "dd nhdn tin", dinh u vng v6i mQt hgc vi€n md thAy gi6o ph6i nhan tin tryc ti6p. Tinh dfng dEn cira thuat to6n duoc suy ra tu thupt to6n Kosaraju-sharir: Dinh u "chua nhin tin" dring cu6i danh s6ch z tai m6i bu6c ld tlinh thuQc mQt thdnh phAn li€n th6ng m4nh kh6ng c6 cung di vdo. Thoi gian thuc hi6n thu4t todn: O(m + n). Chwong

trinh

{ $MODE OBJFPC

program

Mes

,

l

}

sageSending;

const InputFlle : 'MESSAGE.INpT; OutputFile = TMESSAGE.OUT' ; maxN : 100000; maxM : 100000; var n, .m/ k: f nteger,. 218

I adj: array[1..maxM].. of Integer; Link: array[1..maxM] o.f f nLegert head: array[1..maxN] of Integer; avail: array[1..maxN] of Boolean; Stack: array[1..maxN] of Integer; roq.

:rrarr[1

mrwNl]

tf..r||qj:!!jvl+r.uvYv!,

nf

TnJ-onar.

Procedure Enter; var f : TextFil-e; rr et

i.

!.

Tnfoaar. +rrvvYv!

t

begin. AssignFile (f, InputFile) ; Reset(f) Ery

Readln(f, n, m); FillDWord(head[1], n, fori::ltomdo

;

0) ;

begin

Read(f, u, adjlil); ]1nk Ii ] :: head [:1i] I headlul 1= 1;

end,' t r-na,L I v

Closerile (f); end; end;

procedure Numbering;

var u: fnteger; .t|an. ."r.+IIUvYUl' Tntanar.

procedure Visit. (u: Tnteger) ,' var i: Integer; begin availIu] :: False; i := headlul;

wf,ilei0do

begin if avail- tadj til I then Visit (adj Ii]

i := linklil;

end; rnc ( l'op)

)

;

;

StackITop] :: u;

end,'

begin

EiI Ir-hrr/=rz=ir ToP := 0;

[1],

n, TrUe);

foru::ltondo if avail[u] then Visit(u); end;

2t9

procedtrr€i Selecting; var i: Integer,. procedure .Visit (u: Intege:i) f nteger,. begin ,ava1l- [u] :=.False;

var i: 1

.:

r

h6idlrrl rlvqsLsl,

while i O do

I

begin ,

;

if avail ladj til I then visit (adj til

l_ := _LrnK[J-1,. end;

H-

end;'

begin

FilIChar (avail [1], n, True) k := 0;j

;

r

fori:.=ndowntoldo if avaiL tStack tiI I then

begin Inc (k)

;

resIk] := Stacklil; Visit (Stack til ) ;

end; end;

procedure

Pr.intResu.L t,.

var f i Text.F1le; i: Integer;

begin AssignFile (f, OutputFile) i

Rewrite(f); try wrJ_tetn ( t, fori:=1tok finally, CloseFile

end;

l