@@ -18,21 +18,21 @@ class Solution {
1818
1919private:
2020bool check (int n,int K,int N) {
21- // let f(n, K) be the max number of floors could be solved by n moves and K eggs,
22- // we want to do binary search to find min of n, s.t. f(n, K) >= N,
23- // if we use one move to drop egg with X floors
24- // 1. if it breaks, we can search new X in the range [X+1, X+ f(n-1, K-1)]
25- // 2. if it doesn't break, we can search new X in the range [X- f(n-1, K), X-1 ]
26- // => f(n, K) = (X+f(n-1, K-1 ))-(X-f(n-1, K))+1 = f(n-1, K-1 )+f(n-1, K)+1
27- // => (1) f(n, K) = f(n-1, K) +1+f(n-1, K-1)
28- // (2) f(n, K-1) = f(n-1, K-1)+1+f(n-1, K-2)
29- // let g(n, K) = f(n, K)-f(n, K-1), and we subtract (1) by (2)
30- // => g(n, K) = g(n-1, K)+g(n-1, K-1), obviously, it is binomial coefficient
31- // => C(n, K) = g(n, K) = f(n, K)-f(n, K-1),
32- // which also implies if we have one more egg with n moves and x-1egges , we can have more C(n, x) floors solvable
33- // => f(n, K) = C(n, K)+f(n, K-1) = C(n, K) + C(n, K-1) + ... + C(n, 1) + f(n, 0) = sum(C(n, k) for k in [1, K])
34- // => all we have to do is to check sum(C(n, k) for k in [1, K]) >= N,
35- // if true, there must exist a 1-to-1 mapping from each F in [1, N] to eachsucess and failure sequence of every C(n, k) combinations for k in [1, K]
21+ // let f(n, K) be the max number of floors could be solved by n moves and K eggs,
22+ // we want to do binary search to find min of n, s.t. f(n, K) >= N,
23+ // if we use one move to drop egg with X floors
24+ // 1. if it breaks, we can search new X in the range [X- f(n-1, K-1), X-1 ]
25+ // 2. if it doesn't break, we can search new X in the range [X+1, X+ f(n-1, K)]
26+ // => f(n, K) = (X+f(n-1, K))-(X-f(n-1, K-1 ))+1 = f(n-1, K)+f(n-1, K-1 )+1
27+ // => (1) f(n, K) = f(n-1, K) +1+f(n-1, K-1)
28+ // (2) f(n, K-1) = f(n-1, K-1)+1+f(n-1, K-2)
29+ // let g(n, K) = f(n, K)-f(n, K-1), and we subtract (1) by (2)
30+ // => g(n, K) = g(n-1, K)+g(n-1, K-1), obviously, it is binomial coefficient
31+ // => C(n, K) = g(n, K) = f(n, K)-f(n, K-1),
32+ // which also implies if we have one more egg with n moves and x-1eggs , we can have more C(n, x) floors solvable
33+ // => f(n, K) = C(n, K)+f(n, K-1) = C(n, K) + C(n, K-1) + ... + C(n, 1) + f(n, 0) = sum(C(n, k) for k in [1, K])
34+ // => all we have to do is to check sum(C(n, k) for k in [1, K]) >= N,
35+ // if true, there must exist a 1-to-1 mapping from each F in [1, N] to eachsuccess and failure sequence of every C(n, k) combinations for k in [1, K]
3636int total =0 , c =1 ;
3737for (int k =1 ; k <= K; ++k) {
3838 c *= n - k +1 ;