מתוך מבחנים לאפלייד מטריאלס – 3

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

לבדיקת התאמה

פתרון: השיטה היא לעשות קפיצות גדולות ואם כדור אחד נשבר אז לבצע קפיצות של 1 בין השלבים עם הכדור השני, בכדי שלא נעלה במס' הזריקות שאנו מבצעים, כל קפיצה גדולה תהיה קטנה ב- 1 מהקפיצה הקודמת. סכום מס' השלבים שמורידים בקפיצה הגדולה צריך להיות בסביבות ה-100  ולכן הקפיצה הראשונה תהיה של 14 שלבים. מס' הזריקות המינימלי הוא 14.