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.
This is a discussion on CEOI 1996 example solution within the Tech Board forums, part of the Community Boards category; I would like to now the solution. I wrote a heuristic algorithm, but it is not write out the optimal ...
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.
Apart from the fact that the question is ambiguous, what's your problem?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
> Here is the example:
Nevermind someone elses answer, where is your attempt?
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
I support http://www.ukip.org/ as the first necessary step to a free Europe.
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.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
I support http://www.ukip.org/ as the first necessary step to a free Europe.