Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package com.java;
- import java.util.HashMap;
- import java.util.Map;
- import java.util.Objects;
- public class EggsFloorsSecondAttempt {
- 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;
- EggsFloorsSecondAttempt.EggDrops eggDrops = (EggsFloorsSecondAttempt.EggDrops) o;
- return eggs == eggDrops.eggs &&
- drops == eggDrops.drops;
- }
- @Override
- public int hashCode() {
- return Objects.hash(eggs, drops);
- }
- }
- private static Map<EggsFloorsSecondAttempt.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;
- }
- EggsFloorsSecondAttempt.EggDrops eggDrops = new EggsFloorsSecondAttempt.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 <= floors; ++i) {
- if (getNumberFloors(eggs, i) >= floors) return i;
- }
- throw new RuntimeException("Something is wrong here!");
- }
- public static int getFirstDroppingFloor(int eggs, int floors) {
- int lo = 1;
- int hi = floors;
- int s;
- int s_min = 0;
- int wc = Integer.MAX_VALUE;
- while(lo < hi){
- s = (lo + hi) / 2;
- int b = getMinimumEggDrops(eggs - 1, s - 1);
- int nb = getMinimumEggDrops(eggs, floors - s);
- if(b == nb) break;
- int wc1 = 1 + Math.max(b, nb);
- if(wc1 < wc) {
- wc = wc1;
- s_min = s;
- }
- else if(b > nb) {
- hi = s - 1;
- }
- else {
- lo = s + 1;
- }
- }
- return s_min;
- }
- 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(getFirstDroppingFloor(2, 36)); // prints 9 wrong should be 8 or 14
- System.out.println(getFirstDroppingFloor(3, 100)); // prints 25
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement