import java.util.*;

public class EggsFloors {
    private static class EggDrops {
        private int eggs;
        private int drops;

        public EggDrops(int eggs, int drops) {
            this.eggs = eggs;
            this.drops = drops;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EggDrops eggDrops = (EggDrops) o;
            return eggs == eggDrops.eggs &&
                    drops == eggDrops.drops;
        }

        @Override
        public int hashCode() {
            return Objects.hash(eggs, drops);
        }
    }


    private static Map<EggDrops, Integer> floorCache = new HashMap<>();

    public static int getNumberFloors(int eggs, int drops) {
        if(eggs <= 0 || drops <= 0) {
            return 0;
        }
        if(eggs == 1) {
            return drops;
        }
        if(drops == 1) {
            return 1;
        }

        EggDrops eggDrops = new EggDrops(eggs, drops);
        if(floorCache.containsKey(eggDrops)) {
            return floorCache.get(eggDrops);
        }

        int result = getNumberFloors(eggs - 1, drops - 1) + 1 + getNumberFloors(eggs, drops - 1);
        floorCache.put(eggDrops, result);
        return result;
    }

    public static int getMinimumEggDrops(int eggs, int floors) {
        for(int i = 1; i <= 200; i++) {
            getNumberFloors(eggs, i);
        }

        int min = Integer.MAX_VALUE;
        int drops = 0;
        for(Map.Entry<EggDrops, Integer> entry: floorCache.entrySet()) {
            if(entry.getKey().eggs != eggs) continue;
            if(entry.getValue() < min && entry.getValue() >= floors && drops < entry.getValue()) {
                min = entry.getValue();
                drops = entry.getKey().drops;
            }
        }
        return drops;
    }

    public static int getWorseCaseDropsForBreaking(int startFloor, int eggs, int floors) {
        return 1 + Math.max(getMinimumEggDrops(eggs - 1, startFloor - 1), getMinimumEggDrops(eggs, floors - startFloor));
    }

    public static int getFirstBreakingFloor(int eggs, int floors) {
        int minDrops = Integer.MAX_VALUE;
        int firstBreakingFloor = Integer.MAX_VALUE;
        for(int s = 1; s <= floors; s++) {
            int worseCaseDrops = getWorseCaseDropsForBreaking(s, eggs, floors);
            if(minDrops > worseCaseDrops) {
                minDrops = worseCaseDrops;
                firstBreakingFloor = s;
            }
        }
        return firstBreakingFloor;
    }
    public static void main(String[] args) {
        System.out.println(getMinimumEggDrops(2, 100)); // prints 14 correct
        System.out.println(getMinimumEggDrops(3, 100)); // prints 9 correct
        System.out.println(getFirstBreakingFloor(2, 36)); // prints 33 wrong
        System.out.println(getFirstBreakingFloor(3, 100)); // prints 8 wrong
    }
}