GridCut
SRM 280 · 2005-12-28 · by dimkadimon
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.
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.
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.
3 2 4 Returns: 2
100 1 43 Returns: 1
Here we will never need more than one cut to cut away any number of squares.
4 4 4 Returns: 4
The most economical way is to cut out a 2 by 2 square.
10 20 15 Returns: 8
4 5 20 Returns: 0
All cells are used, so no cuts are needed.
Submissions are judged against all 180 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GridCut with a public method int cutLength(int width, int height, int n) · 180 test cases · 2 s / 256 MB per case