פתרון לRecXor

מה רוצים בתרגיל

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

איך פותרים

בנינו פונקציה שמחשבת קסור בין טווח של מספרים ז"א אם נגיד אנחנו רוצים לחשב את כל הXOR-ים בין 1 ל50 אנחנו לא נצטרך לשעות 1 קסור 2 קסור 3 קסור 4 ... קסור 50
יהיה אפשרי לעשות קסור יחיד לטווח בין 1 ל50.
הפונקציה לוקחת את המספר הראשון של הטווח והמספר האחרון של הטווח ובודקת את המספרים האלו עם מודלו 4:
אם המספר מודלו 4 מחזיר 0 אז המספר נשאר אות מספר.
אם המספר מודולו 4 מחזיר 1 המספר הופך ל1.
אם המספר מודלו 4 מחזיר 2 מוסיפים למספר 1.
אם המספר מודלו 4 מחזיר 3 המספר הופך ל0.
ההגיון של זה הוא שהפעולה XOR היא ממש פעולה מחזורית של מודלו 4-כל 4 מספרים הXOR מתאפס ולכן אין טעם לחשב מספר מספר

def xor(a, b):
    a = a-1
    if a % 4 == 0:
        a = a
    elif a % 4 == 1:
        a = 1
    elif a % 4 == 2:
        a += 1
    else:
        a = 0
    if b % 4 == 0:
        b = b
    elif b % 4 == 1:
        b = 1
    elif b % 4 == 2:
        b += 1
    else:
        b = 0
    return a^b

כעת נחפש את ההתחלה והסוף של המלבן הגדול והמלבן הקטן

מלבן גדול:

נקודת ההתחלה נתונה ואת נקודת הסוף נמצא באמצעות חישוב גובה המלבן * רוחב המלבן + נקודת ההתחלה - 1

whole_square = xor(n,l*h + n -1)

מלבן קטן:

כדי לחשב את הxor של המלבן הקטן נצטרך למצוא את הנקודות סוף והתחלה של הגובה והרוחב שלו-נמיר את המשבצות האלו למיקום שלהם ביחס לגובה ורוחב של המלבן הגדול

    width_start = (d1-n) % l + 1
    width_end = (d2-n) % l + 1
    height_start = (d1-n) // l + 1
    height_end = (d2-n) // l + 1

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

    if width_start > width_end:
        width_start, width_end = width_end, width_start

    if height_start > height_end:
        height_start, height_end = height_end, height_start

חיושב סופי

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

    inner_square = 0
    for i in range(height_start,height_end +1):
        inner_square ^= xor(n + width_start-1 + (i-1)*l,n + width_end -1 + (i-1)*l)

    whole_square = xor(n,l*h + n -1)
    print(whole_square^inner_square)