זוג איברים במערכים שסכומם קרוב ביותר לערך

נתונים שני מערכים a ו-b המכילים מספרים שלמים. כל אחד מהמערכים ממוין בסדר לא יורד (יכולים להיות מספרים זהים).

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

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

אילוצים:

שני המערכים מלאים במספרים שלמים וממוינים בסדר לא יורד, והם אינם null.

דוגמה 1:

קלט:

a = [0, 4, 6, 11, 11],
b = [10, 20, 30, 40],
x = 11

פלט:

0 and 10

הסבר: הסכום 0+10=10 הוא הקרוב ביותר ל-11

דוגמה 2:

קלט:

a = [0, 4, 6, 11, 11],
b = [10, 20, 30, 40],
x = 13

פלט:

4 and 10

הסבר: הסכום 4+10=14 הוא הקרוב ביותר ל-13

דוגמה 3:

קלט:

a = [0, 4, 6, 11, 11],
b = [10, 20, 30, 40],
x = 18

פלט:

0 and 20

הסבר: הסכום 6+10=16 או 0+20=20 שניהם במרחק 2 מ-18

דוגמה 4:

קלט:

a = [0, 4, 6, 11, 11],
b = [10, 20, 30, 40],
x = 70

פלט:

11 and 40

הסבר: הסכום 11+40=51 הוא הקרוב ביותר ל-70

דוגמה 5:

קלט:

a = [1, 3, 5],
b = [2, 4, 6],
x = 12

פלט:

5 and 6

הסבר: הסכום 6+5=11 הוא הקרוב ביותר ל-12

דוגמה 6:

קלט:

a = [10, 20, 30],
b = [5, 15, 25],
x = 22

פלט:

10 and 15

הסבר: הסכום 10+15=25 הוא הקרוב ביותר ל-22

דוגמה 7:

קלט:

a = [1],
b = [1],
x = 2

פלט:

1 and 1

הסבר: הסכום 1+1=2

דוגמה 8:

קלט:

a = [-5, -3, -1],
b = [-10, -8, -6],
x = -5

פלט:

-1 and -6

הסבר: הסכום -1+(-6)=-7 הוא הקרוב ביותר ל-(-5)

נשמרLn 1, Col 1

קלט:

a = [0, 4, 6, 11, 11],
b = [10, 20, 30, 40],
x = 11

הפלט המבוקש:

0 and 10