Thread: CEOI 1996 example solution

  1. #1
    Registered User
    Join Date
    Oct 2006
    Posts
    2

    Question 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.

  2. #2
    Registered User SKeane's Avatar
    Join Date
    Sep 2006
    Location
    England
    Posts
    234
    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?

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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.

  4. #4
    Registered User
    Join Date
    Oct 2006
    Posts
    2
    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();
    	}
    }

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 'Solution' and 'Project' usage in VC++
    By C+/- in forum C++ Programming
    Replies: 2
    Last Post: 01-13-2007, 09:50 AM
  2. Solution to earlier quad-tree culling
    By VirtualAce in forum Game Programming
    Replies: 3
    Last Post: 08-10-2006, 08:04 PM
  3. anyone know the solution?
    By heeroyung in forum C Programming
    Replies: 15
    Last Post: 09-30-2005, 06:46 AM
  4. My Unix/Linux SECURITY SOLUTION - pls read
    By bjdea1 in forum Linux Programming
    Replies: 3
    Last Post: 04-11-2004, 09:28 PM
  5. For those of you who helped - thanks! SOLUTION
    By BigDaddyDrew in forum C++ Programming
    Replies: 0
    Last Post: 03-11-2003, 10:42 PM