Ich werde an der OBI (Brasilianische Informatik-Olympiade) teilnehmen und versuche einige Übungen aus den letzten Jahren. Aber ich kann keine Lösung für diese Übung finden (ich habe sie übersetzt, also könnte es ein paar Fehler geben):
Schokoladenwettbewerb
Carlos und Paula haben gerade eine Tüte Schokoladenkugeln bekommen. Wie sie essen würden alles zu schnell, sie machten einen Wettbewerb:
- Sie werden abwechselnd nacheinander essen (Paula beginnt immer).
- Jedes Mal können sie nur von 1 bis M Kugeln essen, M entschieden von Paulas Mutter, damit sie nicht würgen.
- Wenn man in seiner Runde K-Bälle aß, kann die nächste keine K-Bälle essen.
- Wer nicht nach obigen Regeln spielen kann, verliert.
Im folgenden Beispiel mit M = 5 und 20 Bällen hat Carlos gewonnen:
%Vor%Beachte, dass Carlos am Ende 2 Bälle nicht essen konnte, um zu gewinnen, weil Paula in ihrem letzten Zug 2 gegessen hat. Aber Paula konnte den letzten Ball nicht essen, weil Carlos in seinem letzten Zug 1 gegessen hat, also kann Paula nicht spielen und verliert.
Beide sind sehr schlau und spielen optimal. Wenn es eine Abfolge von Drehungen gibt, die ihm den Sieg unabhängig von den Kurven des anderen sichert, wird er / sie diese Sequenzen spielen.
Aufgabe:
Sie müssen herausfinden, wer den Wettbewerb gewinnt, wenn beide optimal spielen.
Eingabe:
Die Eingabe enthält nur eine einzige Testgruppe, die von der Standardeingabe (normalerweise der Tastatur) gelesen werden sollte.
Der Eingang hat 2 ganze Zahlen N (2 ≤ N ≤ 1000000) und M (2 ≤ M ≤ 1000), wobei N die Anzahl der Kugeln und M die pro Umdrehung zulässige Anzahl ist.
Ausgabe:
Ihr Programm sollte in der Standardausgabe eine Zeile mit dem Namen des Gewinners ausgeben.
Beispiele:
%Vor%Ich habe versucht, das Problem zu lösen, aber ich habe keine Ahnung, wie.
Eine Lösung in C finden Sie hier: Ссылка Aber ich kann den Algorithmus nicht verstehen. Jemand hat auf einer anderen Website eine Frage zu diesem Problem gestellt, aber niemand hat darauf geantwortet.
Können Sie mir den Algorithmus erklären?
Hier sind die erwarteten Ergebnisse des Programms: Ссылка
Nehmen wir an, wir haben eine boolesche Funktion FirstPlayerWin (FPW), die zwei Argumente annimmt: die Anzahl der verbleibenden Pralinen (c) und die letzte Bewegung (l), dh die Anzahl der Pralinen, die in der vorherigen Runde genommen wurden Bewegung. Die Routine gibt true zurück, wenn und nur wenn der erste Spieler in dieser Situation einen Gewinn garantiert.
Der Basisfall ist, dass FPW (0, l) = false für jedes l! = 1
istAndererseits, um FPW (c, l) zu berechnen, ist FPW (c, l) wahr, wenn für jedes x & lt; = M, x & lt; = c, x! = 1, FPW (c - x, x) ist falsch. Sonst ist es falsch. Hier setzt die dynamische Programmierung an, denn jetzt wird die Berechnung von FPW auf die Berechnung von FPW für kleinere Werte von c reduziert.
Das Speichern der Einträge für diese Formulierung würde jedoch N * M Tabelleneinträge erfordern, während die von Ihnen angegebene Lösung nur 2N Tabelleneinträge verwendet.
Der Grund dafür ist, dass, wenn FPW (c, 0) wahr ist (der erste Spieler gewinnt, wenn ein Zug bei der Schokoladenzählung c verfügbar ist), aber FPW (c, x) ist falsch für x & gt; 0, FPW (c, y) für und y! = X muss wahr sein. Der Grund dafür ist, dass wenn die Verweigerung der Bewegung x den Spieler verliert, d. H. Der Spieler würde nur durch das Spielen von x gewinnen, dann ist die Bewegung x verfügbar, wenn y stattdessen gebannt wird. Es genügt also, für jeden Zählwert "c" höchstens einen verbotenen Zug zu speichern, der den Spieler dort verliert. So können Sie das Problem der dynamischen Programmierung so umgestalten, dass Sie anstelle des vollständigen zweidimensionalen Arrays FPW (c, x) zwei Arrays haben, eines speichert die Werte FPW (c, 0) und das andere speichert die einzelnen verbotenen Moves, die das verursachen der erste Spieler, der verliert anstatt zu gewinnen, falls vorhanden.
Wie Sie zum genauen Text des zitierten C-Programms gelangen, bleibt dem Leser als Übung überlassen.
Ich denke, dies ist noch eine weitere, dünn verkleidete Übung in der dynamischen Programmierung. Der Status des Spiels wird durch zwei Größen beschrieben: die Anzahl der verbleibenden Bälle und die Anzahl der Bälle, die im vorherigen Zug gegessen wurden. Wenn die Anzahl verbleibender Bälle & lt; = M ist, wird das Spiel entweder gewonnen (wenn die Anzahl nicht gleich der Anzahl ist, die im vorherigen Zug gegessen wurde) oder verloren (wenn es ist - kann man nicht alle Bälle essen, und dein Gegner kann die Bälle essen, die du verlässt).
Wenn Sie die Gewinn / Verlust-Situation für alle Zahlen von Bällen bis H und alle möglichen Anzahl von Bällen, die der vorherige Spieler gegessen hat, ausgearbeitet haben, und diese in einer Tabelle niederschreiben, dann können Sie die Antworten für alle erarbeiten Anzahl der Bälle bis H + 1. Ein Spieler mit H + 1 Bällen und k Bällen, die in der vorherigen Bewegung gegessen wurden, wird alle Möglichkeiten in Betracht ziehen - i Bälle für i = 1 bis M essen, mit Ausnahme des illegalen Wertes von k, wobei eine Position mit H + 1-i Bällen und einer vorherigen bleibt Bewegung von i. Sie können die Tabelle verwenden, die die Gewinn-Verlust-Situation für bis zu H-Bälle gibt, die übrig sind, um zu versuchen, ein legales k zu finden, das ihnen einen Gewinn gibt. Wenn sie einen solchen Wert finden können, ist die H + 1 / k-Position ein Gewinn. Wenn nicht, ist es ein Verlust, also können sie die Tabelle erweitern, um H + 1 Bälle zu bedecken, und so weiter.
Ich habe nicht den gesamten unkommentierten Beispielcode durchgearbeitet, aber es sieht so aus, als könnte es so etwas tun - mit einer dynamischen Programmierung wie Rekursion, um eine Tabelle zu erstellen.
Tags und Links algorithm