cng n tp mn Tin hc CNG N TP Phn I: Xu, Mng: Bi 1: Nhp h v tn. a ra tn. Chng trnh: const fi='bai1.inp'; fo='bai1.

.out'; var s,s1:string; f:text; i:byte; procedure nhap; begin assign(f,fi);reset(f); readln(f,s); close(f); end; procedure xuli; begin while s[length(s)]=' ' do delete(s,length(s),1); for i:=length(s) downto 1 do if s[i]=' ' then begin s1:=copy(s,i+1,length(s)-i+1); exit; end; end; procedure xuat; begin assign(f,fo);rewrite(f); write(f,s1); close(f); end; BEGIN nhap; xuli; xuat; END. Bi 2: Vit chng trnh m cc ph m, nguyn m trong 1 xu ch ton ch ci. Chng trnh: const fi='bai2.inp'; -1-

 cng n tp mn Tin hc fo='bai2.out'; var s:string; f:text; i,dem:byte; procedure nhap; begin assign(f,fi);reset(f); readln(f,s); close(f); end; procedure xuli; begin for i:=1 to length(s) do s[i]:=upcase(s[i]); dem:=0; for i:=length(s) downto 1 do if (s[i]='A') or (s[i]='E') or (s[i]='U') or (s[i]='I') or (s[i]='O') then begin inc(dem); delete(s,i,1); end; end; procedure xuat; begin assign(f,fo);rewrite(f); write(f,'so ki tu nguyen am: ');writeln(f,dem); write(f,'so ki tu phu am: ');writeln(f,length(s)); close(f); end; BEGIN nhap; xuli; xuat; END. Bi 3: Hy sa li chnh t trong 1 cu cho trc vi yu cu: - Nu gp du phy th chn sau n 1 k t trng. - Nu gp du hi, du chm, chm than th chn k t trng v vit hoa. Bi 4: Vit chng trnh m ho xu cho trc theo quy tc a thnh b, b thnh c, z thnh a. Chng trnh: const fi='bai4.inp'; -2-

 cng n tp mn Tin hc fo='bai4.out'; var s:string; i,n:byte; procedure nhap; begin assign(f,fi);reset(f); readln(f,s); close(f); end; procedure xuli; begin n:=length(s); for i:=1 to n do begin if (s[i]>='a') and (s[i]<'z') then s[i]:=succ(s[i]); if s[i]='z' then s[i]:='a'; end; end; procedure xuat; begin assign(f,fo);rewrite(f); write(f,s); close(f); end; BEGIN nhap; xuli; xuat; END. Bi 5: Vit chng trnh nhp 1 xu v a ra xu chun. Chng trnh: var s:string; i:byte; Begin readln(s); while s[1]=' ' do delete(s,1,1); while s[length(s)]=' ' do delete(s,length(s),1); while pos(' ',s)<>0 do begin i:=pos(' 's); -3-

 cng n tp mn Tin hc delete(s,i,1); end; End. Bi 6: Lp trnh m s ln xut hin mi loi k t thuc bng ch ci ting anh trong 1 xu k t. Chng trinh: Var a:array['A'..'Z'] of integer; s:string; ch:char; i:integer; BEGIN write('nhap xau:');readln(s); for ch:='A' to 'Z' do a[ch]:=0; for i:=1 to length(s) do if (s[i]>='a') and (s[i]<='z') then begin s[i]:=upcase(s[i]);a[s[i]]:=a[s[i]]+1;end; for ch:='A' to 'Z' do writeln('so lan xuat hien cua ',ch,' trong xau la ',a[ch],' '); readln END. Bi 7: Nhp t bn phm 2 s m, n (-32768<=m,n<=32768) Tnh v a ra mn hnh so lan xut hin ca cc ch s c ngha ca tng m+n. Chng trnh: uses crt; var a:array[0..9] of byte; s,m,n,i,k:integer; BEGIN write('nhap m,n:');readln(m,n); for i:=0 to 9 do a[i]:=0; s:=m+n; while s>0 do begin k:=s mod 10; inc(a[k]); s:=s div 10; end; for i:=0 to 9 do if a[i]<>0 then writeln('so lan xuat hien chu so ',i,' : ',a[i]); readln END. Bi 8: Nhp vo t bn phm 1 nm dng lch. a ra mn hnh nm m lch tng ng (di dng ting vit ko du). -4-

 cng n tp mn Tin hc Chng trnh: const can:array[0..9] of string=('canh','tan','nham','quy','giap','at','binh','mau','ki'); chi:array[0..11] of string=('than','dau','tuat','hoi','ti','suu','dan','mao','thin','ti','ngo','mui'); var year:integer; i,j:byte; BEGIN year:=1; while year>0 do begin write('duong lich: ');readln(year); if year>0 then begin i:=year mod 10; j:=year mod 12; writeln(' ',can[i],' ',chi[j]); end; end; END. Bi 9: Nhp s t nhin n, a ra dang nh phn ca n. Chng trinh: var n:word; a:array[1..16] of 0..1; i,j:integer; begin writeln('nhap n:');readln(n); i:=0; while n>0 do begin inc(i); a[i]:=n mod 2; n:n div 2; end; writeln('bieu dien nhi phan cua n la: '); for j:=i downto 1 do write(a[i]); readln end. Bi 10: Tng max: Tm dy con di nht cc phn t lin tip c tng ln nht - D liu vo: dng th nht cha 1 s t nhin n, dng tip theo cha n s t nhin. - D liu ra: dng th nht cha tng, dng th 2 cha cc phn t ca dy. -5-

 cng n tp mn Tin hc Chng trnh: const fi='tmax.inp'; fo='tmax.out'; type kmang=array[1..50] of integer; var f:text; n:byte; s:kmang; procedure nhap; begin assign(f,fi);reset(f); readln(f,n); for i:=1 to n do read(f,s[i]); close(f); end; procedure xuli; var dai,d,dau,cuoi,i:byte; t,max:longint; begin assign(f,fo);rewrite(f); max:=-999999; for dai:=n downto 1 do for d:=1 to n-dai+1 do begin t:=0; for i:=d to d+dai-1 do t:=t+s[i]; if t>max then begin max:=t; dau:=d; cuoi:=d+dai-1; end; end; writeln(f,max); for i:=dau to cuoi do write(f,s[i],' '); close(f); end; BEGIN nhap; xuli; END.

