Facebook Hacker Cup Subround 1B - Spielautomat Hacker
Quelle: Facebook Hacker Cup.
Ich habe versucht, ein paar Listen mit Rückgabewerten aus der unten stehenden Funktion zu generieren, aber ich finde nicht, was es möglich macht, zukünftige Zufallszahlen vorherzusagen. Wie würde ich ein Problem wie dieses lösen?
Slot Machine Hacker
Sie haben sich kürzlich mit einem Typen angefreundet, der Software für Spielautomaten schreibt. Nachdem Sie ein wenig mit ihm rumgehangen haben, bemerken Sie, dass er eine Vorliebe dafür hat, sein Wissen darüber, wie die Spielautomaten funktionieren, zu zeigen. Schließlich bringen Sie ihn dazu, den für eine bestimmte Maschinenmarke verwendeten Algorithmus genau zu beschreiben. Der Algorithmus ist wie folgt:
%Vor%Diese Funktion gibt eine Ganzzahl in [0, 999] zurück; Jede Ziffer steht für eines von zehn Symbolen, die während eines bestimmten Maschinenzustands auf einem Rad erscheinen.Sekret wird anfangs auf einen nichtnegativen Wert eingestellt, der Ihnen unbekannt ist.
Indem Sie den Betrieb einer Maschine lange genug beobachten, können Sie den Wert des Geheimnisses bestimmen und so zukünftige Ergebnisse vorhersagen. Wenn Sie zukünftige Ergebnisse kennen, können Sie klug wetten und viel Geld gewinnen.
Eingabe Die erste Zeile der Eingabe enthält die positive Zahl T, die Anzahl der Testfälle. Danach folgen T-Testfälle. Jeder Testfall besteht aus einer positiven Ganzzahl N, der Anzahl der von Ihnen gemachten Beobachtungen. Die nächsten N Tokens sind Ganzzahlen von 0 bis 999, die Ihre Beobachtungen beschreiben. Ausgabe Geben Sie für jeden Testfall die nächsten 10 Werte aus, die von der Maschine durch Leerzeichen getrennt angezeigt werden. Wenn die von Ihnen beobachtete Sequenz nicht von der Maschine erzeugt werden kann, die Ihr Freund Ihnen beschrieben hat, drucken Sie stattdessen "Falsche Maschine". Wenn Sie die nächsten 10 Werte nicht eindeutig bestimmen können, drucken Sie stattdessen "Nicht genügend Beobachtungen".
Einschränkungen T = 20 1 ≤ N ≤ 100 Tokens in der Eingabe sind nicht länger als 3 Zeichen und enthalten nur die Ziffern 0-9.
Beispiel Eingabe
%Vor%Beispielausgabe
%Vor%3 Antworten
Verstanden!
Hier ist meine Lösung in Python:
%Vor%Es könnte wahrscheinlich optimiert werden (und gereinigt), aber da es in weniger als 30 Sekunden auf meinem 3 Jahre alten Laptop läuft, werde ich wahrscheinlich nicht die Mühe machen, es schneller zu machen ...
Das Programm akzeptiert nicht genau die gleiche Eingabe wie angefordert, hier ist wie man es benutzt:
%Vor%Wie Sie sehen können, reichen normalerweise drei Beobachtungen aus, um die zukünftigen Ergebnisse zu bestimmen.
Da es sehr mühsam ist, Mathematik in einem Texteditor zu schreiben, habe ich ein Bild von meiner Demonstration Erklärung gemacht:
secret liegt immer zwischen 0 und 10.000.000 inklusive wegen der Mod um 10.000.001. Die beobachteten Werte sind immer die letzten 3 Ziffern von secret (mit führenden Nullen abgestreift) aufgrund des Mods um 1.000. Es sind also die anderen Ziffern, die unbekannt sind und uns nur 10,001 Nummern zum Iterieren übrig lassen.
Für jedes prefix in 0..10.000 beginnen wir damit, dass secret aus den Ziffern von prefix gebildet wird, gefolgt von der ersten Zahl in der beobachteten Folge mit führenden Nullen. Wenn die Liste der generierten Zahlen der beobachteten Liste entspricht, haben wir einen potenziellen Startwert. Wenn wir mit keinen potenziellen Samen enden, wissen wir, dass dies eine falsche Maschine sein muss. Wenn wir mit mehr als einem enden, haben wir nicht genug Beobachtungen. Andernfalls erzeugen wir die nächsten 10 Werte mit dem einzelnen Seed.
Dies läuft in O (10.000NT), was O (20.000.000) für die gegebenen Einschränkungen ist. Hier ist ein Auszug aus meiner Lösung in C ++ (entschuldigen Sie den starken Gebrauch von Makros, ich benutze sie nur in Wettbewerben):
%Vor%Was ist hier bekannt? Die Formel für die Aktualisierung des Geheimnisses und die Liste der Beobachtungen. Was ist unbekannte? Der geheime Startwert.
Was könnte das Startgeheimnis sein? Wir können den möglichen Start begrenzen
Geheimnis zu 10.000 möglichen Werten, da der beobachtete Wert secret
% 1000 ist und das maximale Geheimnis 10.000.000 ist.
Die möglichen Startgeheimnisse sind dann
%Vor%Nur eine Teilmenge (falls vorhanden) dieser Geheimnisse wird auf einen Wert aktualisiert, der den nächsten anzeigt beobachteter Wert.
%Vor% Selbst wenn jeder possible Wert immer noch in new_possible wäre, würden wir nur 10.000 überprüfen
Zahlen für jede Beobachtung. Es ist jedoch unwahrscheinlich, dass viele Werte übereinstimmen
mehrere Beobachtungen.
Wiederholen Sie einfach diesen Prozess, und entweder die mögliche Liste ist leer, länger als eins, oder es wird genau eine Antwort haben.
Hier ist eine Funktion, um alles zusammenzufassen. (Sie benötigen die f von oben)