Giáo trình Olimpic lập trình

Öt l¹i b¶ng A ta thªm b»ng c¸c sè 0. C¸c phÇn tö ®øng ë c¸c dßng vµ cét ®· ®−îc 
®¸nh dÊu trong c¸c m¶ng B hoÆc C , tøc lµ : 
 If B[i]=1 or C[j]=1 then A[i,j]=0 
Cã thÓ ®Ò xuÊt c¸ch gi¶i kh¸c chØ cÇn sö dông mét m¶ng phô C[1:n]. Trong c¸c tr−êng hîp ®ã m¶ng A sÏ 
®−îc xÐt theo c¸c dßng. C¸c cét cã chøa c¸c phÇn tö 0 vÉn ®−îc ®¸nh dÊu trong m¶ng C nh− tr−íc, cßn cã 
gÆp hay kh«ng sè 0 trong dßng ®ang xÐt ®−îc ®¸nh dÊu trong biÕn z, tøc lµ 
 If A[i,j]=0 then C[j]=1 ; z=1 
Sau khi xem xÐt dßng i, nã sÏ ®−îc cho b»ng 0 nÕu z=1. Cuèi cïng xÐt m¶ng C vµ cho b»ng 0 c¸c cét j mµ 
VIETBOOK 
Trang 28 
C[j]=1. Ch−¬ng tr×nh nµy ®−îc ®−a ra ë 88.5 
C¸c lçi phæ biÕn khi gi¶i bµi nµy lµ : 
1. 1. Xem xÐt m¶ng A, vµ nÕu phÇn tö A[i,j]=0 th× cho b»ng 0 hoÆc dßng i, hoÆc cét j, hoÆc c¶ hai c¸i ®ã. Khi 
xem xÐt tiÕp tôc c¸c phÇn tö ®· ®−a vÒ b»ng 0 ®−îc coi lµ b»ng 0 tõ ®Çu vµ dÉn ®Õn c¸c b−íc ®−a vÒ 0 kh«ng 
cÇn thiÕt. 
2. Xem xÐt m¶ng A, vµ nÕu A[i,j]=0, th× ®−a j vµo phÇn tö C[k] tiÕp theo. Tõ ®ã cïng víi c¸c chØ sè j cã thÓ 
®−îc ®−a ®i nhiÒu lÇn, vµ m¶ng C cã thÓ cÇn ®é dµi m*n tr¸i víi gi¶ thiÕt. 
VIETBOOK 
Trang 29 
lêi gi¶i b»ng ng«n ng÷ pascal 
olimpic 80.1.1 
( In ra c¸c sè nguyªn tè nhá h¬n n) 
program oli8011; 
CONST 
 N=200; 
LABEL 
 BR,LB; 
VAR 
 m,i,,j,k,q : integer ; 
 p : array[1..n] of integer; 
BEGIN 
 write('M:= '); 
 readln(m); 
 writeln(' Chuong trinh lay gia tri cua m= ',m); 
 if (m>=2) then 
 writeln(2); 
 if (m>=3) then writeln(3); 
 k:=1; p[k]:=3; i:=5; 
 while i<=m do 
 begin 
 for j:=1 to k do 
 begin 
 q:=p[j] 
 if (q*q>i) then goto br; 
 if (i mod q= 0) then goto np; 
 end; 
 if k=n then 
 begin 
 i:=m-1; 
 write(' Cac so con lai '); 
 writeln(' Khong the tinh toan chinh xac'); 
 end 
else 
 br: begin 
 writeln(i); 
 if (k<= n-1) then 
VIETBOOK 
Trang 30 
 begin 
 k:=k+1; 
 p[k]:=i ; 
 end; 
 end; 
np: i:=i+2; 
end; 
readln; 
END. 
olimpic 80.1.2 
(in ra cac so hoan vi) 
PROGRAM OL8012; 
CONST 
 mm=100; 
VAR 
 m, i, j, k, n : integer; 
 a, p : array[1..mm] of integer; 
BEGIN 
 write('m:='); 
readln(m); 
writeln(' chuong trinh nay lay gia tri m=',m); 
for i:=1 to m do 
 begin 
 write('a[',i,']='); 
 readln(a[i]); 
 p[i]:= i; 
 end; 