-6-

 cng n tp mn Tin hc Bi 11: Mt siu th bn hng phc v tn ni, c n c quan ng k mua hng ng k t 1 dn n, siu th c m loi hng nh s t 1 n m gi nh nhau , mi c quan ch mua mt loi hng. Hy gip h sp xp cch bn sao cho s tin thu c l ln nht. - D liu vo: dng th nht cha 2 s n,m (0<n<m<1000), n+m dng tip theo, mi dng cha 1 s t nhin, theo th t l s lng ngi ca mi c quan v s lng hng m mi ngi s mua vi 1 loi hng. - D liu ra: c n dng, dng th nht l so hiu hng bn cho c quan 1 dng th n l s hiu hng bn cho c quan n. Bi 12: Xc nh n s t nhin u tin m c ca n ch gm 2,3,5. Chng trnh: var d,n,t,k:integer; begin writeln('nhap n:');readln(n); d:=0;t:=2; repeat while k mod 2=0 do k:=k div 2; while k mod 3=0 do k:=k div 3; while k mod 5=0 do k:=k div 5; if k=1 then begin write(t,' ');inc(d);end; inc(t); until d=n; end. Bi 13: Vit chng trnh tinh a^m vi s php nhn t nht. Chng trnh: var m,n:byte; k,a:longint; BEGIN readln(a,m); d:=0;k:=1; repeat n:=m mod 2; m:=m div 2; if n=1 then begin k:=k*a;inc(d);end; a:=a*a;inc(d); until m=0; write('ket qua la: ',k,' voi so phep nhan ',d-2); END.

