Algorithm

 Problem Statement for GridCut

     Problem link- https://community.topcoder.com/stat?c=problem_statement&pm=5936&rd=8077

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.

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

class GridCut {
  int solve(int width, int height, int n) {
    int r1 = 0, r2 = 0;
    
    if(width * height == n)
      return 0;
    
    if(width > height)
      swap(width, height);

    int rem = n % width;
    
    if(n > width * height - width)
      r1 = width - rem + 1;
    else if(rem == 0)
      r1 = width;
    else
      r1 = width + 1;

    int mx = 0;
    for(int i = 1; i <= width; ++i)
      if(n >= i * i)
        mx = i;

    int tmp = n;
    n -= mx * mx;

    if(mx == width) {
      n %= width;
      if(tmp > width * height - width)
        r2 = width - n + 1;
      else if(n == 0)
        r2 = width;
      else
        r2 = width + 1;
    } else {
      int plus = n >= mx;
      if(plus)
        n -= mx;
      n = max(0, n);

      if(mx + plus == width) {
        if(mx + 1 == height) {
          if(n == 0) {
            r2 = width;
          } else {
            r2 = width - n + 1;
          }
        } else {
          r2 = width + 1;
        }
      } else {
        if(n == 0)
          r2 = mx + (mx + plus);
        else
          r2 = mx + (mx + plus) + 1;
      }
    }

    return min(r1, r2);
  }
  
public:
  int cutLength(int width, int height, int n) {
    return min(solve(width, height, n), solve(width, height, width * height - n));
  }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4
2
3

Output

x
–
+
cmd
3
Advertisements

Demonstration

TopCoder Solution SRM280-D1-500  Problem Statement for GridCut C,C++, Java, Js and Python ,SRM280-D1-500,TopCoder Solution