Number of rectangles
- anonymous
- Aug 10, 2015
- 2 min read
NUMBER OF RECTANGLES
Q. A rectangular grid measuring 3 by 2 contains eighteen rectangles. For each testcase an integer target would be entered by the user. In many cases it is not possible to get the exact grid therefore it is essential to consider those rectangular grids such that the number of rectangles contained in the grid is nearest to target. Out of these rectangular grids output the area of the rectangular grid having the largest area.
Sample output:
Testcases = 2
Target = 10
grid 1 = 1*4
grid 2 = 4*1
Largest area = 4
Target = 16
grid 1 = 1*5
grid 2 = 5*1
grid 3 = 2*3
grid 4 = 3*2
Largest area = 6
[endif]--
Solution:
This program deals with the use of a formula to find out number of rectangles in a rectangular grid. The issue is when the exact rectangular grid is improbable, so let’s consider an example to know how the program deals with such cases e.g. when target is 16. The grid 1×5 and 5×1 contains 15 rectangles and the grids 2×3 and 3×2 contain 18 rectangles each.
All other rectangular grids either contain rectangles less than 15 or more than 18.
Hence the set of grids containing the number of rectangles nearest to target are 1×5, 5×1, 2×3 and 3×2. Out of these, 2×3 and 3×2 are the grids having the largest area equal to 6.
Hence 6 is the answer as it is the largest area in the set of rectangular grids being considered.
Code:
#include<iostream>
#define MAX 50
using namespace std;
int main()
{
int i,j,h,k,b,tr,a[MAX];
long int t;
cout<<"Testcases = ";
cin>>t;
while(t>0)
{
k=0;
h=0;
cout<<"\nTarget = ";
cin>>tr;
for(i=1;i<100;i++)
{
for(j=1;j<100;j++)
{
if( (4*tr)==(i*(i+1)*j*(j+1)) )
{
a[k]=(i*j);
k++;
cout<<"grid "<<k<<" = "<<i<<" * "<<j<<endl;
}
}
}
if(k==0)
{
for(b=1;;b++)
{
for(i=1;i<100;i++)
{
for(j=1;j<100;j++)
{
if( 4*(tr-b)==(i*(i+1)*j*(j+1)) )
{
a[k]=(i*j);
k++;
cout<<"grid "<<k<<" = "<<i<<" * "<<j<<endl;
}
}
}
if(k>0)
{
break;
}
}
for(b=1;;b++)
{
for(i=1;i<100;i++)
{
for(j=1;j<100;j++)
{
if( 4*(tr+b)==(i*(i+1)*j*(j+1)) )
{
a[k]=(i*j);
k++;
cout<<"grid "<<k<<" = "<<i<<" * "<<j<<endl;
h=1;
}
}
}
if(h==1)
{
break;
}
}
}
h=a[0];
for(i=0;i<k;i++)
{
if(h<a[i])
{
h=a[i];
}
}
cout<<"Largest area = "<<h<<endl;
t--;
}
return 0;
}
![endif]--
![endif]--
Comentários