Clash Wildcard - Nobita and Boxes (CLWI21C) - EDITORIAL

editorial
,
1

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();
}
2 Likes