My approach :-

1. x and y is the length of the rectange so we need length and breadth closer to x and y respectively.

2. Initialy let len1=-1, len2=-1, br1=-1, br2=-1 . Then we will get len1 = c * (x/c),
len2 = c * (x/c+1) , br1 = c * (y/c), br2 = c * (y/c +1).

3. if any of the len or br gets equal to 0 than we will discard it from further calculation . target = x * y .

4. finally we will find (val1 * br1) , (val1 * br2), (val2 * br1) and (val2 * br2). Select the one which is closest to the target.

My Code :-

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll compare(ll a,ll b,ll tar,ll ans)
{
if(a!=-1&&b!=-1)
{
ll val = a*b;
ll curr=abs(val-tar);
ll old=abs(ans-tar);

//cout<<"curr and old are "<<curr<<" "<<old<<endl;
//cout<<curr<<" "<<old<<endl;

ans = (curr<old)? val:ans;
}
//cout<<ans<<endl;
return ans ;
}

int main()
{

int t ; cin>>t;
for(int i=0;i<t;i++)
{
ll x,y,c; cin>>x>>y>>c;
ll val1=-1,val2=-1,val3=-1,val4=-1;

if(x%c==0)
{
val1=x;
}
else
{
ll z=x/c;
val1=z*c; z++; val2=z*c;
if(val1==0)
val1=-1;
}
if(y%c==0)
{
val3=y;
}
else
{
ll z=y/c;
val3=z*c; z++; val4=z*c;
if(val3==0)
val3=-1;
}

ll ans = LLONG_MAX ;
ll tar=x*y;

/* cout<<"val1, val2 , val3 , val4 , tar, ans "
<<val1<<" "<<val2<<" "<<val3<<" "<<val4<<" "
<<tar<<" "<<ans<<" "<<endl; */

ans = compare(val1,val3,tar,ans);
ans = compare(val1,val4,tar,ans);
ans = compare(val2,val3,tar,ans);
ans = compare(val2,val4,tar,ans);

cout<<ans<<endl;

}

return 0;
}


I haven’t implemented it yet, but what I would do is:

1. calculate area of rectangle
2. calculate area of one square
3. divide area of rectangle by area of square
4. Round to nearest whole number
1 Like

Thanks

Here is an efficient way in Tyl language,
getcloser gets the closest side value
getarea cascades from the trivial areas to the approximate

input _testnum
testnum number.of _testnum

i testnum ~
input numa
input numb
input numc

print getarea numa numb numc
ᐤ

getarea a b c »
ma math.mod a c
mb math.mod b c
ea not ma
eb not mb

ea • eb ?
a • b
⇋
ea ?
a • getcloser b c mb
⇋
eb ?
b • getcloser a c ma
⇋
result getcloser a c ma
result •• getcloser b c mb
ᐤ
ᐤ
ᐤ

getcloser num div mod »
div2 div ÷ 2
mod <= div2 ?
div • math.floor num ÷ div
⇋
div • math.ceil num ÷ div
ᐤ

Note that your specification says that you should match the area as closely as possible, not the length and breadth.

So if you have (X,Y,C) = (14,9,5), the closest match on dimensions would imply you want 6 squares in a 3\times 2 layout . However the rectangle area is 14\times 9 = 126 which is closely matched by using 5 squares, 5\times 5^2 = 125, which you will not find by your process.

1 Like