סכום זוג תאים במטריצה ממוינת

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

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

דוגמא למטריצה ממוינת:

 01234
03571218
12331444556
26167728990

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

  • אם התשובה חיובית, יש להדפיס את המיקום של שני התאים שסכומם הוא num, ולהחזיר את הערך true.
  • אם יש כמה פתרונות אפשריים – יש להדפיס את כולם ולהחזיר את הערך true.
  • אם אין אף זוג תאים במטריצה שסכומם הוא num יש להחזיר את הערך false.

דוגמאות:

בהינתן המטריצה mat לעיל:

  • אם num = 69, יוחזר false כיון שאין שני איברים במטריצה שסכומם 69.
  • אם num = 134, יוחזר true ויודפס את הפלט הבא:
    (1, 2) (2, 4)
    (1, 3) (2, 3)
    כיוון שמתקיים:
    mat[1][2] + mat[2][4] = 44 + 90 = 134
    mat[1][3] + mat[2][3] = 45 + 89 = 134

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

אילוצים:
  • פתרון נכון שיכלול רק אחת משתי הדרישות שלעיל - החזרת תשובה בוליאנית והדפסת פתרונות, לא יתקבל.
  • פתרון נכון שיבדוק את כל הזוגות האפשריים של ערכים מתוך המטריצה, אינו הפתרון המבוקש.
  • אפשר להניח שהמערך מלא בנתונים חוקיים ואינו null.
  • במהלך הפתרון אין להשתמש במערכי עזר או במבני נתונים נוספים.
דוגמה 1:
קלט: 
mat =
[[3, 5, 7, 12, 18],
 [23, 31, 44, 45, 56],
 [61, 67, 72, 89, 90]],
num = 69
פלט: 
false

הסבר: אין שני איברים במטריצה שסכומם 69.

דוגמה 2:
קלט: 
mat =
[[3, 5, 7, 12, 18],
 [23, 31, 44, 45, 56],
 [61, 67, 72, 89, 90]],
num = 134
פלט: 
(1, 2) (2, 4)
(1, 3) (2, 3)
true

הסבר: מתקיים mat[1][2] + mat[2][4] = 44 + 90 = 134, וכן mat[1][3] + mat[2][3] = 45 + 89 = 134.

דוגמה 3:
קלט: 
mat =
[[1, 2],
 [3, 4]],
num = 5
פלט: 
(0, 0) (1, 1)
(0, 1) (1, 0)
true

הסבר: הזוגות (0, 0) ו-(1, 1) נותנים 1+4=5, וכן הזוגות (0, 1) ו-(1, 0) נותנים 2+3=5.

דוגמה 4:
קלט: 
mat = [[10, 20]],
num = 30
פלט: 
(0, 0) (0, 1)
true

הסבר: הזוג (0, 0) ו-(0, 1) בשורה היחידה נותנים 10+20=30.

דוגמה 5:
קלט: 
mat = [[1, 2, 3]],
num = 10
פלט: 
false

הסבר: הסכום הגדול ביותר האפשרי משני תאים שונים הוא 2+3=5, שהוא קטן מ-10 ולכן התשובה שלילית.

דוגמה 6:
קלט: 
mat =
[[-10, -5, 0],
 [1, 2, 3]],
num = -7
פלט: 
(0, 0) (1, 2)
true

הסבר: הזוג (0, 0) המכיל -10, והזוג (1, 2) המכיל 3, נותנים (10-) + 3 = 7-.

דוגמה 7:
קלט: 
mat =
[[100, 200],
 [300, 400]],
num = 50
פלט: 
false

הסבר: הסכום הקטן ביותר האפשרי במטריצה הוא 100+200=300, שהוא גדול מהיעד 50.

דוגמה 8:
קלט: 
mat =
[[2, 4, 6],
 [8, 10, 12],
 [14, 16, 18]],
num = 22
פלט: 
(0, 1) (2, 2)
(0, 2) (2, 1)
(1, 0) (2, 0)
(1, 1) (1, 2)
true

הסבר: קיימים מספר זוגות שסכומם 22: (0, 1) ו-(2, 2) שהם 4+18, (0, 2) ו-(2, 1) שהם 6+16, ועוד.

Loading...
נשמרLn 1, Col 1

קלט:

mat =
[[3, 5, 7, 12, 18],
 [23, 31, 44, 45, 56],
 [61, 67, 72, 89, 90]],
num = 69

הפלט המבוקש:

false