CEOI 1996 example solution

I would like to now the solution. I wrote a heuristic algorithm, but it is not write out the optimal solutions.
Please help.

Here is the example:
Click!

Cutting rectangle.

Quote:

---

You are given a rectangle whose side lengths are integer numbers. You want to cut the rectangle into the smallest number of squares, whose side lengths are also integer numbers. Cutting can be performed with a cutting machine that can cut only from side to side across, parallel with one side of the rectangle. Obtained rectangles are cut separately.
Input Data

The input file contains two positive integers in the first line: the lengths of the sides of the rectangle. Each side of the rectangle is at least 1 and at most 100.
Output Data

The output file consist of one line on which your program should write the number of squares resulting from an optimal cutting.
Example

CUTS.IN
5 6

CUTS.OUT
5

---

Apart from the fact that the question is ambiguous, what's your problem?

> Here is the example:
Nevermind someone elses answer, where is your attempt?

My first solution is divide with the little side of the rectangle, but that solution is not the optimal result. I think i have ti make it with dynamic programming with an array, but I don't know how to start it. I would like to know tha recursive algorithm which I have to use to fill the array with the solution. Than I search the optimal solution in the array...

here is the heuristic algorithm (but this is not the optima solutionl) i wrote it in Java:
i use an array to store the squares size and number of pieces.

Code:

---

import java.util.*;
import java.io.*;

public class feladat{
        private static int A;
        private static int B;       
        private static int F;
        private static int C=1;
        private static int[] D;
        private static int[] E;

        private static void ReadIn() throws IOException{
                BufferedReader in = new BufferedReader(new FileReader("in.txt"));
                StringTokenizer line;
                line = new StringTokenizer(in.readLine());
                A = Integer.parseInt(line.nextToken());
                B = Integer.parseInt(line.nextToken());
                in.close();
                D=new int[100];
                E=new int[100];
        }
      private static void Divide(int x, int y){
                if(x>y){F=x; x=y; y=F;}
                if(x==y){D[C]=1; E[C]=x;}
                else
                if((y%x) != 0){
                D[C]=y/x;
                E[C]=x;
                C++;
                Divide(y%x,x);
                }
                else
                {D[C]=y/x; E[C]=x; }
        }

        private static void POut() throws IOException{
                PrintWriter out=new PrintWriter(new BufferedWriter(new FileWriter("out.txt")));
                int m=0;
                for(int i=1; i<=C; i++){
                m +=D[i];
                }
                ki.println(m);
                for(int i=0; i<C; i++){
                ki.println(E[C-i]+" "+D[C-i]);
                }
                out.close();
        }

        public static void main(String[] args)throws Exception{
                ReadIn();
                DivideA,B);
                POut();
        }
}

---

So why are you posting Java code on a C++ board?
Moved.