-7-

 cng n tp mn Tin hc Bi 15: Nhp n s thc (n<=10000). Hy sp xp dy theo th t ko gim. Thng bo ra mn hnh dy c sp xp li v ghi r v tr tng s hng trong dy c. Chng trnh: var a,b:array[1..10000] of longint; n,i,j,tg1,tg2:longint; procedure nhap; begin writeln('nhap n:');readln(n); for i:=1 to n do begin write('a[',i,']=')readln(a[i]); b[i]:=i; end; end; procedure xuli; begin for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin tg1:=a[i];a[i]:=a[i+1];a[i+1]:=tg1; tg2:=b[i];b[i]:=b[i+1];b[i+1]:=tg2; end; end; procedure xuat; begin for i:=1 to n do write(a[i],' ');writeln; for i:=1 to n do write(b[i],' '); end; BEGIN nhap; xuli; xuat; readln END. Bi 16: Dy i mt khc nhau: m xem trong dy c bao nhiu phn t i mt khc nhau. Chng trnh: const k=maxinteger; var a:array[1..1000] of integer; -8-

 cng n tp mn Tin hc n,i,j,tg1,tg2:integer; procedure nhap; begin writeln('nhap n:');readln(n); for i:=1 to n do begin write('a[',i,']='); readln(a[i]); end; end; procedure sapxep; begin for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin tg1:=a[1];a[i]:=a[i+1];a[i+1]:=tg1;end; for i:=1 to n-1 do for j:=i+1 to n do if a[i]=a[i] then begin tg2:=a[j];a[j]:=a[n];a[n]:=tg2;a[n]:=k;end; while a[n]=k do n:=n-1; end; procedure xuli; begin sapxep; dem:=0; for i:=1 to n-1 do for j:=i+1 to n do if (a[i]<>a[j]) and (a[i]>=0) and (a[j]>=0) then inc(dem); write(dem); end; BEGIN nhap; xuli; readln END. Bi 17: Lp nhiu nht: Cho mng gm n phn t nguyn. Tm s m s c lp nhiu nht trong mng. Chng trnh: var a:array[1..1000] of integer; n,i,j,tg,dai,d:integer; t:boolean; -9-

 cng n tp mn Tin hc procedure nhap; begin writeln('nhap n:');readln(n); for i:=1 to n do begin write('a[',i,']=');readln(a[i]); end; end; procedure sapxep; begin for j:=n downto 2 do for i:=1 to j-1 do if a[i]>a[i+1] then begin tg1:=a[1];a[i]:=a[i+1];a[i+1]:=tg1;end; end; procedure xuli; begin sapxep; for dai:=n downto 1 do begin for d:=1 to n-dai+1 do begin t:=true; for i:=d to d+dai-1 do if a[i]=a[i+1] then begin t:=false;break;end; if t then break; end; if t then break; end; write(a[d]); end; BEGIN nhap; xuli; END. Bi 18: Vit chng trnh nhp vo 1 s c n ch s (n<=100). Hy xo trong k ch s c s ln nht. Bi 19: Xt xu s ch bao gm cc k t ngoc m '(' v ngoc ng ')'. Xu s xc nh mt cch t ngoc ng nu tho mn cc iu kin: - S ngoc m bng s ngoc ng. - Nu duyt t tri qua phi, s lng ngoc m lun ln hn hoc bng s ngoc ng. - 10 -

 cng n tp mn Tin hc Bi 20: Vit chng trnh nhp vo 1 xu. Bin i xu theo nguyn tc sau: nu xu l aaabb 3a2b. Bi 21: Cho mt xu: * Hy tm xu con di nht ca xu ny m khng cha bt k ch s no. * Cho 1 k t, xt xem k t ny c trong xu hay khng? Nu c hy tm s ln nht cc k t ny i lin nhau trong xu. Bi 22: Vit chng trnh nhp t bn phm 2 xu k t s1 v s2: * Cho bit k t s1 xut hin bao nhiu ln trong s2 v xut hin nhng v tr no? * Hy xt xen s2 c phi l ghp lin tip mt s ln ca s1 hay khng? Bi 23: Vit chng trnh nhp mt xu s ch gm cc ch ci thng. Hy lp xu s1 nhn t s bng cch sp xp cc k t theo vn a, b, c,. Bi 24: Vit chng trnh nhp t bn phm 1 xu s ch gm cc k t 0 v 1. * Bin i xu s thnh xu s1 nh sau: c t tri qua phi xu s, thay nhng xu con ch gm cc k t 1 lin tip gia cc 0 bi s thp phn nhn n lm dng nh phn ca di ca n, gia cc on ny t k t trng phn cch. VD: s='000111100' s1='11 15 10' * Gi s bit s1, hy khi phc li xu s. Bi 25: Cho hai xu: * Tm tt c cc k t xu 1 nhng khng c xu 2. * Tm tt c cc k t c c 2 xu. * Xu 1 c phi l xu con ca xu 2 hay khng. Bi 26: Cho mt xu: * Tm mt t i xng di nht trong xu. a ra di max. * Thm vo xu 1 s nh nht cc k t dy a cho c to thnh dy i xng. Bi 27: Cho 1 xu. m v a ra s k t khc nhau trong xu. Bi 28: Xu khng c k t phn cch c gi l mt t. Cu l mt xu bao gm nhiu hoc mt t. Vit chng trnh tnh s lng t trong cu. Bi 29: Cho 2 dy s nguyn a v b. Dy c c xc nh nh sau: c[i]= a[k] vi i=2k-1, k=1,2,,n b[k] vi i=2k, k=1,2,,n Hy lp trnh: Nhp t bn phm s nguyn n (2<=n<=20), dy s nguyn a, b.To v a ra mn hnh dy c. Bi 30: Cho dy s nguyn p=(p1,p2,,pn), 2<=n<=100. Bit rng khng phi mi phn t ca p u bng nhau. Hy vit on chng trnh i ch hai phn t ln nht v nh nht cho nhau. Nu c nhiu phn t ln nht hoc nh nht th i ch phn t ln nht c ch s nh nht vi phn t nh nht c chi s ln nht. Bi 31: Lp trnh: Nhp t bn phm s nguyn n (1<n<50) v dy s nguyn a (c t nht 2 ch s 0). Tnh tng cc s a[i] nm gia s 0 u tin v s 0 cui cng.

