Eggs and Building in C programming

Eggs and Building 

Level: Difficult
You are given 'k' eggs and a 'n' storey building. The eggs MIGHT break if thrown down from a specific height (Note: It is NOT necessary that the eggs have to break; they might not even break from the topmost floor). What is the minimum number of steps in which you can find (using 'k' eggs) the minimum height of the floor in the building from which the eggs will start breaking ?

Note: You have to output the minimum number of steps required; NOT the floor of the building from which eggs will break;

Input Format: 
First line of the input is an integer 'q':
1 <= q <= 1,000, which is the number of queries.

Second line of the input has two space separated integers: the height of the building 'n' and the number of eggs which you can use 'k':
1 <= n <= 1,000
1 <= k <= 10

Output Format: 
For each q output a single line denoting the minimum number of trials required to find the height from which the eggs will start breaking.


Example: 
For n = 151 and k = 1 the minimum number of steps in which we can find the height from which eggs can break(considering the worst case) is 151. This is because since we have only 1 egg we have no choice but to start from the first floor and throw the egg from each floor and check whether it breaks or not. In worst case this might require 151 steps.

For n = 100 and k = 2 the minimum number of steps in which we can find the height from which eggs can break(considering again the worst case) is 14. This is because suppose we throw the FIRST egg from 14th floor and it breaks then we will have to try each of the remaining 13 floors using the remaining egg. So in this case number of trials required is 14. Suppose the first egg doesn't break then we can drop it from 27th floor (13 + 14). We have chosen 27th floor because suppose if the first egg breaks from 27th floor then we will have to test floors from 15-26 (=12). So, the total number of trials required in this case is: 12 + 1(from 14th floor) + 1(from 27th floor) = 14 trials. Suppose the first egg doesn't break even now, drop it from 39(12 + 13 + 14) floor for same reason. 


InputOutput
Test Case 1
4
10 1
10 2
100 2
104 3

10
4
14
9
Test Case 2
3
923 8
23 9
101 2

10
5
14
Test Case 3
5
42 8
35 1
70 5
79 9
63 5

6
35
7
7
7
Test Case 4
10
42 8
335 1
170 5
479 9
963 5
706 6
282 8
962 2
996 3
828 7

6
335
8
9
11
10
9
44
19
10
Test Case 5
20
42 8
335 1
170 5
479 9
963 5
706 6
282 8
962 2
996 3
828 7
392 5
903 4
293 3
422 7
719 6
448 7
772 9
870 3
668 10
36 5

6
335
8
9
11
10
9
44
19
10
10
13
12
9
10
9
10
18
10
6
Test Case 6
100
42 8
335 1
170 5
479 9
963 5
706 6
282 8
962 2
996 3
828 7
392 5
903 4
293 3
422 7
719 6
448 7
772 9
870 3
668 10
36 5
704 2
323 4
674 5
142 2
254 9
548 5
663 8
38 10
724 2
530 9
317 6
191 3
289 7
41 3
265 9
447 6
891 10
371 1
7 2
394 9
630 4
85 5
757 1
967 7
932 9
945 10
627 4
538 9
119 3
930 2
834 6
640 9
705 1
978 7
674 7
22 6
925 3
271 10
778 4
98 3
987 1
162 7
356 8
656 5
32 3
351 1
942 5
967 1
108 2
8 8
458 8
754 4
946 10
210 9
222 9
423 7
507 1
414 9
901 2
763 6
411 10
625 8
549 4
596 2
603 1
292 7
375 1
597 2
349 10
669 5
282 5
54 10
419 9
901 9
128 8
729 4
649 4
808 2
311 8
814 5

6
335
8
9
11
10
9
44
19
10
10
13
12
9
10
9
10
18
10
6
38
10
11
17
8
10
10
6
38
10
9
11
9
6
9
9
10
371
4
9
12
7
757
10
10
10
12
10
9
43
10
10
705
11
10
5
18
9
12
9
987
8
9
11
6
351
11
967
15
4
9
12
10
8
8
9
507
9
42
10
9
10
11
35
603
9
375
35
9
11
9
6
9
10
8
12
12
40
9
11


Source Code:

(Dynamic Programming is used to create function, it has exponential complexity so the error is coming "Time limit Exceeded" program is only working for < 15 floors )

# include <stdio.h>

# include <limits.h>

 int EGGS = 0;
 int FLOORS = 000;
int array[10000][10000];
// A utility function to get maximum of two integers
int max(int a, int b) { return (a > b)? a: b; }

/* Function to get minimum number of trails needed in worst
  case with n eggs and k floors */

/*************Function 1*********
int eggDrop(int n, int k)
{
    // If there are no floors, then no trials needed. OR if there is
    // one floor, one trial needed.
    if (k == 1 || k == 0)
        return k;

    // We need k trials for one egg and k floors
    if (n == 1)
        return k;

    int min = INT_MAX, x, res;

    // Consider all droppings from 1st floor to kth floor and
    // return the minimum of these values plus 1.
    for (x = 1; x <= k; x++)
    {
        res = max(eggDrop(n-1, x-1), eggDrop(n, k-x));
        if (res < min)
            min = res;
    }
    return min + 1;
}
*/
/********** Function 2*************/
int omlette(const int e, const int f)
{
    // basic cases or rare cases only. i say such cases are rare as i like Manhattan
    if (e == 1) return f;
    if (f == 0) return 0;
    if (f == 1) return 1;
    
    // Memoization at work. to check if we have already calculated a value.
    if ( array[e][f] >= 0 )
            return array[e][f];
    // initialize minimum number of drops to number of floors 
    int min = f;
    for (int n = 1; n <= f; ++n)
        {      
            const int a = omlette(e-1, n-1);//drop from floor n. If it breaks,test floors 1 to n-1 with e-1 eggs.
       
            const int b = omlette(e, f-n); // If it doesn't break,test floors n+1 to f with e eggs.
       
            const int c = 1 + (a > b ? a : b);// find worst case number of drops. since 1 drop already used.
       
            min = (c < min ? c : min); // minimum for all n.
        }
    array[e][f] = min; // Memoization of the result
   return min;
}

