Gegeben ist ein Array von $n$ ganzen Zahlen von $1$ bis $n+1$. Es ist möglich, dass einige der ganzen Zahlen mehrfach im Array vorkommen. Dennoch ist klar, dass mindestens eine der ganzen Zahlen von $1$ bis $n+1$ im Array fehlt. Deine Aufgabe ist es, eine beliebige solche Zahl zu finden. Normalerweise wäre das einfach, aber es gibt ein bedauerliches Problem: Auf deinem Computer ist nicht genug Speicherplatz vorhanden, um das gesamte Array darzustellen.
Daher wirst du gebeten, stattdessen einen Streaming-Algorithmus zu entwerfen. Informell ausgedrückt werden dir die Elemente des Arrays einzeln nacheinander übergeben, ohne dass du wahlfrei (per Random Access) auf sie zugreifen kannst. Es gibt jedoch einen Trost: Nachdem du das letzte Element des Arrays erhalten hast, kannst du das Lesen wieder von vorne beginnen. Idealerweise möchtest du eine solche Situation vermeiden und das gesamte Problem in einem einzigen Durchlauf (Pass) lösen. Manchmal (einschließlich genau dieses Problems) können jedoch mehrere Durchläufe über die Eingabe erforderlich sein, um nicht zu viel Speicher zu verbrauchen. Du musst beide Anforderungen ausbalancieren und gleichzeitig weder zu viel Speicher verbrauchen noch zu viele Durchläufe über das Array machen (das Problem ist trivial, wenn du $n$ Bits Speicher nutzen oder $n$ Durchläufe machen darfst).
Es gibt allerdings noch einen Haken. Aus technischen Gründen musst du einen deterministischen endlichen Automaten (DFA) über dem Alphabet $\{0, 1, \dots, n + 1\}$ erzeugen, der die Logik deines Algorithmus implementiert. Die Zeichen des Alphabets entsprechen den Informationen, die du beim Lesen des Datenstroms erhältst: Zahlen von $1$ bis $n+1$ stehen für das Lesen der entsprechenden ganzen Zahl aus dem Array, während die Zahl $0$ bedeutet, dass du das Ende des Arrays erreicht hast. Nachdem du die ersten 7 Male das Ende des Arrays erreicht hast, wird dir das Array erneut in derselben Reihenfolge wie zuvor übergeben, wobei am Ende immer ein $0$-Zeichen steht, das das Ende des Arrays markiert. Somit wird dein DFA insgesamt 8-mal mit der Zeichenkette $a_1, a_2, \dots, a_n, 0$ gefüttert (hierbei ist $a_1, a_2, \dots, a_n$ das versteckte Array). Schließlich kann dein Automat zu jedem Zeitpunkt der Ausführung „sagen“, dass er bereits eine richtige Antwort auf das Problem kennt; in diesem Fall wird die Ausführung angehalten. Wenn dein DFA dies bis zu dem Zeitpunkt, an dem er den gesamten Strom (einschließlich des $0$-Zeichens am Ende) 8-mal gelesen hat, nicht getan hat, wird er nicht als Lösung akzeptiert. Ebenso wird er nicht als Lösung akzeptiert, wenn er zwar anhält, aber eine falsche Antwort liefert.
Formulieren wir das Problem nun formal. Es gibt ein verstecktes Array $a_1, a_2, \dots, a_n$ aus $n$ ganzen Zahlen von $1$ bis $n+1$. Im Beispiel gilt $n = 4$, in allen anderen Tests gilt $n = 250$. Du musst eine endliche Zustandsmaschine mit höchstens 4000 Zuständen angeben, die von $0$ bis $q - 1$ nummeriert sind, wobei $q \le 4000$ die Anzahl der Zustände ist. Für den Zustand $i$ ($0 \le i \le q - 1$) musst du $n + 2$ Zahlen $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$ angeben. Die Zahl $\delta(i, j)$ beschreibt das Verhalten deines DFA, wenn er sich im Zustand $i$ befindet und die Zahl $j$ aus der Eingabe liest. Sie muss eine ganze Zahl von $-(n + 1)$ bis einschließlich $q - 1$ sein. Negative ganze Zahlen entsprechen der Tatsache, dass die Ausführung angehalten und eine Antwort ausgegeben wird; konkret bedeutet $-s$, dass dein DFA behauptet, $+s$ sei eine korrekte Antwort auf das Problem. Nichtnegative ganze Zahlen entsprechen der Tatsache, dass die Ausführung fortgesetzt wird und der Zustand des Automaten von $i$ zu $\delta(i, j)$ wechselt. Die Ausführung des Automaten beginnt im Zustand $0$.
Dein DFA arbeitet auf dem Array $a_1, a_2, \dots, a_n$ korrekt, wenn er zu irgendeinem Zeitpunkt beim Lesen der Zeichenkette $a_1, a_2, \dots, a_n, 0, a_1, a_2, \dots, a_n, 0, \dots, a_1, a_2, \dots, a_n, 0$ (wobei das Array 8-mal wiederholt wird) mit einer korrekten Antwort anhält. Dein DFA arbeitet im Allgemeinen korrekt, wenn er auf allen möglichen Arrays $a_1, a_2, \dots, a_n$ aus ganzen Zahlen von $1$ bis $n+1$ korrekt arbeitet (daher wird von probabilistischen Lösungen abgeraten).
Für $n = 4$ werden wir deinen DFA auf allen möglichen Arrays überprüfen. Für $n = 250$ haben wir keine Möglichkeit, ihn auf allen Arrays zu prüfen, daher werden wir ihn auf weniger als 5000 speziell ausgewählten Arrays testen. Es gibt zwei Tests in diesem Problem; beide Tests prüfen effektiv, ob dein Ansatz auf vielen Arrays gleichzeitig korrekt funktioniert.
Eingabe
Eine einzelne ganze Zahl $n$, die entweder gleich $4$ oder gleich $250$ ist.
Ausgabe
Gib in der ersten Zeile eine einzelne ganze Zahl $q$ ($1 \le q \le 4000$) aus, die die Anzahl der Zustände in deinem DFA angibt.
Gib in der $i$-ten der folgenden $q$ Zeilen $n + 2$ ganze Zahlen $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$ aus. Sie müssen alle zwischen $-(n + 1)$ und einschließlich $q - 1$ liegen und den Übergängen des Automaten entsprechen. Beachte, dass alle Zahlen in diesem Bereich liegen müssen: Selbst wenn eine Kombination aus Zustand $i$ und Eingabezahl $j$ bei keiner gültigen Eingabe jemals erreicht werden kann, muss der von dir angegebene Wert $\delta(i, j)$ dennoch im Bereich $[-(n + 1), q - 1]$ liegen.
Beispiel
Eingabe 1
4
Ausgabe 1
8 -3 0 0 1 0 0 2 1 1 1 1 1 -1 3 2 2 2 2 4 3 3 3 3 3 -5 4 4 4 4 5 6 5 5 5 5 5 -2 6 7 6 6 6 -4 7 7 7 7 7
Hinweis
Die Antwort für das Beispiel ist ein sehr langweiliger Automat, der vier Durchläufe verwendet, um zu prüfen, ob das Array die Zahlen 3, 1, 5 und 2 (in dieser Reihenfolge) enthält. Jeder der Durchläufe nutzt effektiv nur zwei Zustände, die angeben, ob er die im aktuellen Durchlauf gesuchte Zahl bereits gefunden hat. Wenn er das Ende des Arrays (das Zeichen 0) erreicht, ohne die gesuchte Zahl gefunden zu haben, hält er sofort an und gibt aus, dass die betreffende Zahl tatsächlich fehlt. Andernfalls nutzt er den nächsten Durchlauf, um nach der nächsten Zahl zu suchen. Wenn er schließlich alle vier gesuchten Zahlen gefunden hat, muss die Zahl 4 fehlen. Daher führt er keinen fünften Durchlauf auf der Suche nach der Zahl 4 durch (obwohl er dies hätte tun können, ohne die Beschränkungen hinsichtlich Zustandsanzahl und Durchläufen zu verletzen).
Natürlich hat dieser naive Ansatz für $n = 250$ keinerlei Aussicht auf Erfolg, und es wird etwas wesentlich Besseres benötigt. Der Hauptgrund für die Existenz des Beispiels besteht darin, das Ausgabeformat zu veranschaulichen.