- 11 -

 cng n tp mn Tin hc Bi 32: Hy lp trnh: Nhp t bn phm s nguyn dng n (1<=n<=20) v n s nguuyn a[1],a[2],,a[n]. a ra mn hnh s lng a[i] l v bn thn cc s a[i] l theo th t xut hin ca chng trong dy nhp. Nu ko c s l no th a ra mn hnh 1 s 0. Bi 33: Hy lp trnh: Nhp t bn phm dy s nguyn khc 0. Du hiu kt thc nhp l s 0. a ra mn hnh: - S lng cc s nhp (ko k s 0). - S lng cc s chia ht cho 3, nu ko c th a ra s 0. - S lng cc s m chn, nu ko c th a ra s 0. Bi 34: Hy lp trnh: Nhp t bn phm s nguyn k v dy s nguyn khc 0. Du hiu kt thc nhp l s 0. a ra mn hnh: - S lng cc phn t trong dy nhp nh hn k. - Tng cc phn t nh hn k. Nu ko c phn t no nh hn k th a ra s 0. Bi 35: Nhp dy a[1],a[2],,a[n] sp xp ko gim. Tm phn t trong dy bng mt s cho trc. Bi 36: Nhp dy a[1],a[2],,a[n]. Kim tra xem dy sp xp cha. Nu cha sp xp th hy sp xp thnh dy ko gim. Bi 37: Nhp mng a kch thc MxN ch gm cc gi tr 0, 1. m xem c bao nhiu phn t c gi tr 0 m 4 phn t xung quanh n c gi tr 1. Bi 38: Nhp mng a kch thc MxN ch gm cc gi tr 0, 1. m s phn t c gi tr bng o m vi mi k cnh, k nh ca n bng 1. Bi 39: Cho dy s gm n s nguyn dng c hai s bt k lin nhau th khc nhau (4n<1000). Ta ni dy s dch dc bc m nu dy bao gm m+1 on lin tip lun phin n iu tng gim hoc gim tng. Nu dy l n iu th quy c dy dch dc bc 0. Cho bit dy dch dc bc my. a ra cc don n iu, mi on 1 dng. Bi 40: C mt ngi i mua hng, anh ta c n ng tin d1,d2,,dn. Ngi bn hng co m ng tin b1,b2,,bm. Anh ta mun mua mt mt hng vi gi tr c. Hi cuc mua bn c din ra c ko. Gii hn: m,n<=100; d[i],b[i]<=100.

