מסלול אוטובוס

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

לאמיר ישנן 2 אפשרויות להתקדם במערך:

  1. צעד בגודל step1 בו מותר לו להשתמש ללא הגבלה.
  2. צעד בגודל step2 בו מותר להשתמש לכל היותר limit פעמים.

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

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

דוגמה 1:
קלט:
stations = [2, 4, 8, 3, 10, 1, 12, 3, 2],
step1 = 3,
step2 = 2,
limit = 4
פלט:
0	3	6	8	=19
0	3	5	8	=8
0	2	5	8	=13
0	2	4	6	8	=34
8

הסבר: השיטה תחזיר את הערך 8 שהוא הסכום של המספרים 2+3+1+2 והמינימלי מבין כל המסלולים

דוגמה 2:
קלט:
stations = [5, 100, 100, 1, 1, 1],
step1 = 1,
step2 = 3,
limit = 1
פלט:
0	1	2	3	4	5	=208
0	1	2	5	=206
0	1	4	5	=107
0	3	4	5	=8
8
דוגמה 3:
קלט:
stations = [10, 5, 1, 100, 1, 5],
step1 = 1,
step2 = 2,
limit = 2
פלט:
0	1	2	3	4	5	=122
0	1	2	3	5	=121
0	1	2	4	5	=22
0	1	3	4	5	=121
0	1	3	5	=120
0	2	3	4	5	=117
0	2	3	5	=116
0	2	4	5	=17
17
דוגמה 4:
קלט:
stations = [4, 100, 2, 1, 5],
step1 = 1,
step2 = 2,
limit = 1
פלט:
0	1	2	3	4	=112
0	1	2	4	=111
0	1	3	4	=110
0	2	3	4	=12
12
דוגמה 5:
קלט:
stations = [7, 6, 1, 2, 9, 3],
step1 = 1,
step2 = 3,
limit = 1
פלט:
0	1	2	3	4	5	=28
0	1	2	5	=17
0	1	4	5	=25
0	3	4	5	=21
17
דוגמה 6:
קלט:
stations = [2, 2, 2, 2, 2, 2],
step1 = 1,
step2 = 2,
limit = 2
פלט:
0	1	2	3	4	=10
0	1	2	4	=8
0	1	3	4	=8
0	2	3	4	=8
0	2	4	=6
6
דוגמה 7:
קלט:
stations = [1, 1, 2, 1, 2, 1],
step1 = 1,
step2 = 2,
limit = 2
פלט:
0	1	2	3	4	5	=8
0	1	2	3	5	=6
0	1	2	4	5	=7
0	1	3	4	5	=6
0	1	3	5	=4
0	2	3	4	5	=7
0	2	3	5	=5
0	2	4	5	=6
4
Loading...
נשמרLn 1, Col 1

קלט:

stations = [2, 4, 8, 3, 10, 1, 12, 3, 2],
step1 = 3,
step2 = 2,
limit = 4

הפלט המבוקש:

0	3	6	8	=19
0	3	5	8	=8
0	2	5	8	=13
0	2	4	6	8	=34
8