eggdropping.cc

template <typename T>
T worstCase(T p_psxCount, T p_floorCount) {
    Cache<T> cache;

    auto min = [](T a, T b) { return (a < b) ? a : b; };
    auto max = [](T a, T b) { return (a > b) ? a : b; };
    auto memo_W = [&cache](T n, T k, auto &&W) {
        return (cache.count({n,k}) > 0) ? cache[{n,k}] : cache[{n,k}] = W(n,k,W);
    };

    // https://en.wikipedia.org/wiki/Dynamic_programming#Egg_dropping_puzzle
    // W(n,k) = 1 + min{max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k }
    auto W = [&](T n, T k, auto&& W)->T {
        T L = 1, R = k, x, least = std::numeric_limits<T>::max();

        if (k == 0) return 0; // W(n, 0) = 0
        if (n == 1) return k; // W(1, k) = k

        while (L <= R) { // Binary Search
            x = (L+R) >> 1;
            T n1 = memo_W(n - 1, x - 1, W); // W(n − 1, x − 1) -> BROKEN
            T n2 = memo_W(n, k - x, W);     // W(n, k - x) -> NOT BROKEN

            if (n1 > n2) {
                R = x - 1;
                least = min(least, n1);
            } else {
                L = x + 1;
                least = min(least, n2);
            }
        }

       return 1 + least; // W(n,k) = 1 + ...
    };

    return W(p_psxCount, p_floorCount, W);
}