פתרון לLemons

מה רוצים בשאלה

יש מערכת השקיה המורכבת מצינורות המחוברים בתור.
אחד הצינורות מקולקל ודופק את זרימת המים ממנו ואילך.
ידוע שהצינור שהכי קרוב למטע הלימון(שלשם הולכת מערכת ההשקיה) תקין והבעיה באחד הצינורות שלפניו.
צריך למצוא את הצינור התקול נתון לך-מספר הצינורות(N)הצינור במקום ה-1 הוא זה שידוע כתקין,כמות הזמן שלוקח להגיע לכל צינור(M) וכמות הזמן שלוקח לבדוק כל צינור(S)

איך פותרים

עושים חיפוש בינארי מ2 עד N(כיוון שידוע שהראשון תקין).
ונחשב כל פעם את כמות הזמן שלוקח לו בין בדיקה לבדיקה(המרחק להגיע לצינור+הבדיקה של הצינור.
מכיוון שביקשו את המקרה הגרוע ביותר בכל פעם נשווה את low לmid+1

sumall = 0
low = 2
high = N
while(low <= high):
    mid = (high + low)//2
    sum = (mid - (low - 1))*M + S
    low = mid + 1
    sumall += sum
print(sumall)