/****************Function 3***********
int eggDrop(int n, int k)
{
    // If there are no floors, then no trials needed. OR if there is
    // one floor, one trial needed.
    if (k == 1 || k == 0)
        return k;
    // We need k trials for one egg and k floors
    if (n == 1)
        return k;
    int min = INT_MAX, x, res;
    // Consider all droppings from 1st floor to kth floor and
    // return the minimum of these values plus 1.
    for (x = 1; x <= k; x++)
    {
        res = max(eggDrop(n-1, x-1), eggDrop(n, k-x));
        if (res < min)
            min = res;
    }
    return min + 1;
}
*/
/* Driver program to test to pront printDups
k ==> Number of floors
  n ==> Number of Eggs*/
   
int main()
{
    int n = 2,i,val, k = 10,arr[1000];
    scanf("%d",&val);
    for(i=0;i<val*2;i++)
    {
    scanf("%d",&arr[i]);
    }
     for(i=0;i<val*2;i=i+2)
    {//printf("%d",arr[i+1]);
    FLOORS=arr[i];
    EGGS=arr[i+1];
    for (int f = 1; f <= FLOORS; ++f)
            array[1][f] = f;
   
    for (int e = 2; e <= EGGS; ++e) // making sure of the rare case
        {
            array[e][1] = 1; // With just 1 floor we only need one drop.
            array[e][0] = 0; // With zero floors we don't need any drops.
        }
    // rest of array is made -1. Will be used later for computation. these are frequent cases
    for (int e = 2; e <= EGGS; ++e)
            for (int f = 2; f <= FLOORS; ++f)
                array[e][f] = -1;
    printf ("%d\n" ,omlette(arr[i+1],arr[i]));
   //printf ("%d\n" ,eggDrop(arr[i+1],arr[i]));
  
    }
    return 0;
}

Source Code 2:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <math.h>

#define egg 10
#define floor 1000

/*
 *----------------------------------
 * Function that returns the maximum of a and b
 *----------------------------------
 */
int max(int a, int b){
 if(a > b){
  return a;
 }
 return b;
}

/*
 *----------------------------------
 * Function that returns the minimum of a and b
 *----------------------------------
 */
int minimum(int a, int b){
 if(a < b){
  return a;
 }
 return b;
}

int main(){
 int matrix[floor+1][egg+1];
 memset(matrix, 0, sizeof(matrix)); /* initialize matrix to 0 */

 /*
  * We fill the initial values in the matrix
  * If there are 0 eggs, then we cannot solve the problem.
  * We set matrix[i][0] = INT_MAX to indicate that it takes
  * infinitely many queries
  */
 for(int i=0; i<=floor; i++){
  matrix[i][0] = INT_MAX;
 }

 /* 
  * if there are 0 floors, then you need only 0 queries
  * if there is exactly 1 floor, then you need 1 query
  */
 for(int i=0; i<=egg; i++){
  matrix[0][i] = 0;
  matrix[1][i] = 1;
 }
 
 /*
  * if there is only 1 egg, then you need i queries to
  * determine the floor (starting from the top and going down,
  * stopping at the highest (first) floor where the egg
  * breaks. 
  */
 for(int i=0; i<=floor; i++){
  matrix[i][1] = i; 
 }


 int temp, min;
 

 /*
  *------------------------------------------------
  * Now we come to the main recurrence:
  *
  * Suppose the total number of floors is "floor", and the
  * total number of eggs is "egg"
  *
  * We try to find the minimum number of eggs needed if the
  * highest floor is numbered i, and we have j eggs in our
  * hands. 
  *
  * We can pick a floor k <= i and throw an egg from floor
  * k. There are two possibilities - 
  *
  * 1. The egg breaks. In this case, the lowest floor at which
  * the egg can break is either k or lower, and you now have to
  * solve this problem with j-1 eggs.
  *
  * 2. The egg does not break. In this case, the lowest floor
  * at which the egg breaks is higher than k - that is, it is
  * among i-k floors, and you have j eggs to solve the problem.
  *
  * We don't know whether the egg will break or not. However,
  * we know that in the worst case, the number of eggs needed
  * if we try at floor k is the greater of 1 and 2.  
  *            cost(k) = max(1,2)
  *
  * The optimal way to solve the problem if the highest floor
  * is i, is to pick a k which minimizes the cost.
  *         optcost(i) = min{cost(k) | 0 <= k <= i}
         *-------------------------------------------------------
  */
 for(int j=2; j<=egg; j++){
  for(int i=2; i<=floor; i++){
   min = INT_MAX;
   for(int k=1; k<=i; k++){
    temp = 1 + max(matrix[k-1][j-1], 
            matrix[i-k][j]);
    min = minimum(min, temp);
   }
   matrix[i][j] = min;
  }
 }


 int query, n, k;
 scanf("%d", &n):
 
 while(query--){
  scanf("%d%d",&n,&k); 
  printf("%d\n", matrix[n][k]);
 }
 return 0;
}




Labels: , , , , , ,