56 lines
1.6 KiB
Java
56 lines
1.6 KiB
Java
import java.util.Scanner;
|
|
|
|
/**
|
|
* EggDropping
|
|
* You are given k identical eggs and you have access to a building with n
|
|
* floors labeled from 1 to n.
|
|
*
|
|
* You know that there exists a floor f where 0 <= f <= n such that any egg
|
|
* dropped at a floor higher than f will break,
|
|
* and any egg dropped at or below floor f will not break.
|
|
*
|
|
* Each move, you may take an unbroken egg and drop it from any floor x (where 1
|
|
* <= x <= n).
|
|
* If the egg breaks, you can no longer use it. However, if the egg does not
|
|
* break, you may reuse it in future moves.
|
|
*
|
|
* Return the minimum number of moves that you need to determine with certainty
|
|
* what the value of f is.
|
|
*
|
|
* Example 1:
|
|
*
|
|
* Input: k = 1, n = 2
|
|
* Output: 2
|
|
* Explanation:
|
|
* Drop the egg from floor 1. If it breaks, we know that f = 0.
|
|
* Otherwise, drop the egg from floor 2. If it breaks, we know that f = 1.
|
|
* If it does not break, then we know f = 2.
|
|
* Hence, we need at minimum 2 moves to determine with certainty what the value
|
|
* of f is.
|
|
*
|
|
*/
|
|
public class EggDropping {
|
|
public static void main(String[] args) {
|
|
Scanner scanner = new Scanner(System.in);
|
|
|
|
int a = scanner.nextInt();
|
|
int b = scanner.nextInt();
|
|
scanner.close();
|
|
System.out.println(minMoves(a, b));
|
|
}
|
|
|
|
private static int minMoves(int k, int n) {
|
|
// if n > f ==> eggs break
|
|
// if n < f ==> eggs are good
|
|
int min = 0;
|
|
int[][] dp = new int[n + 1][k + 1];
|
|
while (dp[min][k] < n) {
|
|
min++;
|
|
for (int i = 1; i <= k; i++) {
|
|
dp[min][i] = dp[min - 1][i - 1] + dp[min - 1][i] + 1;
|
|
}
|
|
}
|
|
return min;
|
|
}
|
|
}
|