... הבאה: בנוסף אומרים לנו את הדבר הבא: באפשרותך לבצע פעולה אחת בכל פעם, של הוספת הערך 1, כדי
להגדיל את כל המספרים, לערך הגדול ביותר, דהיינו, לבצע 9 פעולות של הגדלה ב 1, כנל. אבל כמו כן, באפשרותך ... בערך 1 ופעם אחת אחרונה, נגדיל רק ערך אחד בלבד, בערך 1, כי כבר אין ערכים נוספים שצריכים
להגדיל. ועד כאן הבנו, שיש לנו רשימת מספרים, שאנחנו צריכים ליישר קו
להגדיל את כל הערכים לערך הגדול ביותר, באמצעות פעולת הוספה של הערך 1 עד שכל הערכים יהיו זהים ערך הגדול ... ומחיר2 הוא 15, במקרה כזה השאלה היא, מה יהיה המחיר המינימאלי ההכרחי שנהיה חייבים לשלם, כדי
להגדיל את כל המספרים למספר הגדול ביותר? עד כאן הפירוש של השאלה... ועכשיו נצעד אל התשובה כך: אז איך בעצם ... את כל התהליך לחלקים הכי קטנים, לדוגמה כך: שואלים אותנו: נותנים לנו רשימת מספרים. עלינו
להגדיל את כל רשימת המספרים, אל המספר הגדול ביותר ברשימה. עלינו לעשות זאת באמצעות פעולת הוספה של הערך 1, ... נניח שהיו אומרים לנו, שלכל פעולת הוספה, יש מחיר1 כלשהו. והיו שואלים אותנו, כמה יעלה לנו
להגדיל את כל המספרים? האם היינו יודעים לפתור את זה? תשובה: כן. היינו פשוט סופרים את כל פעולות ההוספה של ... הרשימה, פעמיים. פעם ראשונה כדי לאתר את המספר הגדול ביותר. ורק אחר כך לעבור על כל הערכים
להגדיל אותם וכולי. אבל זאת לא כל האמת. כי בפועל, אפשרי לרוץ פעם אחת על כל הרשימה ולבצע בריצה אחת את ... לחלק קצת יותר קשה של השאלה, והוא, בהינתן רשימה של מספרים כנל, ובהינתן אפשרות אחת ויחידה
להגדיל את המספרים כנל, והיא באמצעות הגדלת 2 מספרים בכל פעם בבת אחת. דהיינו, שאנחנו חייבים
להגדיל בערך 1, אך ורק שני מספרים שונים בבת אחת. האם היינו יודעים לחשב את כמות הפעמים שניתן לבצע את ... לחשב, במידה ונבצע X הגדלות כפולות, כמה Y הגדלות בודדות נבצע. דהיינו, אם יש לנו צורך
להגדיל את כל המספרים נניח בסכום של 500. אז כעיקרון, במידה ונרצה לבצע כמה שיותר הגדלות כפולות, ורק לאחר ... ובהינתן לנו מחיר2 שהוא עלות של הגדלה כפולה, אז, מה יהיה המחיר המינימאלי שנוכל לשלם, כדי
להגדיל את כל המספרים. ואיך ניגשים לפתור את החלק הזה של השאלה? אז לשם כך לכאורה בעצם עלינו לקחת רשימה, לחשב את כל האפשרויות האפשריות
להגדיל את הרשימה למקסימום. באמצעות כל השילובים של הגדלה בודדת ושל הגדלה כפולה. ומכאן נוכל לדעת, מהו המחיר המינימאלי שעלינו לשלם כדי
להגדיל את הרשימה כולה. אבל זהו כמובן חישוב לא יעיל מבחינת זמן ריצה. ולכן, אם היינו יודעים מראש, איך הכי ... אחרות, מכך נוכל להסיק לגבי פתרון השאלה המקורית את הדבר הבא: בהינתן רשימת מספרים, שעלינו
להגדיל אותה למקסימום ב 2 דרכים אפשרויות עם 2 מחירים שונים. אז בשלב הראשון עלינו להבין האם כדאי לנו לבצע ... לזה? אז נתחיל מהמקרה הקל ביותר, נניח שיש לנו את הרשימה הבאה (1,2) דהיינו, שאנחנו צריכים
להגדיל את 1 לערך 2. האם ניתן לבצע זאת בהגדלה כפולה? כמובן שלא. אפשרי לבצע זאת בהגדלה אחת בודדת בלבד. ואם יש לנו את הרשימה (1, 100) דהיינו, שאנחנו צריכים
להגדיל את הערך 1 לערך 100. האם ניתן לעשות זאת בהגדלות כפולות? תשובה: לא. רק ב 99 הגדלות בודדות. או במילים אחרות, בטוח נכון שכאשר צריכים
להגדיל רק עמודה אחת בודדת, הרי שאין אפשרות לבצע הגדלה כפולה. ומה אם יש לנו
להגדיל 2 עמודות, לדוגמה (1, 1, 2), שעלינו
להגדיל את 2 העמודות של ה 1 אל הערך 2. הרי שניתן לבצע כאן הגדלה אחת כפולה שתהפוך את כל הרשימה ל (2, 2, ... כזה נוכל לבצע 99 הגדלות כפולות, שיביאו את הרשימה ל (100,100,100). ואם לצורך העניין נצטרך
להגדיל 3 עמודות, לדוגמה (1,1,1,2), הרי שבמקרה כזה, נוכל לבצע הגדלה 1 כפולה, שתביא אותנו ל (2,2,1,2) ואז ... את השארית, נגדיל בצורה של הגדלה בודדת. ומכך נובע ש, בהינתן עמודות שוות בגובהן, שצריך
להגדיל את כולן באותה כמות הגדלות, אז: אם יש לנו מספר זוגי של עמודות שצריכים
להגדיל, לדוגמה: (1,1,100) (1,1,1,1,100) (1,1,1,1,1,1,100) (1,1,1,1,1,1,1,1,100) אז ניקח את סהכ ההגדלות ... ל 2 ונקבל את כמות ההגדלות הכפולות שצריכים לבצע. ואם יש לנו מספר אי זוגי של עמודות שצריכים
להגדיל, לדוגמה: (1,100) (1,1,1,100) (1,1,1,1,1,100) (1,1,1,1,1,1,1,100) אז נצטרך לבצע את החישוב הבא: אם ... לדוגמה במקרים הבאים: (2,100) (2,2,2,100) (2,2,2,2,2,100) (2,2,2,2,2,2,2,100) שצריכים
להגדיל את כל המספרים ב 98 שזה מספר זוגי, אז שוב כנל, ניקח את סהכ ההגדלות שצריכים לבצע, לחלק ל 2. וזו תהיה כמות ההגדלות הכפולות שניתן לבצע. אבל אם נצטרך
להגדיל את המספרים בערך אי זוגי וכמות המספרים עצמם שנצטרך
להגדיל תהיה אי זוגית, לדוגמה: (1,100) (1,1,1,100) (1,1,1,1,1,100) (1,1,1,1,1,1,1,100) שיש לנו כמות אי זוגית של עמודות שצריכים
להגדיל + צריכים
להגדיל כל עמודה ב 99, שזה מספר אי זוגי, אז במקרה כזה, ניקח את סהכ הסכום שצריך
להגדיל, נחלק אותו ב 2. וזו תהיה כמות ההגדלות הכפולות שצריכים לבצע. ואחר כך בוודאות שנצטרך לבצע עוד ... שאנחנו יכולים לבצע, עלינו לאתר את העמודה עם הערך הקטן ביותר, שאותה אנחנו הכי צריכים
להגדיל. דהיינו, בדיוק כמו שאנחנו מחפשים את הערך MAX שהוא הערך שאליו צריכים