המסלול עם הממוצע הגדול ביותר

נתון מערך דו-ממדי mat המכיל מספרים שלמים, כולם שונים זה מזה.

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

לדוגמה, במערך mat שלהלן:

	0	1	2
0	9	7	5
1	18	-1	0
2	-14	4	-13
3	-19	10	11

ישנם 2 מסלולים חוקיים שאורכם הוא k = 2, והם:

9 → 7
9 → 18

ישנם 4 מסלולים חוקיים שאורכם הוא k = 3, והם:

9 → 7 → 5
9 → 18 → -14
9 → 7 → -1
9 → 18 → -1

ישנם 9 מסלולים חוקיים שאורכם הוא k = 4. למשל, הנה חלק מהתשעה:

9 → 7 → 5 → 0
9 → 18 → -1 → 4
9 → 18 → -1 → 0
9 → 18 → -14 → 4
ועוד.

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

בדוגמה לעיל,

אם k = 2, הממוצע של המסלול 9 → 7 הוא 8.0 והממוצע של המסלול 9 → 18 הוא 13.5, ולכן השיטה תחזיר את הערך 13.5.

אם k = 3, הממוצע של המסלול 9 → 7 → 5 הוא 7.0, הממוצע של המסלול 9 → 18 → -14 הוא 4.333, הממוצע של המסלול 9 → 7 → -1 הוא 5.0, והממוצע של המסלול 9 → 18 → -1 הוא 8.666, ולכן השיטה תחזיר את הערך 8.666.

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

אילוצים:

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

דוגמה 1:

קלט:

mat =
[[9, 7, 5],
 [18, -1, 0],
 [-14, 4, -13],
 [-19, 10, 11]],
k = 3

פלט:

8.666666666666666

הסבר: ישנם 4 מסלולים חוקיים באורך 3 שמתחילים ב-[0][0]: 9→7→5 (ממוצע 7.0), 9→18→-14 (ממוצע 4.333), 9→7→-1 (ממוצע 5.0), ו-9→18→-1 (ממוצע 8.666). הממוצע הגדול ביותר הוא 26/3 ≈ 8.6667.

דוגמה 2:

קלט:

mat =
[[9, 7, 5],
 [18, -1, 0],
 [-14, 4, -13],
 [-19, 10, 11]],
k = 2

פלט:

13.5

הסבר: ישנם 2 מסלולים חוקיים באורך 2: 9→7 (ממוצע 8.0) ו-9→18 (ממוצע 13.5). הממוצע הגדול ביותר הוא 27/2 = 13.5.

דוגמה 3:

קלט:

mat =
[[9, 7, 5],
 [18, -1, 0],
 [-14, 4, -13],
 [-19, 10, 11]],
k = 4

פלט:

8.25

הסבר: המסלול 9→18→-1→7 (וגם 9→7→-1→18) בעל הסכום המקסימלי 33, ולכן הממוצע הוא 33/4 = 8.25.

דוגמה 4:

קלט:

mat =
[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]],
k = 5

פלט:

5.8

הסבר: המסלול 1 → 4 → 7 → 8 → 9 (סכום 29) הוא בעל הסכום המקסימלי, ולכן הממוצע הוא 29/5 = 5.8.

דוגמה 5:

קלט:

mat =
[[10, 20],
 [30, 40]],
k = 3

פלט:

26.666666666666668

הסבר: המסלול 10 → 30 → 40 (סכום 80) הוא בעל הסכום המקסימלי, והממוצע הוא 80/3 ≈ 26.6667.

דוגמה 6:

קלט:

mat =
[[1, 2],
 [3, 4]],
k = 4

פלט:

2.5

הסבר: המסלול 1 → 2 → 4 → 3 (או 1 → 3 → 4 → 2) עובר בכל התאים וסכומו 10. הממוצע הוא 10/4 = 2.5.

דוגמה 7:

קלט:

mat =
[[1, 2, 3]],
k = 3

פלט:

2.0

הסבר: מטריצה בשורה אחת – המסלול היחיד באורך 3 הוא 1 → 2 → 3, סכום 6, ממוצע 2.0.

דוגמה 8:

קלט:

mat =
[[1, 100],
 [2, 3]],
k = 4

פלט:

26.5

הסבר: המסלול 1(0,0) → 100(0,1) → 3(1,1) → 2(1,0) (או הסדר ההפוך 1 → 2 → 3 → 100) עובר בכל התאים, סכום 106, ממוצע 106/4 = 26.5.

נשמרLn 1, Col 1

קלט:

mat =
[[9, 7, 5],
 [18, -1, 0],
 [-14, 4, -13],
 [-19, 10, 11]],
k = 3

הפלט המבוקש:

8.666666666666666