for i:=1 to m do write(a[i],' '); 
writeln; 
readln; 
for i:=m-1 downto 1 do 
if (p[i]<p{i+1]) then 
 begin 
 n:=p[i]; 
 for j:=m downto i do 
 if (n<p[j]) then 
 begin 
 p[i]:= p[j]; 
 p[j]:=n; 
 k:=1; 
 while i+k<m-k+1 do 
VIETBOOK 
Trang 31 
 begin 
 n:=p[i+k]; 
 p{i+k]:=p[m+1-k]; 
 p[m+1-k]:=n; 
 k:=k+1; 
 end; 
j:=i; 
end; 
for i:=1 to m do write(a[p[i]],''); 
writeln; 
end; 
readln; 
END. 
OLIMPIC 80.1.3 
(n©ng bËc nhanh) 
PROGRAM OLI8013; 
VAR 
 a, b : real; 
 k, n : integer; 
BEGIN 
 written(' a,k= '); readln(a,k); 
 write(a,' mu ',k,' = '); 
 b:=1; 
while k>0 do 
begin 
 n:=k div 2; 
 if (n+n<k) then 
 b:=b+a; 
 k:=n; 
 a:=a*a; 
end; 
writeln(b); 
readln; 
END. 
olimpic 80.1.4 
(nh÷ng phÐp tÝnh sè häc) 
PROGRAM OL8014; 
CONST 
 M=1; 
VIETBOOK 
Trang 32 
 N=9; 
LABEL r; 
var 
 i, j, k, y : integer; 
 a,b : array[1..n] of integer; 
BEGIN 
 b[1]:=1; 
 k:=0; 
 a[2]:=0 ; 
 for i:=3 to n do 
 a[i]:=4; 
 r: 
for i:=n downto 2 do 
 if a[i]=4 then 
 a[i]:=1 
 else 
begin 
 a[i]:=a[i]+1; 
 y:=b[i-1]; 
 case a[i] of 
1 : b[i]:=y+i; 
2 : b[i]:=y-i 
3 : b[i]:=y*i; 
4 : b[i]:=y div i; 
end; 
for j:=i+1 to n-1 do 
b[j]:=b[j-1]+j; 
if (b[n] m) then 
goto r; 
 k:=k+1; 
 for j:=2 to n-1 do 
 write('('); 
 write('1'); 
 for j:=2 to n do 
begin 
 if (j>2) then 
 write(')'); 
case a[j] of 
1: write('+'); 
2: write('-'); 
3: write('*'); 
4: write('%'); 
VIETBOOK 
Trang 33 
end; 
write(j); 
end; 
writeln('=',m); 
goto r; 
end; 
writeln(k); 
readln; 
END. 
olimpic 80.2.1 
{T×m kiÕm nh÷ng ph©n tö b»ng nhau} 
PROGRAM OLI8021 
 LABEL 
 F; 
 VAR 
 i, j, p, q, b: integer; 
 a : array[1..2,1..15 ] of real; 
 ff : boolean; 
 BEGIN 
 for j:=1 to 15 do 
 begin 
 write('a[1,',j,']:=');readln(a[1,j]); 
 write('a[2,',j,']:=');readln(a[2,j]); 
 end; 
 ff:=false; 
 for i:=1 to 2 do 
 for j:=1 to 15 do 
 for p:=i to 2 do 
 begin 
 if i<p then 
 b:=1 else 
 b:=j+1; 
 for q:=p to 15 do 
 if (a[i,j]= a[p,q]) then 
 begin 
 ff:=true; 
 goto f; 
 end; 
 end; 
VIETBOOK 
Trang 34 
 F: 
 if ff then 
 writeln('a[',i,',',j,']=a[',p,',',q,']') 
 else 
 writeln('------'); 
 END. 
olimpic 80.2.2 
(tæng c¸c b×nh ph−¬ng) 
PROGRAM OLI8022; 
 VAR 
 m, i, j: integr; 
 ff :boolean; 
 BEGIN 
 write('m:='); 
 readln(m); 
 writeln('chuong trinh nay lay gia tri m=',m); 
 i:=1; ff:=true; 
 while (2*i*i<=m) and ff do 
 begin 
 j:= round(sqrt(m-i*i)); 
 if (i*i+j*j=m) then 
 ff:=false else 
 i:=i+1; 
 end; 
 if ff then 
 write('net') else 
 writeln(i,'*',i,'+',j,'*',j,'=',m); 
