PROBLEM STATEMENT:
We are given a number of eggs and number of floors of a building. We are to drop the eggs from the floors and see if it breaks or not.
We have to determine the minimum number of attempts to determine the threshold floor. Threshold floor means from all the floors above this floor, if we drop an egg, it will break down. That means this is the floor from where the eggs starts breaking excluding this floor. We have to break minimum number of eggs while performing the experiment and we will determine the answer considering the worst case. If one egg that doesn't break, we can use it again, but the egg which breaks down, we can't use it again.
QUICK POINTS:
1. We have to start from bottom, because if we start from the top, we will run out of eggs before getting the proper answer.
2. We can use a egg again and again until it breaks down.
3. We have to minimize the number of attempts i.e. minimum drops to get the threshold floor.
4. If we have only one floor, then in worst case, we can perform only one attempt from the first floor. If we have only one egg, then we have to start from 1st floor and in worst case, number of attempts will be equal to number of floors.
5. The conditions of zero floor and zero number of eggs are not valid. You can observe it wisely.
CODE:
#include <bits/stdc++.h>
using namespace std;
int solve(int e,int n)
{
if(n==0 || n==1)
return n;
if(e==1)
return n;
int mn=INT_MAX;
for(int k=1;k<=n;k++)
{
int temp=1+max(solve(e-1,k-1),solve(e,n-k));
mn=min(mn,temp);
}
return mn;
}
int main()
{
int n,e;
cin>>n>>e;
int c=solve(e,n);
cout<<c;
return 0;
}
0 Comments