מריה בוטוסוב

יש בניין בעל 100 קומות. אם ביצה נופלת מקומה n ומעלה, היא נשברת. אם מטילים אותה מקומה מתחת ל - n, היא לא נשברת. נותנים לך 2 ביצים. צריך למצוא n, כאשר מפחיתים את הכמות הזריקות במקרה הגרוע.

נגיד, להתחלה, שאנחנו נזרוק את הביצה מקומה 10 ואחרי זה מקומה 20...

 - אם ביצה 1 נשברה בהטלה ראשונה (קומה 10), יש לנו 10 הטלות סה''כ.

 - אם ביצה 1 נשברת בהטלה אחרונה (קומה 100), אז מקסימום יהיו 19 הטלות (קומות 30,20,10,...,100,90)

זה חישוב סבבה, ומספיק טוב, אבל לקחנו בחשבון רק מקרה קצה הגרוע ביותר. אנחנו יכולים לעשות "איזון עומסים", כדי לעשות שתי המקרים האלה יותר שווים.

המטרה שלנו -  לייצר מערכת להטלת ביצה 1 עם מספר ההטלות עקבי ככל האפשר: אם ביצה נשברת בזריקה ראשונה או אחרונה.

1. במערכת המושלמת, (מספר זריקות של ביצה 1)  + (מספר של זריקות של ביצה 2) תהיה תמיד זהה, ללא קשר איפה ביצה 1 נשברה.

2. כדי לעשות את זה, אם זריקה של ביצה 1 תקח יותר שלב, ביצה 2 תקח פחות.

3. לכן, אנחנו חייבים להקטין מספר שלבים פוטנציאליים של ביצה 2 בזריקה אחד כל פעם. למשל, אם ביצה 1 נזרקה מקומה 20, ולכן מקומה 30, ביצה 2 פוטנציאלית צריכה 9 שלבים. כאשר אנחנו נזרוק ביצה 1 שוב, אנחנו צריכים להקטין כמות שלבים של ביצה 2 ל - 8. לכן, אנחנו צריכים לזרוק ביצה 1 מקומה 39!

4. לכן, ביצה 1 צריכה בפעם ראשונה להיות נזרקת מקומה x, לכן, לעלות ל x-1, אחר כך ל x-2...

5. צריך לפתור את זה:

ברור גם ש x חייב להיות מספר שלם.

אם אנחנו לעגל אותו ל 14, אנחנו נעלה  14 קומות,אחרי זה לעלה עוד 13, אחרי זה נעלה עוד 12... המכפיל אחרון יהיה 4 וזה יהיה בקומה 99.

אם אנחנו נעגל ל 13, המכפיל האחרון יהיה 1 וזה יקרה בקומה 91. כלומר, זריקה אחד שנשארה לנו - איננה מספיקה.

לכן, אנחנו צריכים לעגל ל 14, ללכת לקומה 14,אחר כך ל 27, אחר כך ל 39... 14 שלבים לכל היותר.

int breakingPoint = ...;
int countDrops = 0;
 
bool drop(int floor) {
    countDrops++;
    return floor >= breakingPoint;
}
 
int findBreakingPoint(int floors) {
    int interval = 14;
    int previousFloor = 0;
    int egg1 = interval;
    
    //Drop egg1 at decreasing intervals
    while (!drop(egg1) && egg1 <=floors) {
        interval-=1;
        previousFloor = egg1;
        egg1 += interval;
    }
    
    //Drop egg2 at 1 unit increments
    int egg2 = previousFloor + 1;
    while (egg2 < egg1 && egg2 <= floors && !drops(egg2)) {
        egg2 +=1;
    }
    //If didn't break, return -1
    return egg2 > floors ? -1 : egg2;
}