... 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions. אז קודם כל נסביר את השאלה. יש לנו מספר
ילדים כלשהו (N) ויש לנו רשימת ערכים (חיוביים), שכל ערך בתוכה מציג את הציון של כל
ילד ברשימה. לדוגמה יש לנו 3
ילדים (N=3) ויש לנו רשימה שנראית כך (1,0,2) שאומרת ש:
ילד 1 הציון שלו הוא 1.
ילד 2 הציון שלו הוא 0.
ילד 3 הציון שלו הוא 2. עכשיו, עלינו לחלק סוכריות
לילדים האלו, עפ החוקים הבאים: חוק 1 - כל
ילד צריך לקבל לפחות סוכריה 1. חוק 2 - כל
ילד עם ציון יותר גבוה, צריך לקבל יותר סוכריות מאשר כל
ילד שצמוד אליו. והחידה היא, מהו מספר הסוכריות המינימלי והקטן ביותר שצריך לתת
לילדים האלו? כדי ליישם את 2 החוקים הקודמים. וכמובן שעלינו למצוא נוסחה כללית שתתאים באופן כללי לכל סוגי המקרים האפשריים. אז איך ניגשים לשאלה הזאת ואיך אפשרי לנסות לחלק אותה לחלקים יותר קטנים. אז קודם כל ננסה להבין אותה יותר טוב. בעצם נותנים לנו רשימה של
ילדים ולכל
ילד נותנים ציון כלשהו. ואנחנו צריכים לחלק סוכריות
לילדים לפי הציון שלהם ולפי 2 חוקים כלשהם. כאשר אנחנו אמורים לנסות לתת כמה שפחות סוכריות
לילדים. עכשיו, אם נתבונן בשאלה נבין, שכמות הסוכריות שאנחנו צריכים לחלק
לילדים, תלויה אך ורק בציון שלהם ולא בשום דבר אחר. שזה בעצם אומר, שאת הסוכריות אנחנו כאילו מחלקים לציונים ולא
לילדים. שזה בעצם אומר, שאנחנו יכולים להתעלם מכך שיש בכלל
ילדים ואנחנו יכולים לנסח את השאלה ולהבין אותה בצורה יותר פשוטה ושונה, כדלקמן: יש לנו רשימת מספרים כלשהי ועלינו לשים על כל מספר X ... אין את האילוץ שהוא יקבל יותר סוכריות ממי שעומד לידו (כמו שניתן לראות בדוגמה ה 2 שהם הביאו באתר שלהם, במקרה של (1,2,2) ). דהיינו, יכול להיות שכמה
ילדים עם אותו הציון, יקבלו מספר שונה של סוכריות, בהתאם למי שהם עומדים לידו. אז איך בעצם ניגשים לפתור את השאלה הזאת? אז בעצם יש לנו כאן 2 תהליכים. תהליך 1 הוא לחשב מה מינימום הסוכריות שצריך לקבל כל
ילד. תהליך 2 הוא לחשב כמה סהכ סוכריות קיבלו כל
הילדים. וכמובן שניתן להבין שתהליך החישוב של מה מינימום הסוכריות שצריך לקבל כל
ילד שנמצא ברשימה, הוא התהליך הראשון ובמקרה הוא גם התהליך הקשה יותר בחישובים, ולכן נתחיל ממנו. אז איך נדע כמה מינימום סוכריות צריך לקבל כל
ילד שנמצא ברשימה? אז ננסה לחלק את זה לחלקים. במקום לשאול את השאלה של כמה מינימום סוכריות צריך לקבל כל
ילד שנמצא ברשימה? במקום זה ננסה לשאול בצורה יותר פשוטה, כמה מינימום סוכריות צריך לקבל
ילד 1 מסוים שעומד ברשימה? ולכאורה זה אולי נראה אותה השאלה, ואפילו אפשרי לומר שזאת כמעט אותה השאלה. אבל באמת אלו 2 צורות שונות לפקס את המוח. ובמקום לחשוב על: איך אני מוצא כמה סוכריות צריך לקבל כל
ילד, צריך לחשוב על: איך אני מוצא כמה סוכריות צריך לקבל
הילד ה X ברשימה. דהיינו, לנסות לחשוב רק על
ילד 1 בלבד. עכשיו ננסה להפוך את השאלה הזאת לעוד יותר פשוטה וקלה. ולצורך העניין ננסה לחשוב על
הילד הראשון שעומד בשורה. אז נניח שיש לנו את השורה הבאה (0,1,2,3,4,5,6,7) דהיינו,
שהילד הראשון הערך שלו הוא 0. אז כמה סוכריות הוא צריך לקבל הכי פחות? תשובה: 1. כי הוא יכול לקבל את המינימום ההכרחי של סוכריות. ואין לו ...