Problem link : Nobita and Boxes

Author : Saurabh

Tester: Prajwal

**Difficulty:** Easy-Medium

**Prerequisite:** Binary search

**Problem**:

You need to find minimum length of cube so that you can

fit n cuboids of l,b,h where all cuboids faces are

parallel to cube faces and all cuboids have same orientation.

## Hint1

Linearly iterating on side of the cube would be slow.

Think a faster solution.

## Hint2

Think of a function which is a non-decreasing function.

## Hint3

Apply binary search on the cube side to get the answer.

## Explanation

The main observation in this question is that there is a Minimum

value of the cube C such that all cubes of side X>=C can fit

all the cuboids while X<C dont fit the cuboids.

So we apply binary search on the side of the cube to find

the minimum value C.

```
//For given constraints max value of cube can be 1e6 so right=1e6
Let left=0,right=1e6
while(left+1<right){
X=(right-left)/2+left;
//No. of cuboids you can fit in X side cube is
// (X/l)*(X/b)*(X/h)
if((X/l)*(X/b)*(X/h)>=n){
right=X;
}
else left=X;
}
```

So we will have our required value in variable **right**.

**Solution link**: Solution

## Setters solution

```
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll l,b,h,n;
bool f(ll x){
return (x/l)*(x/b)*(x/h)>=n;
}
void solve(){
cin>>l>>b>>h>>n;
ll l=0,r=1e6;
while(l+1<r){
ll m=(r-l)/2+l;
if(f(m)){
r=m;
}
else l=m;
}
cout<<r<<endl;
}
int main(){
ll t;
cin>>t;
while(t--)
solve();
}
```