您所在位置：主题：[NOIP热身竞赛]方砖问题(顶楼公布正解)
maxumi
[专家分：2200] 发布于 2007-07-22 16:42:00
有一块n*n的大方砖(2<=n<=10000), 现要将其分成m块小正方形砖, 求m的最小值.
输入(bricks.in):
本题有多组测试数据, 每组测试数据占1行, 每行为一个数n.
输出(bricks.out):
每组输出占1行, 每行为一个数m.
样例输入:
2
3
5
9999
样例输出:
4
6
8
6
正解:
program lx;
var
i, n, p, min:word;
function calc(m, n:word): word;
begin
if n=0 then
calc:=0
else
calc:=m div n + calc(n, m mod n);
end;
begin
while not seekeof do begin
readln(n);
min:=maxint;
if n=1 then p:=1;
for i:=1 to n div 2 do begin
p:=2+calc(n-i, i) shl 1;
if min>p then min:=p;
end;
writeln(min);
end;
end.
输入(bricks.in):
本题有多组测试数据, 每组测试数据占1行, 每行为一个数n.
输出(bricks.out):
每组输出占1行, 每行为一个数m.
样例输入:
2
3
5
9999
样例输出:
4
6
8
6
正解:
program lx;
var
i, n, p, min:word;
function calc(m, n:word): word;
begin
if n=0 then
calc:=0
else
calc:=m div n + calc(n, m mod n);
end;
begin
while not seekeof do begin
readln(n);
min:=maxint;
if n=1 then p:=1;
for i:=1 to n div 2 do begin
p:=2+calc(n-i, i) shl 1;
if min>p then min:=p;
end;
writeln(min);
end;
end.
