Problem Link:
Click Here
Difficulty:
Easy
Prerequisite:
Binary - Search
Problem:
Given the length and breadth of a rectangle and a number N. Find the minimum length of a square that can fit all the N rectangles in it. Rectangles cannot be rotated.
Explanation:
This a classic binary search problem, the first idea you should have got to use binary search is that if a square of size S fits all the N rectangles then the square of size S + 1 will also fit all the rectangles in it.
So we need to find a value such that after that value every square of the side that value will fit all the rectangles in it.
So can achieve this by binary search,
We will take value min as something will never be able to fit all the N rectangles and max as something that will always be able to fit all the N rectangles in it.
We will take min as 0 and max as N * max( length, breadth ).
Then we will binary search for the value that will be able to fit all the N rectangles.
Way to achieve that is to take mid = min + max / 2 if mid is able to fit all the N rectangles then it means the value we want is less than or equal to mid or else it is greater than mid so in the first case, we change max to mid and in the latter case, we change min to mid.
Now to check if a particular value fits all the rectangles N we think this as follows:
Let the size of the square be S, if S/length * S/breadth \geq N then it will be able to fit N rectangles.
Here S/length represents the rectangles we are able to fill vertically in the square of size S, and S/breadth represents rectangles we are able to fill horizontally and their product represents all the rectangles we are able to fill in the square. If this value is greater than N then square of this side will be able to fill all N rectangles.
Setters Code
#include
using namespace std;
typedef unsigned long long ll;
int check(ll side, ll w, ll h, ll n) {
if((side/h) * (side/w) >= n) return 1;
else return 0;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 0;
cin >> t;
while(t--) {
ll n = 0, w = 0, h = 0;
cin >> n >> h >> w;
ll area = n * w * h;
ll mx = 0;
mx = max(h, w) * n;
ll mn = 0;
// cout << mx < mn + 1) {
ll mid = (mx + mn)/2;
if(check(mid, w, h, n)) {
mx = mid;
}
else mn = mid;
// cout << mx << " " << mn << endl;
}
cout << mx << endl;
}
return 0;
}