העיר הקטנה שבה אתם גרים מתכננת להנהיג מערכת חדשה של מספרי ביטוח לאומי (SSN). כל אזרח יזוהה באמצעות SSN בן חמש ספרות. ארבע הספרות הראשונות שלו מציינות את מספר ה-ID הבסיסי (0000–9999), והספרה האחרונה היא ספרת ביקורת לגילוי שגיאות.
לצורך חישוב ספרות הביקורת החליטה העיר להשתמש בטבלת פעולה. טבלת פעולה היא טבלה בגודל $10 \times 10$ של ספרות עשרוניות שכל איברי האלכסון הראשי שלה הם $0$. להלן שתי דוגמאות לטבלאות פעולה.
טבלת פעולה 1
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | |
|---|---|---|---|---|---|---|---|---|---|---|
| $0$ | $0$ | $3$ | $1$ | $7$ | $5$ | $9$ | $8$ | $6$ | $4$ | $2$ |
| $1$ | $7$ | $0$ | $9$ | $2$ | $1$ | $5$ | $4$ | $8$ | $6$ | $3$ |
| $2$ | $4$ | $2$ | $0$ | $6$ | $8$ | $7$ | $1$ | $3$ | $5$ | $9$ |
| $3$ | $1$ | $7$ | $5$ | $0$ | $9$ | $8$ | $3$ | $4$ | $2$ | $6$ |
| $4$ | $6$ | $1$ | $2$ | $3$ | $0$ | $4$ | $5$ | $9$ | $7$ | $8$ |
| $5$ | $3$ | $6$ | $7$ | $4$ | $2$ | $0$ | $9$ | $5$ | $8$ | $1$ |
| $6$ | $5$ | $8$ | $6$ | $9$ | $7$ | $2$ | $0$ | $1$ | $3$ | $4$ |
| $7$ | $8$ | $9$ | $4$ | $5$ | $3$ | $6$ | $2$ | $0$ | $1$ | $7$ |
| $8$ | $9$ | $4$ | $3$ | $8$ | $6$ | $1$ | $7$ | $2$ | $0$ | $5$ |
| $9$ | $2$ | $5$ | $8$ | $1$ | $4$ | $3$ | $6$ | $7$ | $9$ | $0$ |
טבלת פעולה 2
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | |
|---|---|---|---|---|---|---|---|---|---|---|
| $0$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ |
| $1$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ |
| $2$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
| $3$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| $4$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ |
| $5$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ | $4$ |
| $6$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ | $3$ |
| $7$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ | $2$ |
| $8$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ | $1$ |
| $9$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $0$ |
באמצעות טבלת פעולה, ספרת הביקורת $e$ עבור מספר ID בסיסי בן ארבע ספרות $abcd$ מחושבת לפי הנוסחה הבאה. כאן $i \otimes j$ מציין את איבר הטבלה בשורה $i$ ובעמודה $j$.
$$e = (((0 \otimes a) \otimes b) \otimes c) \otimes d$$
לדוגמה, באמצעות טבלת פעולה 1, ספרת הביקורת $e$ עבור מספר ה-ID הבסיסי $abcd = 2016$ מחושבת באופן הבא.
$$\begin{aligned} e &= (((0 \otimes 2) \otimes 0) \otimes 1) \otimes 6 \\ &= ((1 \otimes 0) \otimes 1) \otimes 6 \\ &= (7 \otimes 1) \otimes 6 \\ &= 9 \otimes 6 \\ &= 6 \end{aligned}$$
לפיכך, מספר ה-SSN הוא $20166$.
שימו לב שספרת הביקורת תלויה בטבלת הפעולה שבה משתמשים. עם טבלת פעולה 2 מתקבל $e = 3$ עבור אותו מספר ID בסיסי $2016$, ומספר ה-SSN המלא יהיה $20163$.
$$\begin{array}{c} \begin{aligned} 2016 & \\ \Downarrow & \; \text{+ספרת ביקורת לפי טבלת פעולה 2} \\ 20163 & \\ \Downarrow & \; \text{טעויות אנוש} \end{aligned} \\[6pt] \boxed{\begin{array}{c} \overbrace{\mathbf{0}0163 \quad \mathbf{1}0163 \quad \dots \quad \mathbf{9}0163 \quad 2\mathbf{1}163 \quad 2\mathbf{2}163 \quad \dots \quad 2016\mathbf{8} \quad 2016\mathbf{9}}^{\text{שינוי ספרה בודדת}} \\[10pt] \overbrace{\mathbf{02}163 \quad 2\mathbf{10}63 \quad 20\mathbf{61}3 \quad 201\mathbf{36}}^{\text{החלפת שתי ספרות סמוכות}} \end{array}} \end{array}$$
איור B.1. שני סוגים של טעויות אנוש נפוצות
המטרה של הוספת ספרת הביקורת היא לגלות טעויות אנוש בעת כתיבה או הקלדה של מספרי SSN. הפונקציה check הבאה יכולה לגלות טעויות אנוש מסוימות. עבור מספר בן חמש ספרות $abcde$, הפונקציה check מוגדרת כך.
$$\operatorname{check}(abcde) = ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e$$
פונקציה זו מחזירה $0$ עבור SSN תקין. זאת משום שכל איבר אלכסוני בטבלת פעולה הוא $0$, ועבור SSN תקין מתקיים $e = (((0 \otimes a) \otimes b) \otimes c) \otimes d$:
$$\operatorname{check}(abcde) = ((((0 \otimes a) \otimes b) \otimes c) \otimes d) \otimes e = e \otimes e = 0.$$
לעומת זאת, ערך שונה מאפס המוחזר על ידי check מעיד שהמספר הנתון אינו יכול להיות SSN תקין. שימו לב שבהתאם לטבלת הפעולה שבה משתמשים, הפונקציה check עלולה להחזיר $0$ גם עבור SSN שגוי. סוגי השגיאות המתגלים תלויים בטבלת הפעולה שבשימוש; הטבלה קובעת את איכות גילוי השגיאות.
רשויות העיר מעוניינות לגלות שני סוגים של טעויות אנוש נפוצות ברצפי ספרות: שינוי ספרה בודדת והחלפת שתי ספרות סמוכות, כפי שמוצג באיור B.1.
טבלת פעולה נקראת טובה אם היא מסוגלת לגלות את כל השגיאות הנפוצות משני הסוגים בכל מספרי ה-SSN הנוצרים ממספרי ID בסיסיים בני ארבע ספרות 0000–9999. שימו לב שיש לגלות שגיאות בספרת הביקורת כמו גם בארבע ספרות ה-ID הבסיסי. לדוגמה, טבלת פעולה 1 היא טובה. טבלת פעולה 2 אינה טובה משום שעבור $20613$, שהוא מספר המתקבל מהחלפת הספרה ה-3 והספרה ה-4 של SSN תקין $20163$, הערך של $\operatorname{check}(20613)$ הוא $0$. למעשה, מתוך $10000$ מספרי ID בסיסיים, טבלת פעולה 2 אינה מצליחה לגלות שגיאה נפוצה אחת או יותר עבור לא פחות מ-$3439$ מספרי ID בסיסיים.
בהינתן טבלת פעולה, קבעו עד כמה היא טובה על ידי ספירת מספרם של מספרי ה-ID הבסיסיים שעבורם הטבלה הנתונה אינה מצליחה לגלות שגיאה נפוצה אחת או יותר.
קלט
הקלט מורכב ממקרה בדיקה יחיד בפורמט הבא.
$$\begin{array}{cccc} x_{00} & x_{01} & \cdots & x_{09} \\ \vdots & & & \\ x_{90} & x_{91} & \cdots & x_{99} \end{array}$$
הקלט מתאר טבלת פעולה שבה $x_{ij}$ היא הספרה העשרונית בשורה $i$ ובעמודה $j$. כל שורה בקלט מתאימה לשורה בטבלה, שבה האיברים מופרדים ברווח בודד. איברי האלכסון $x_{ii}$ ($i = 0, \ldots, 9$) הם תמיד $0$.
פלט
הדפיסו את מספרם של מספרי ה-ID הבסיסיים שעבורם הטבלה הנתונה אינה מצליחה לגלות טעות אנוש נפוצה אחת או יותר.
דוגמאות
קלט 1
0 3 1 7 5 9 8 6 4 2 7 0 9 2 1 5 4 8 6 3 4 2 0 6 8 7 1 3 5 9 1 7 5 0 9 8 3 4 2 6 6 1 2 3 0 4 5 9 7 8 3 6 7 4 2 0 9 5 8 1 5 8 6 9 7 2 0 1 3 4 8 9 4 5 3 6 2 0 1 7 9 4 3 8 6 1 7 2 0 5 2 5 8 1 4 3 6 7 9 0
פלט 1
0
קלט 2
0 1 2 3 4 5 6 7 8 9 9 0 1 2 3 4 5 6 7 8 8 9 0 1 2 3 4 5 6 7 7 8 9 0 1 2 3 4 5 6 6 7 8 9 0 1 2 3 4 5 5 6 7 8 9 0 1 2 3 4 4 5 6 7 8 9 0 1 2 3 3 4 5 6 7 8 9 0 1 2 2 3 4 5 6 7 8 9 0 1 1 2 3 4 5 6 7 8 9 0
פלט 2
3439
קלט 3
0 9 8 7 6 5 4 3 2 1 1 0 9 8 7 6 5 4 3 2 2 1 0 9 8 7 6 5 4 3 3 2 1 0 9 8 7 6 5 4 4 3 2 1 0 9 8 7 6 5 5 4 3 2 1 0 9 8 7 6 6 5 4 3 2 1 0 9 8 7 7 6 5 4 3 2 1 0 9 8 8 7 6 5 4 3 2 1 0 9 9 8 7 6 5 4 3 2 1 0
פלט 3
9995
קלט 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
פלט 4
10000