# CEOI 1996 example solution

• 10-31-2006
bogabor
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.

Here is the example:
Click!

Cutting rectangle.
• 10-31-2006
SKeane
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?
• 10-31-2006
Salem
> Here is the example:
```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();         } }```