END. 
OLIMPIC 80.2.3 
( nh÷ng sè kh¸c nhau) 
PROGRAM OLI8023; 
CONST 
 n=100; 
VAR 
 m, i, j, s: integer; 
 b : bolean 
 a : array[1..n] of integer; 
BEGIN 
 write('m:='); 
 readln(m); 
VIETBOOK 
Trang 35 
 writeln(' Ch−¬ng tr×nh lÊy gi¸ trÞ m =',m); 
 for i:=1 to m do 
 begin 
 write('a[',i,']:='); 
 readln(a[i]); 
 end; 
 s:=0; 
 for i:=1 to m do 
 begin 
 b:=false; j:=i+1; 
 while(j<=m) and not b do 
 begin 
 b:=b or (a[i])= a[j]); 
 j:=j+1; 
 end; 
 if not b then 
 s:=s+1; 
 end; 
 writeln(s); 
END. 
OPLIMPIC 80.3.2 
(M+1 TROng hÖ ®Õm c¬ sè hai) 
PROGRAM OLI8032; 
VAR 
 n, i, j: integer; 
 b : boolean ; 
BEGIN 
 write('n:='); 
 readln(n); 
 b:=true; 
 for i:=1 to n do 
 begin 
 readln(j); 
 if b then 
 writeln(' ',1-j); 
 else 
 writeln(' ',j); 
 if j=0 then 
 b:= false 
VIETBOOK 
Trang 36 
 end; 
 if b then 
 writeln(' 1 '); 
 readln; 
END. 
OLIMPIC 80.3.3 
(MAX cu¶ min) 
PROGRAM OLI8033; 
CONST 
 mm=10; 
 nn=20; 
LABEL 
 si; 
VAR 
 i, j, k, m, n: integer 
 x: : array[1..mm,1..nn] of integer; 
 min,max: integer; 
BEGIN 
 write('m:='); 
 readln(m); 
 write('n:='); 
 readln(n); 
 for i:=1 to m do 
 for j:=1 to n do 
 begin 
 write('x[',i,',',j,']='); 
 readln(x[i,j]); 
 end; 
 for i:=1 to m do 
 begin 
 for 
j:=1 to n do 
 begin 
 if (i>1) and (x[i,j ]<=max) then 
 goto si; 
VIETBOOK 
Trang 37 
 if (j=1) or (x[i,j]<=min) then 
 min:=x[i,j]; 
end; 
max:=min; 
k:=i; 
si; 
end; 
writeln(k); 
readln; 
END. 
OLIMPIC 80.3.4 
(ho¸n vÞ c¸c sè 0, 1, 2) 
PROGRAM OLI8034; 
CONST 
 mm=100; 
TYPE 
el=0..2; 
VAR 
 i,n: integer; 
 a: array[el] of 0..nn; 
 x: array[1..nn] of el; 
BEGIN 
 write('n:='); readln(n); 
 writeln('Chuong trinh lay gia tri n=',n); 
 for i:=1 to n do 
 readln(x[i]); 
 writeln; 
 a[0]:=0; a[1]:=0; a[2]:=0; 
 for i:=1 to n do 
 a[x[i]]:=a[xi]]+1 
 for i:=1 to n do 
 if i<=a[0] then 
 x[i]:=0 
 else 
 if i<=n-a[2] then 
 x[i]:=1 
 else 
 x[i]:=2; 
 for i:=1 to n do 
 writeln(x[i]); 
VIETBOOK 
Trang 38 
END. 
OLIMPIC 81.1 
(hµm sè) 
PROGRAM OLI811; 
VAR 
 n, i, j: integer; 
BEGIN 
 write('n:='); readln(n); 
 writeln('Chuong trinh lay gia tri n=',n); 
 i:=1; j:=0; 
 while n>0 do 
 begin 
 if n mod 2=0 then 
 i:=i+j; 
else 
 j:=j+i; 
 n:= n div 2; 
 end; 
 writeln(j); 
END. 
OLIMPIC 81.2 
(béi bèn sè) 
PROGRAM OLI812; 
LABEL 
 BRJ,VSJO; 
VAR 
 n, i, j, k, p:integer; 
 i1, j1, k1, p1: integer; 
 b: boolean; 
