Someone please explain me the logic behind this problem.

help
1
2

To answer this question, first you need to find the largest X such that squares of side X can exactly fit into a rectangle of sides M, N.

The following are some important observations:

  1. The squares should exactly fit inside the rectangle. Therefore, M and N both should be divisible by X.
  2. As the number of squares should be minimum, the side of the squares i.e. X has to be maximised.

From the above, it is clear that the required X is the GCD of M and N.

Finally, we have to find the number of squares of side X that fit into a rectangle of sides M, N. This is

(Area of rectangle) / (Area of one square) = (M * N) / (X * X)
2 Likes
3

Thanks… :slight_smile:

4

#include<stdio.h>
int main()
{

int i,n,N,M,T,j;
scanf("%d",&T);

for(j=0;j<T;j++)
{ int max=1;
scanf("%d%d",&N,&M);
n=NM;
for(i=1;(ii)<n;i++)
{
if(n % (ii)==0)
max=i;
}
printf("%d\n",n/(maxmax));

}

return 0;

}

5

The logic is simple.

First, lets take a look at problem. It says that “So your task is to find the minimum number of square plots that can be formed out of the rectangular plot.”

Firstly, we see that its a rectangular field and secondly, the number of square must be MINIMUM. (So thinking that M*N squares of 1x1 area is solution is wrong.) In other words, problem is asking us the MINIMUM number of squares (of greatest X which fits) which will fit in the rectangle.

Now, first thing. Area of Rectangle is MN.
Area of square is XX

Firstly, the solution is integral. ==>M*N must be divisible by X^2 (or X square, as we say).

Also, since square is inside the rectangle, ==> X <= min(M,N) (since if X is more than length or breadth, then it wont fit)

Lets say that the answer is m. ==> m * XX= MN
Thus, m= (MN)/(XX)
(in last para I will prove that this equation is further constrained to m = (M/X) * (N/X) where M/X AND N/X MUST BE integers.)
and m is minimum, and integral.

Many algos come to mind.

The best one is, as the first answer told, Is finding the GCD. In case you need code, PM me. Notice that it is a compulsory condition that length%x==0 AND breadth%x==0. To explain it, allow me to take a test case-

length=25, breadth =8.
link text
If we don’t apply the constraint of “length and breadth MUST BE divisible by X” then one may obtain an answer of 5 from his program. Because, 25*8=200, and 5 square divides it! One may get misled thinking that since 200/25=8, 8 squares will fit in here. But no, they wont. We can lay 5 squares across length, but then remaining breadth would be 3, and cant fit the 5 unit square. The reason why program may return 5 as answer is, because ANOTHER rectangle of SAME area is possible, WHICH CAN FIT 8 squares of 5 unit (dimensions of 40 x 5. ) . Hence, the condition of l & b being divisible by X is of utmost importance!

(And pls upvote if you find the answer satisfactory!)

EDIT: Its editorial is on discuss forum. here
EDITx2- Sorry I didn’t know editing brings Q to front page. I thought that adding editorial would complete this answer. Apologies :slight_smile: