 Clash Wildcard - Nobita and Boxes (CLWI21C) - EDITORIAL

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.

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