מיקומו של ערך true

נתון מערך דו-ממדי ריבועי המכיל ערכים בוליאניים. כל הערכים במערך הם false חוץ מתא אחד שהוא true. מטרתנו היא למצוא איפה נמצא התא שהוא true.

נתונה שיטת עזר סטטית Helper.ask המקבלת שני מספרים שלמים x ו-y המייצגים את מספר השורה ומספר העמודה (בהתאמה). השיטה בודקת איפה נמצא התא עם הערך true במערך יחסית לתא [x][y], ומחזירה מערך חד-ממדי בגודל שני תאים של מספרים שלמים, כך ש-

בתא הראשון (תא 0) במערך יהיה אחד מהערכים הבאים:

• 0 אם x הוא מספר השורה בה נמצא הערך true
• 1- אם מספר השורה בה נמצא הערך true קטן מ-x
• 1 אם מספר השורה בה נמצא הערך true גדול מ-x

בתא השני (תא 1) במערך יהיה אחד מהערכים הבאים:

• 0 אם y הוא מספר העמודה בה נמצא הערך true
• 1- אם מספר העמודה בה נמצא הערך true קטן מ-y
• 1 אם מספר העמודה בה נמצא הערך true גדול מ-y

אפשר להניח שהערכים x ו-y המהווים את הפרמטרים בשיטה Helper.ask הם בטווח הנכון, כלומר אין צורך לבדוק אם הם מחוץ למערך.

לדוגמא:

להלן מערך ריבועי בגודל 11×11, כאשר בכל תאי המערך, הערך הוא false ובתא שבשורה 4 ובעמודה 8 הערך הוא true. באיור להלן, הסימן X הוא true וכל שאר התאים ריקים (הם false).

אם נקרא לשיטה Helper.ask עם הפרמטרים הבאים נקבל את הערכים להלן:

Helper.ask(4,8) -> {0, 0}

Helper.ask(9,9) -> {-1, -1}

Helper.ask (4, 7) -> {0, 1}

Helper.ask(7, 7) -> {-1, 1}

בהינתן מערך הבוליאני יש להחזיר את מיקומו של הערך true. המיקום יוחזר באמצעות מערך חד-ממדי של מספרים שלמים בגודל 2 תאים. בתא הראשון (0) יוחזר מספר השורה בה נמצא הערך true ובתא השני (1) יוחזר מספר העמודה בה מסתתר הערך true.

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

tmp =
[[false,false,false,false,false,false,false,false,false,false],
 [false,false,false,false,false,false,false,false,false,false],
 [false,false,false,false,false,false,false,false,false,false],
 [false,false,false,false,false,false,false,false,false,false],
 [false,false,false,false,false,false,false,false,true,false],
 [false,false,false,false,false,false,false,false,false,false],
 [false,false,false,false,false,false,false,false,false,false],
 [false,false,false,false,false,false,false,false,false,false],
 [false,false,false,false,false,false,false,false,false,false],
 [false,false,false,false,false,false,false,false,false,false]]

[4, 8]

tmp =
[[true,false],
 [false,false]]

[0, 0]

tmp =
[[false,false,false],
 [false,true,false],
 [false,false,false]]

[1, 1]

tmp =
[[false,false],
 [true,false]]

[1, 0]