Có một hcn M x N , mỗi lần ta được phép cắt một hcn thành 2 hcn con theo chiều ngang hoặc dọc , và tiếp tục cắt các hcn cho đến khi thành hình vuông thì dừng .
Yêu cầu : tìm cách cắt thành ít ô vuông nhất

HCN.INP

10 2

HCN.OUT

5( Số lượng hình vuông min )

Code:

Const fi='bai.inp'; fo='bai.out';
 Var n,m:Integer;
    f:array[1..100,1..100] Of Integer;
    f1,g:text;
Procedure doctep;
 Begin
  Assign(f1,fi);
  Reset(f1);
  Readln(f1,n,m);
  Close(f1);
  Assign(g,fo);
  Rewrite(g);
 End;
Procedure xuly;
 Var a,b,i,j,c:Integer;
    res:Integer;
  Begin
  Fillchar(f,sizeof(f),0);
  For a:=1 to n do
    For b:=1 to m do
    Begin
      If a=b then
      Begin
        f[a,b]:=1;
        continue;
      End;
      res:=a*b;
    For c:=1 to a-1 do
      If res > (f[c,b]+f[a-c,b]) then
      res:=f[c,b]+f[a-c,b];
    For c:=1 to b-1 do
      If res > (f[a,c]+f[a,b-c]) then
      res:=f[a,c]+f[a,b-c];
    f[a,b]:=res;
    End;
  End;
Procedure xuat;
 Var i,j:Integer;
  Begin
  For i:=1 to n do
    Begin
    For j:=1 to m do
      Write(g,f[i,j]:3);
    Writeln(g);
    End;
  End;
Begin
 doctep;
 xuly;
 xuat;
 Writeln(g,f[n,m]:3);
 Close(g);
End.