H
hai6f2009
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Con kiến (Đề thi Olympic 30/4 năm 2012)
Trên một sân hình chữ nhật MxN, được chia thành các ô vuông đơn vị, mỗi ô chứa một lượng thức ăn. Một con kiến xuất phát từ ô (1,1) muốn đi qua sân để đến dòng thứ M. Con kiến chỉ có thể đi theo một dòng chia nhỏ trên sân ứng với một dòng của bảng chữ nhật hoặc đi theo trên một cột của sân. Hãy chỉ ra đường đi giúp con kiến có được nhiều thức ăn nhất.
Input: file FOOD.INP gồm:
- Dòng 1 chứa 2 số M và N
- M dòng tiếp theo, mỗi dòng chứa N số là lượng thức ăn trên mỗi ô vuông đơn vị.
Output: file FOOD.OUT gồm:
- Dòng đầu chứa lượng thức ăn nhiều nhất mà con kiến có thể ăn được.
- Dòng 2 lần lượt chứa từng cặp (x,y) là vị trí dòng và cột của ô mà con kiến đi qua.
Ví dụ:
FOOD.INP: 3 5
7 3 8 1 5
8 8 3 14 1
6 15 19 1 1
FOOD.OUT:45
(1,1)(2,1) (2,2) (2,3) (3,3)
còn đây là chương trình của mình:
program food;
const fi='food.inp';
fo='food.out';
var f:text;
m,n,cs,l,r,gtln:integer;
a,b,h,c:array [0..10000,0..10000] of integer;
s,p:array [1..10000] of integer;
procedure enter;
var i,j:integer;
begin
assign(f,fi);reset(f);
readln(f,m,n);
for i:=1 to m do
begin
for j:=1 to n do read(f,a[i,j]);
readln(f);
end;
close(f);
end;
function max(a,b:integer):integer;
begin
if a>b then exit(a) else exit(b);
end;
procedure optimize;
var i,j:integer;
begin
h[1,1]:=0;c[1,1]:=0;
for j:=1 to n do
b[1,j]:=a[1,j]+b[1,j-1];
for i:=2 to m do
b[i,1]:=a[i,1]+b[i-1,1];
for i:=2 to m-1 do
for j:=2 to n do
begin
if b[i-1,j]>b[i,j-1] then
begin
b[i,j]:=b[i-1,j]+a[i,j];
h[i,j]:=i-1;
c[i,j]:=j;
end
else begin
b[i,j]:=b[i,j-1]+a[i,j];
h[i,j]:=i;
c[i,j]:=j-1;
end;
end;
end;
procedure trace;
var i,j,k,d:integer;
begin
assign(f,fo);rewrite(f);
gtln:=b[m-1,1]+a[m,1];
for j:=2 to n do
if b[m-1,j]+a[m,j]>gtln then
begin
gtln:=b[m-1,j]+a[m,j];
cs:=j;
h[m,j]:=m-1;
c[m,j]:=j;
end;
writeln(f,gtln);
d:=0;i:=m;j:=cs;
while (i>0) and (j>0) do
begin
write(f,'(',i,',',j,')',' ');
i:=h[i,j];
j:=c[i,j];
end;
close(f);
end;
BEGIN
enter;
optimize;
trace;
END.
Trên một sân hình chữ nhật MxN, được chia thành các ô vuông đơn vị, mỗi ô chứa một lượng thức ăn. Một con kiến xuất phát từ ô (1,1) muốn đi qua sân để đến dòng thứ M. Con kiến chỉ có thể đi theo một dòng chia nhỏ trên sân ứng với một dòng của bảng chữ nhật hoặc đi theo trên một cột của sân. Hãy chỉ ra đường đi giúp con kiến có được nhiều thức ăn nhất.
Input: file FOOD.INP gồm:
- Dòng 1 chứa 2 số M và N
- M dòng tiếp theo, mỗi dòng chứa N số là lượng thức ăn trên mỗi ô vuông đơn vị.
Output: file FOOD.OUT gồm:
- Dòng đầu chứa lượng thức ăn nhiều nhất mà con kiến có thể ăn được.
- Dòng 2 lần lượt chứa từng cặp (x,y) là vị trí dòng và cột của ô mà con kiến đi qua.
Ví dụ:
FOOD.INP: 3 5
7 3 8 1 5
8 8 3 14 1
6 15 19 1 1
FOOD.OUT:45
(1,1)(2,1) (2,2) (2,3) (3,3)
còn đây là chương trình của mình:
program food;
const fi='food.inp';
fo='food.out';
var f:text;
m,n,cs,l,r,gtln:integer;
a,b,h,c:array [0..10000,0..10000] of integer;
s,p:array [1..10000] of integer;
procedure enter;
var i,j:integer;
begin
assign(f,fi);reset(f);
readln(f,m,n);
for i:=1 to m do
begin
for j:=1 to n do read(f,a[i,j]);
readln(f);
end;
close(f);
end;
function max(a,b:integer):integer;
begin
if a>b then exit(a) else exit(b);
end;
procedure optimize;
var i,j:integer;
begin
h[1,1]:=0;c[1,1]:=0;
for j:=1 to n do
b[1,j]:=a[1,j]+b[1,j-1];
for i:=2 to m do
b[i,1]:=a[i,1]+b[i-1,1];
for i:=2 to m-1 do
for j:=2 to n do
begin
if b[i-1,j]>b[i,j-1] then
begin
b[i,j]:=b[i-1,j]+a[i,j];
h[i,j]:=i-1;
c[i,j]:=j;
end
else begin
b[i,j]:=b[i,j-1]+a[i,j];
h[i,j]:=i;
c[i,j]:=j-1;
end;
end;
end;
procedure trace;
var i,j,k,d:integer;
begin
assign(f,fo);rewrite(f);
gtln:=b[m-1,1]+a[m,1];
for j:=2 to n do
if b[m-1,j]+a[m,j]>gtln then
begin
gtln:=b[m-1,j]+a[m,j];
cs:=j;
h[m,j]:=m-1;
c[m,j]:=j;
end;
writeln(f,gtln);
d:=0;i:=m;j:=cs;
while (i>0) and (j>0) do
begin
write(f,'(',i,',',j,')',' ');
i:=h[i,j];
j:=c[i,j];
end;
close(f);
end;
BEGIN
enter;
optimize;
trace;
END.
Last edited by a moderator: