# Cut The Paper

Posted: 8 Jan, 2021
Difficulty: Hard

## PROBLEM STATEMENT

#### Note:

``````1. Square is a quadrilateral whose all four sides are of equal length.
2. If the given paper is already a square then it is possible to cut the whole square in one move.
``````
##### Input Format:
``````The first line of the input contains an integer T, denoting the number of test cases.

The first line of each test case consists of two space-separated integers N and M denoting the dimensions of the given paper, in a separate line.
``````
##### Output Format:
``````For each test case return, the minimum number of squares in which you can cut the given paper.
``````
##### Note:
``````You don't have to print anything, it has already been taken care of. Just Implement the given function.
``````
##### Constraints:
``````1<= T <= 50
1<= N, M <= 150

Time Limit: 1 sec.
`````` Approach 1
• In order to try all possible ways to cut the paper, we make a recursive function that will compute the answer for the given (N, M).
• The base condition for this function will be when N==M (which means it is already a square), we will return 1 in such a case.
• In the case where the base condition is not satisfied, we will try out all possible ways to cut the paper horizontally and vertically as follows:
• For trying all possible horizontal cuts, we will find the answer for paper with dimensions (N-x, M) and (x, M) for x in the range from 1 to N/2(both inclusive) with the help of the same recursive function. And the summation of results from both calls for a given x will give one of the possible solutions.
• For trying all possible vertical cuts, we will find the answer for paper with dimensions (N, M-x) and (N, x) for x in the range from 1 to M/2(both inclusive) with the help of the same recursive function. And the summation of results from both calls for a given x will give one of the possible solutions.
• Taking the minimum of all possible solutions for given (N, M) will give the desired solution.
• One thing to observe here is that we can reach a state more than once for eg. the state (N-2, M-1) can be reached from (N-2, M) and (N-1, M-1).
• In order to avoid recomputation of solutions for a given state, we can use a 2-Dimensional table to store the results for a state, so that we can use those results for future calls to that state.
• There is one edge case for paper with dimension 13*11. Our algorithm will give 8 as the answer but since we can cut the paper in 6 squares only as shown in the following picture.

Eg. For paper with dimension (2, 3), the algorithm will work as follows:

• HELPER(2, 3)
• HELPER(1, 3)
• HELPER(1,2)
• HELPER(1,1)
• Return 1                                          ....(1)
• Return 1                                          ....(2)
• Return 2 (sum of (1) + (2))                        ….(3)