- 12 -

 cng n tp mn Tin hc Phn II: Quy hoch ng: Bi 1: Tm dy con tng di nht. - D liu vo t file daycon.inp: dng u l s n, dng 2 l dy n s nguyn - D liu ra file daycon.out: dng u ghi di dy con di nht, dng th 2 ghi cc gi tr ca dy con sau khi xo t nht 1 s phn t trong dy cho. Bi 2: i tin: Cho mt ngn hng c n loi tin mnh gi a[1],a[2],,a[n] vi s lng tin mi loi ko gii hn. Cn chi tr cho khch hng mt s tin m ng. Hy cho bit cn bao nhiu tin mi loi chi tr sao cho s lng t l t nht. - D liu vo: t file tien.inp + Dng 1 ghi m,n (n<=100, m<=10000) + Dng 2 ghi n s a[1],a[2],,a[n] (a[i]<a[i+1]); - Kt qu: ghi ra file tien.out + Dng 1 ghi s t cn dng, nu ko i c th ghi 0 v ko cn thc hin tip. + Dng tip ghi s biu hin cho s t cn dng cho mi loi. Bi 3: Cho hnh ch nht n.m vung, mi cha 1 s nguyn. C th di chuyn t 1 sang thuc ct bn phi cng dng hoc chnh lch 1 dng. Tm cch di chuyn t ct 1 n ct n sao cho tng cc s cc i qua l nh nht. - D liu vo: Dng 1 l 2 s m,n; m dng tip theo mi dong cha n s. - Kt qu: Ghi ra tng, ch s cc t ct 1 n ct n. Bi 4: Tm dy con chung di nht: Cho hai dy a1,a2,an v b1,b2,..bn. Tm 1 dy di nht nhn c t a v b bng cch xo i 1 s phn t trong a hoc b. - D liu vo: dy a, dy b - D liu ra: Dy c. Bi 5: C n cuc hp nh s t 1 n n ng k lm vic ti 1 phng hi tho. Cuc hp i cn c bt u ti thi im a[i] v kt thc ti thi im b[i] (i=1,2,n), 2 cuc hp bt k ch c nhn phc v nu cc khong thi gian lm vic tng ng ch giao nhau ti u mt. Hy tm 1 lch cho phng hi tho c th phc v c nhiu cuc hp nht. - D liu vo: + Dng 1 ghi n + Dng th i trong s n dng tip ghi 2 s a[i], b[i] - D liu ra: + Dng 1 ghi gi tr k l s cuc hp ti a c th c + k dng tip theo, mi dng ghi s hiu ca cuc hp c phc v theo trnh t b tr Bi 6: Cho mt tam gic s. a ra tng ln nht c th i t trn xung. 7 3 8 8 1 0 - 13 -

 cng n tp mn Tin hc 2 7 4 4 4 5 2 6 5 Bi 7: Tr chi bng s: C mt hnh ch nht c chia lm n vung nh s t tri qua phi bt u t 1. Trn vung th i ngi ta ghi 1 s nguyn dng a[i], i=1,2,..,n. mi lt chi, ngi tham gia tr chi c quyn la chn mt s lng tu cc trn bn s. Gi s theo th t t tri qua phi, ngi chi la chn cc i1,i2,,ik. Khi im s m ngi chi t c l a[i1] - a[i2] ++ (-1)^(k-1)*a[ik] - D liu: + Dng u cha s nguyn dng n (n<=10^6) l s lng ca bng s + Dng th 2 cha n s nguyn dng a1,a2,,an (ai<=10^4) ghi trn bng s. - Kt qu: Mt s nguyn duy nht l s im ln nht m ngi chi c th t c. Bi 8: Mua v: C N ngi sp hng mua v d bui ho nhc. Ta nh s h t 1 n N theo th t ng trong hng. Mi ngi cn mua mt v, song ngi bn v c php bn cho mi ngi ti a hai v. V th, mt s ngi c th ri hng v nh ngi ng trc mnh mua h v. Bit ti l thi gian cn thit ngi i mua xong v cho mnh. Nu ngi i+1 ri khi hng v nh ngi i mua h v th thi gian ngi th i mua c v cho c hai ngi l ri. Yu cu: Xc nh xem nhng ngi no cn ri khi hng v nh ngi ng trc mua h v tng thi gian phc v bn v l nh nht. D liu: - Dng u tin cha s N (1 N 60000). - Dng th 2 ghi N s nguyn dng t1, t2, ..., tN. (1 ti 30000) - Dng th ba ghi N-1 s nguyn dng r1, r2, ..., rN-1. (1 ri 30000) Kt qa: In ra tng thi gian phc v nh nht.

- 14 -