begin 
 for n:=2 to maxint do 
 begin 
 b:=false; 
 for i:=1 to trunc(sqrt(n)) do 
 begin 
 for j:=1 to i do 
 begin 
 if 
VIETBOOK 
Trang 39 
i*i+j*j>=n then 
 goto 
brj; 
 for 
k:=1 to j do 
 if 
i*i+j*j+k*k<n then 
begin 
 p:=trunc(sqrt(n-i*i-j*j-k*k)); 
 if 
(i*i+k*k+j*j+p*p=n) and (p<=k) then 
 begin 
 if (b) then 
 goto vsjo; 
 i1:=i; j1:=j; k1:=k; p1:=p; 
 b:=true; 
 end; 
end; 
 end; 
 brj; 
 end; 
 end; 
 vsjo; 
 writeln(i*i+j*j+k*k+p*p,'='); 
 write(i,'*',i' + ',j,'*',j,' + ',k,'*',k,' + ',p,'*',p,' = '); 
 writeln(i1,'*',i1' + ',j1,'*',j1,' + ',k1,'*',k1,' + ',p1,'*',p1); 
 readln; 
END. 
PLIMPIC 81.3 
{H×nh xo¸y tr«n èc} 
PROGRAM OLI813; 
CONST 
 NN=19; 
VIETBOOK 
Trang 40 
VAR 
 i, j, k, n: integer; 
 a : array[1..nn,1..nn] of integer; 
FUNCTION MOV: BOOLEAN ; 
 begin 
 mov:=false; 
 if k<=n*n then 
 begin 
 a[i,j]:=k; 
 k:=k+1; 
 mov:=true; 
 end; 
end; 
BEGIN 
 write('n:='); 
 readln(n); 
 k:=1; i:=1; j:=1; 
 repeat 
 while mov and (i+j<n+1) do j:=j+1; k:=k-1; 
 while mov and (i<j) do i:=i+1; k:=k-1; 
 while mov and (i+j>n+1) do j:=j-1; k:=k-1; 
 while mov and (i>j+1) do i=i-1; k:=k-1; 
 until k=n*n; 
 for i:=1 to n do 
 begin 
 for j:=1 to n do 
 writeln(a[i,j]:4); 
readln; 
 end 
END. 
olimpic 81.4 
{ c¸c sè lËp tõ c¸c ch÷ sè kh¸c nhau} 
PROGRAM OLI814; 
var 
 i, j, k, m: integer; 
begin 
 for i:=1 to 9 do 
 for j:=0 to 9 do 
 if ij then 
 for 
k:=0 to 9 do 
VIETBOOK 
Trang 41 
 if (ki) and (kj) then 
 for m:=0 to 9 do 
 if (mi) and (mj) and (mk) then 
 writeln(((i*10+j)*10+k*10)+m); 
end. 
olimpic 81.5 
{lo¹t c¸c sè kh«ng} 
PROGRAM OLI815; 
const 
 nn=100; 
var 
 n, i, t, max: integer; 
 a: array[1..nn] of real; 
begin 
 write('N:='); readln(n); 
 for i:=1 to n do 
 begin 
 if a[i]0 then 
 begin 
 if (max<t) then max:=t; 
 t:=0; 
 end 
 else t:=t+1; 
 end; 
 if max<t then max:=t; 
 writeln; 
 writeln(max); 
end. 
OLIMPIC 82.1 
{ h×nh ch÷ nhËt} 
PROGRAM OLI821; 
CONST 
 mm=100; 
 nn=100; 
var 
 m, n, i, j, s: integer; 
VIETBOOK 
Trang 42 
 a : array[0..mm,0..nn] of byte; 
begin 
 write(' M,N:=');readln(m,n); 
 for i:=0 to m do 
 for j:=0 to n do 
 if (i=0) or (j=0) then 
 a[i,j]:=0 else 
 begin 
 write('A[',i,',',j,']:='); 
 readln(a[i,j]); 
 end; 
 s:=0; 
 for i:=1 to m do 
 for j:=1 to n do 
 if (a[i,j]=1) and (a[i-1,j]+a[i,j-
1]=0) then 
 s:=s+1; 
 writeln(s); 
END. 
OLIMPIC 82.2 
( S