露露, 花花 und 萱萱 interessieren sich neuerdings für Zufallszahlen in Computern. Wie allgemein bekannt ist, sind vom Computer erzeugte Zufallszahlenfolgen nicht wirklich zufällig, sondern nach bestimmten Regeln erzeugte Pseudozufallszahlen.
Eines Tages lernte 露露 ein Verfahren zur Erzeugung von Zufallszahlen namens Mersenne twister kennen. Für die Anfangsparameter $m\in\mathbb Z^+$, $x\in\mathbb Z\cap[0,2^m)$ und den Anfangswert $M_0\in\mathbb Z\cap[0,2^m)$ erzeugt es die Pseudozufallsfolge $\{M_n\}$ durch folgende Rekursion:
$$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}$$
Dabei bezeichnet xor die bitweise Exklusiv-Oder-Verknüpfung (den Operator ^ in C/C++). Wird der Parameter $x$ so gewählt, dass die Folge für gegen unendlich gehende Länge annähernd gleichwahrscheinlich Werte aus $\mathbb Z\cap(0,2^m)$ annimmt, heißt $x$ gut. Beispielsweise ist für $m>1$ der Wert $x=0$ offensichtlich nicht gut.
Nachdem 露露 ihren Freunden Mersenne twister vorgestellt hatte, wollte 花花 dessen Zufallseigenschaften mit klassischen Zufälligkeitstests überprüfen. Dazu berechnete 花花 einige Werte $M_k$ am Computer.
Die aufmerksame 萱萱 bemerkte jedoch, dass 花花 bei einer binären Eingabe von $k$ versehentlich $l$ zusätzliche Nullen angehängt hatte. Sie wollte 花花 gerade darauf hinweisen, doch 花花 hatte den falschen Wert $M_k$ bereits berechnet und notiert, ohne $k$ zu speichern. Obwohl dies eigentlich kein schwerwiegendes Problem war, bat die perfektionistische 花花 萱萱 dennoch, den Wert $M_k$ zu korrigieren. 萱萱 übertrug diese Aufgabe ihrer KI — dir.
Eingabe
Die erste Zeile der Eingabedatei random.in enthält eine positive ganze Zahl $m$. Die zweite Zeile enthält $x$ in Binärdarstellung ($m$ Ziffern, vom niederwertigsten zum höchstwertigen Bit). Die dritte Zeile enthält $M_0$ in derselben Darstellung wie $x$, die vierte eine ganze Zahl $type$.
Danach gibt es zwei mögliche Fälle:
- $type=0$ (萱萱 hat 花花s Eingabe notiert): Die fünfte Zeile enthält eine ganze Zahl, den von 萱萱 notierten korrekten Wert von $k$.
- $type=1$ (萱萱 konnte 花花s Eingabe nicht notieren): Die fünfte Zeile enthält $l$, die sechste den von 花花 falsch berechneten Wert $M_k$ in Binärdarstellung.
Ausgabe
Die Ausgabedatei random.out enthält genau eine Zeile mit einer aus $m$ Bits bestehenden 01-Zeichenkette, die den berechneten korrekten Wert $M_k$ darstellt (ebenfalls vom niederwertigsten zum höchstwertigen Bit).
Beispiele
Eingabe 1
10 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 100
Ausgabe 1
0101111001
Eingabe 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
Ausgabe 2
0101111001
Beispiele 3
Siehe random/random.in und random/random.ans im Teilnehmerverzeichnis.
Beschränkungen
| Testnummer | $m$ | $k$ | $l$ | $type$ | Ist $x$ „gut“? |
|---|---|---|---|---|---|
| $1$ | $\le10$ | $\le10^9$ | N/A | $0$ | Ja |
| $2$ | $\le10$ | $\le10^9$ | $\le10$ | $1$ | Ja |
| $3$ | $\le100$ | $\le10^9$ | N/A | $0$ | Ja |
| $4$ | $\le100$ | $\le10^9$ | N/A | $0$ | Ja |
| $5$ | $\le100$ | $\le10^9$ | N/A | $0$ | Ja |
| $6$ | $\le100$ | $\le10^5$ | $=1$ | $1$ | Ja |
| $7$ | $\le100$ | $\le10^9$ | $\le10$ | $1$ | Ja |
| $8$ | $\le100$ | $\le10^9$ | $\le10$ | $1$ | Ja |
| $9$ | $\le100$ | $\le10^9$ | $\le10$ | $1$ | Ja |
| $10$ | $\le1000$ | $\le10^{18}$ | $\le10$ | $1$ | Ja |
| $11$ | $\le1000$ | $\le10^{18}$ | $\le10$ | $1$ | Ja |
| $12$ | $\le1000$ | $\le10^{18}$ | $\le10$ | $1$ | Ja |
| $13$ | $\le2000$ | $\le10^9$ | N/A | $0$ | Ja |
| $14$ | $\le2000$ | $\le10^9$ | N/A | $0$ | Ja |
| $15$ | $\le500000$ | $\le10^6$ | N/A | $0$ | Nein |
| $16$ | $\le500000$ | $\le10^6$ | N/A | $0$ | Nein |
| $17$ | $\le1000000$ | $\le10^6$ | N/A | $0$ | Nein |
| $18$ | $\le1000000$ | $\le10^6$ | N/A | $0$ | Nein |
| $19$ | $\le1000000$ | $\le10^6$ | N/A | $0$ | Nein |
| $20$ | $\le1000000$ | $\le10^6$ | N/A | $0$ | Nein |