SOURCE

// function findBrokenFloor(N, K) {
//     let bf = setEggBrokenFloor(N)
//     let dropCount = dropEgg(0, N, K, bf)
//     console.log("Droped " + dropCount + " times")
// }

// function dropEgg(startF, endF, eggsLeft, target) {
//     if(eggsLeft == 1) {
//         for(let i = startF; i <= endF; i ++) {
//             console.log("Droped at " + i)
//             if(i == target) {
//                 console.log("Egg broken at floor " + i)
//                 return i - startF + 1;
//             }
//         }
//     } else {
//         let midF = parseInt((startF + endF)/2)
//         console.log("Droped at " + midF)
//         if(midF == target) { 
//             console.log("Egg broken at floor " + midF)
//             return 1
//         } else if (midF > target) {
//             return dropEgg(startF, midF - 1, eggsLeft-1, target) + 1
//         } else {
//             return dropEgg(midF + 1, endF, eggsLeft-1, target) + 1
//         }
//     }
// }

// function setEggBrokenFloor(N) {
//     let timestamp = new Date().getTime();
//     // 时间戳除以N的余数，此时 蛋碎
//     let ret = timestamp%N 
//     console.log("Egg will break at floor " + ret)
//     return ret
// }


// findBrokenFloor(20, 3)

let memo = {}

function dropEgg(N, eggsLeft) {
    if(eggsLeft == 1) return N
    if(N == 0) return 0
    
    if(memo[N]) return memo[N]
    let ret = 10000000
    for(let i = 1; i < N+1; i ++) {
        ret = Math.min(ret, Math.max(dropEgg(i-1, eggsLeft -1) + 1, dropEgg(N - i, eggsLeft) + 1))
    }
    memo[N] = ret
    return ret
}

let times = dropEgg(100, 2)
console.log("Need drop at most " + times + " times")