露露, 花花 ו־萱萱 התעניינו לאחרונה במספרים אקראיים במחשב. כידוע, סדרת המספרים האקראיים שמחשב מייצר אינה אקראית באמת, אלא סדרה פסאודו־אקראית הנוצרת לפי כללים מסוימים.
יום אחד למדה 露露 שיטה ליצירת מספרים אקראיים הנקראת Mersenne twister. בהינתן פרמטרים התחלתיים $m\in\mathbb Z^+$, $x\in\mathbb Z\cap[0,2^m)$ וערך התחלתי $M_0\in\mathbb Z\cap[0,2^m)$, היא בונה סדרה פסאודו־אקראית $\{M_n\}$ לפי נוסחת הנסיגה הבאה:
$$M_n=\begin{cases}2M_{n-1}&2M_{n-1}<2^m\\(2M_{n-1}-2^m)\mathbin{\mathrm{xor}}x&2M_{n-1}\ge2^m\end{cases}$$
כאן $\mathrm{xor}$ היא פעולת XOR בינארית, כלומר האופרטור ^ ב־C/C++. אם בחירת הפרמטר $x$ גורמת לכך שכאשר אורך הסדרה שואף לאינסוף, ערכיה מופיעים בקירוב בהסתברות שווה ב־$\mathbb Z\cap(0,2^m)$, נקרא ל־$x$ טוב. לדוגמה, כאשר $m>1$, ברור ש־$x=0$ אינו טוב.
אחרי ש־露露 הציגה לחבריה את Mersenne twister, רצתה 花花 לבדוק את מידת האקראיות שלו באמצעות כמה מבחני אקראיות קלאסיים. לשם כך היא חישבה במחשב כמה ערכי $M_k$.
אולם 萱萱 הקשובה שמה לב שבאחת הפעמים שבהן 花花 הקלידה את $k$ בבסיס בינארי, היא הוסיפה בטעות $l$ אפסים בסוף. היא עמדה לספר ל־花花 על הטעות, אבל 花花 כבר חישבה ורשמה את הערך השגוי של $M_k$, בלי לרשום את $k$. אף שאין זו בעיה חמורה במיוחד, כש־萱萱 סיפרה לה על ההשמטה, 花花 הפרפקציוניסטית בכל זאת ביקשה ממנה לתקן את ערך $M_k$. 萱萱 העבירה את המשימה לבינה המלאכותית שלה — אתה.
קלט
השורה הראשונה בקובץ הקלט random.in מכילה מספר שלם חיובי $m$. השורה השנייה מכילה את הייצוג הבינארי של $x$: בסך הכול $m$ ספרות, מהסיבית הפחות משמעותית אל המשמעותית ביותר. השורה השלישית מכילה את הייצוג הבינארי של $M_0$ באותו סדר. השורה הרביעית מכילה מספר שלם $type$.
בהמשך יש שני מקרים אפשריים:
- $type=0$ (萱萱 רשמה את הקלט של 花花): השורה החמישית מכילה מספר שלם — הערך הנכון של $k$ ש־萱萱 רשמה.
- $type=1$ (萱萱 לא הספיקה לרשום את הקלט של 花花): השורה החמישית מכילה את $l$, והשורה השישית מכילה את הייצוג הבינארי השגוי של $M_k$ שחישבה 花花.
פלט
קובץ הפלט random.out מכיל שורה אחת בלבד: מחרוזת של $m$ ספרות 0 ו־1 המייצגת את ערך $M_k$ הנכון שמצאת. גם כאן יש לסדר את הספרות מהסיבית הפחות משמעותית אל המשמעותית ביותר.
דוגמאות
קלט 1
10 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 100
פלט 1
0101111001
קלט 2
10 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 3 0 1 0 1 1 1 1 1 0 1
פלט 2
0101111001
דוגמה 3
ראה random/random.in ו־random/random.ans בתיקיית המתחרים.
מגבלות והנחות
| מספר מקרה הבדיקה | $m$ | $k$ | $l$ | $type$ | האם $x$ טוב |
|---|---|---|---|---|---|
| $1$ | $\le 10$ | $\le 10^9$ | לא חל | $0$ | כן |
| $2$ | $\le 10$ | $\le 10^9$ | $\le10$ | $1$ | כן |
| $3$ | $\le 100$ | $\le 10^9$ | לא חל | $0$ | כן |
| $4$ | $\le 100$ | $\le 10^9$ | לא חל | $0$ | כן |
| $5$ | $\le 100$ | $\le 10^9$ | לא חל | $0$ | כן |
| $6$ | $\le 100$ | $\le 10^5$ | $=1$ | $1$ | כן |
| $7$ | $\le 100$ | $\le 10^9$ | $\le10$ | $1$ | כן |
| $8$ | $\le 100$ | $\le 10^9$ | $\le10$ | $1$ | כן |
| $9$ | $\le 100$ | $\le 10^9$ | $\le10$ | $1$ | כן |
| $10$ | $\le 1000$ | $\le 10^{18}$ | $\le10$ | $1$ | כן |
| $11$ | $\le 1000$ | $\le 10^{18}$ | $\le10$ | $1$ | כן |
| $12$ | $\le 1000$ | $\le 10^{18}$ | $\le10$ | $1$ | כן |
| $13$ | $\le 2000$ | $\le 10^9$ | לא חל | $0$ | כן |
| $14$ | $\le 2000$ | $\le 10^9$ | לא חל | $0$ | כן |
| $15$ | $\le 500000$ | $\le 10^6$ | לא חל | $0$ | לא |
| $16$ | $\le 500000$ | $\le 10^6$ | לא חל | $0$ | לא |
| $17$ | $\le 1000000$ | $\le 10^6$ | לא חל | $0$ | לא |
| $18$ | $\le 1000000$ | $\le 10^6$ | לא חל | $0$ | לא |
| $19$ | $\le 1000000$ | $\le 10^6$ | לא חל | $0$ | לא |
| $20$ | $\le 1000000$ | $\le 10^6$ | לא חל | $0$ | לא |