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; } }