TopCoder problem "GridCut" used in SRM 280 (Division I Level Two)



Problem Statement

    

On a piece of paper you draw a rectangular grid whose outer edges coincide with the edges of the paper. Every grid cell is exactly 1 unit by 1 unit. You can use scissors to cut out groups of cells along grid lines. The length of a cut is given as the number of units that the scissors need to travel along grid lines.

Given that the grid has dimensions width units by height units return the minimum length of a cut that cuts out exactly n cells from the piece of paper.

 

Definition

    
Class:GridCut
Method:cutLength
Parameters:int, int, int
Returns:int
Method signature:int cutLength(int width, int height, int n)
(be sure your method is public)
    
 

Constraints

-width will be between 1 and 1000 inclusive.
-height will be between 1 and 1000 inclusive.
-n will be between 1 and width*height inclusive.
 

Examples

0)
    
4
2
3
Returns: 3

We cut along the dotted lines to obtain the blue cells. The lengths of the dotted lines add up to 3.

1)
    
3
2
4
Returns: 2
2)
    
100
1
43
Returns: 1
Here we will never need more than one cut to cut away any number of squares.
3)
    
10
20
15
Returns: 8
4)
    
4
5
20
Returns: 0
All cells are used, so no cuts are needed.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5936

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8077&pm=5936

Writer:

dimkadimon

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Geometry