[mathjax]
Đề bài:
Thuật toán:
Với mỗi ô (i,j) với $i=1..m; j=1..n-1;$ kiểm tra xem ô (ii,jj) với $ii=1..i-1; jj=1..j;$ có đi được đến ô (i,j) không
- Nếu có
l[i,j]:=(l[i,j]+l[ii,jj]) mod base;
Kết quả: $\sum_{i=1}^{m}L[i][n]$
Code:
- Pascal (http://ideone.com/AburXq)
const fi='';
fo='';
maxn=100;
base=1000000000;
type arra=array[1..maxn,1..maxn] of integer;
arrl=array[1..maxn,1..maxn] of longint;
var a:arra;
i,j,m,n:byte;
l:arrl;
f:text;
res:int64;
procedure nhap;
begin
assign(f,fi);
reset(f);
readln(f,m,n);
for i:=1 to m do
for j:=1 to n do read(f,a[i,j]);
close(f);
end;
procedure init;
begin
for i:=1 to m do l[i,1]:=1;
res:=0;
end;
function kt(x,y:longint):boolean;
var tmp:longint;
begin
while y>0 do
begin
x:=x mod y;
tmp:=x;
x:=y;
y:=tmp;
end;
if x=1 then exit(false) else exit(true);
end;
procedure xuly;
var ii,jj:byte;
begin
for i:=1 to m do
for j:=1 to n-1 do
begin
for ii:=i-1 downto 1 do
for jj:=j downto 1 do
if kt(a[i,j],a[ii,jj]) then l[i,j]:=(l[i,j]+l[ii,jj]) mod base;
for jj:=j-1 downto 1 do
if kt(a[i,j],a[i,jj]) then l[i,j]:=(l[i,j]+l[i,jj]) mod base;
end;
for i:=1 to m do
for ii:=i downto 1 do
for jj:=n-1 downto 1 do
if kt(a[i,n],a[ii,jj]) then res:=(res+l[ii,jj]) mod base;
end;
procedure xuat;
begin
assign(f,fo);
rewrite(f);
writeln(f,res);
close(f);
end;
begin
nhap;
init;
xuly;
xuat;
end.
Recent Comments