Ein Kartenspiel, das als Prüfstein des Verstandes gilt, trägt den Namen „Kang“. In diesem Spiel hat jede Karte eine Punktzahl, die eine positive ganze Zahl ist. Zu Beginn erhältst du $N$ Karten auf die Hand, und weitere $M$ Karten liegen offen von links nach rechts aufgereih auf dem Tisch. Du kannst die Punktzahl jeder Karte sehen – sowohl der Karten auf deiner Hand als auch der Karten, die auf dem Tisch liegen. Danach kannst du in $k$ Runden jeweils eine weitere Karte vom Tisch ziehen, wobei du die Karten einzeln nacheinander von links nach rechts aufnehmen musst. Nach jeder Runde, in der du eine Karte gezogen hast, darfst du 1-mal Karten aus deiner Hand ablegen, und zwar beliebig viele Karten aus deiner Hand, die dieselbe Punktzahl haben. Du musst deinen Spielplan so gestalten, dass nach $k$ Runden des Ziehens vom Tisch und Ablegens aus der Hand die verbleibenden Karten auf deiner Hand eine möglichst kleine Gesamtpunktzahl aufweisen.
Betrachte das folgende Beispiel.
Angenommen, du hast zu Beginn fünf Karten mit den Punktzahlen $6, 3, 9, 6, 3$ auf der Hand, und die auf dem Tisch liegenden Karten haben von links nach rechts die Punktzahlen $4, 6, 9, 6$.
Fall $k = 1$: Wenn du nur 1 Karte vom Tisch ziehen darfst, lauten die Punktzahlen deiner Karten nach dem Ziehen der ersten Karte $6, 3, 9, 6, 3, 4$. Danach kannst du 1-mal Karten mit gleicher Punktzahl zum Ablegen auswählen. Die beste Wahl besteht darin, 2 Karten mit der Punktzahl $6$ abzulegen, sodass die Gesamtpunktzahl der verbleibenden Karten den kleinstmöglichen Wert $3 + 9 + 3 + 4 = 19$ annimmt.
Fall $k = 2$: Wenn du 2 Karten vom Tisch ziehen darfst, lautet die beste Strategie: Nachdem du die erste Karte mit der Punktzahl $4$ gezogen hast, wählst du aus, eine Karte mit der Punktzahl $9$ abzulegen. Die verbleibenden Karten auf deiner Hand haben die Punktzahlen $6, 3, 6, 3, 4$. Wenn du anschließend die 2. Karte mit der Punktzahl $6$ ziehst, kannst du 3 Karten mit der Punktzahl $6$ ablegen, wodurch die verbleibenden Karten die kleinstmögliche Gesamtpunktzahl von $3 + 3 + 4 = 10$ erreichen.
Fall $k = 3$: Wenn du 3 Karten vom Tisch ziehen darfst, lautet die beste Strategie: Wenn du die erste Karte ziehst, haben die Karten auf deiner Hand die Punktzahlen $6, 3, 9, 6, 3, 4$. Danach darfst du 1-mal Karten mit gleicher Punktzahl ablegen; am besten legst du beide Karten (2 Karten) mit der Punktzahl $3$ ab, sodass $6, 9, 6, 4$ auf deiner Hand verbleiben. Wenn du danach die 2. Karte mit der Punktzahl $6$ ziehst, kannst du 3 Karten mit der Punktzahl $6$ ablegen, sodass $9, 4$ auf der Hand bleiben. Und wenn du beim 3. Mal die Karte mit der Punktzahl $9$ ziehst, kannst du beide Karten (2 Karten) mit der Punktzahl $9$ ablegen, sodass die verbleibende Karte eine Gesamtpunktzahl von $4$ hat.
Fall $k = 4$: Wenn du 4 Karten vom Tisch ziehen darfst, lautet die beste Strategie: Nachdem du die erste Karte mit der Punktzahl $4$ gezogen hast, legst du eine Karte mit der Punktzahl $4$ ab, sodass Karten mit den Punktzahlen $6, 3, 9, 6, 3$ auf der Hand bleiben. Beim 2. Ziehen hat die Karte die Punktzahl $6$; der beste Weg ist es, beide Karten (2 Karten) mit der Punktzahl $3$ abzulegen, wodurch $6, 9, 6, 6$ auf der Hand bleiben. Beim 3. Ziehen hat die Karte die Punktzahl $9$; lege beide Karten (2 Karten) mit der Punktzahl $9$ ab. Und beim Ziehen der letzten Karte mit der Punktzahl $6$ kannst du 4 Karten mit der Punktzahl $6$ ablegen. Dieses Ablegen führt dazu, dass keine Karten mehr auf der Hand verbleiben, was bedeutet, dass die Gesamtpunktzahl der Karten $0$ beträgt.
Deine Aufgabe (Your Task)
Bestimme die „kleinstmögliche Gesamtpunktzahl der verbleibenden Karten auf der Hand“ nach Abschluss von $k$ Runden für $k = 1, 2, 3, \ldots, M$.
Diese Aufgabe verwendet ein Programmierformat, das vom üblichen Format abweicht und im echten Wettbewerb eingesetzt wird. Bitte beachte das Ende dieser Aufgabenstellung für Hinweise zur Verwendung.
Implementierungsdetails
Du musst die folgende Funktion implementieren:
std::vector<long long> capsize(std::vector<int> A, std::vector<int> B)Mit den folgenden Parametern:
- $A$ ist ein Array der Länge $N$, das die Nummern der Karten angibt, die sich zu Beginn auf der Hand befinden.
- $B$ ist ein Array der Länge $M$, das die Nummern der auf dem Tisch liegenden Karten in der Reihenfolge von links nach rechts angibt.
- Die Funktion muss ein Array $C$ der Länge $M$ zurückgeben, das die kleinstmögliche Gesamtpunktzahl der Karten auf der Hand nach $k$ Runden für $k = 1, 2, 3, \ldots, M$ darstellt.
Wenn beispielsweise $A = [6, 3, 9, 6, 3]$ und $B = [4, 6, 9, 6]$ ist, muss die Funktion das Array $[19, 10, 4, 0]$ zurückgeben.
Beschränkungen
- $1 \le N, M \le 10^6$
- $1 \le A[i] \le 10^9$ für jedes $i$ mit $1 \le i \le N$
- $1 \le B[i] \le 10^9$ für jedes $i$ mit $1 \le i \le M$
Teilaufgaben
| Testgruppe | Maximale Punktzahl dieser Testgruppe | Bedingungen |
|---|---|---|
| 1 | 5% | $N, M \le 5$ |
| 2 | 7% | $N \le 1\,000$ und $M = 1$ |
| 3 | 8% | $N, M \le 1\,000$, alle Karten (sowohl auf der Hand als auch auf dem Tisch) haben paarweise verschiedene Nummern |
| 4 | 12% | $N, M \le 1\,000$, alle zusätzlich gezogenen Karten haben denselben Wert |
| 5 | 16% | $N, M \le 1\,000$ |
| 6 | 28% | $N, M \le 100\,000$ |
| 7 | 24% | Keine zusätzlichen Bedingungen |
Hinweis
Programmierhinweise
Bei dieser Aufgabe unterscheidet sich die Art und Weise, wie das Programm geschrieben und an das Bewertungssystem (Grader) übermittelt wird, vom üblichen Format, bei dem die Teilnehmenden den Programmteil zum Einlesen der Eingabe und zum Ausgeben der Ergebnisse selbst schreiben müssen. In dieser Aufgabe müssen die Teilnehmenden lediglich den erforderlichen Berechnungsteil innerhalb der vorgegebenen Funktion schreiben. Sämtliche Eingabedaten stehen über die Parameter der Funktion zur Verfügung, und das Berechnungsergebnis muss ebenfalls über die Funktion zurückgegeben werden, ohne dass die Teilnehmenden Code für die Eingabe oder Ausgabe schreiben müssen.
Die Teilnehmenden erhalten mehrere Dateien wie folgt. Die Teilnehmenden dürfen nur die einzige in der Aufgabe festgelegte Datei bearbeiten und müssen diese Datei im System einreichen:
grader.cppist die Hauptdatei, die für das Einlesen der Eingabe und das Ausgeben der Ausgabe zuständig ist.kang.cppist die Datei, in der die Teilnehmenden die Berechnungen implementieren müssen und die im System eingereicht wird (in der Dateikang.cppdarf keine Funktionmain()vorhanden sein, andere Funktionen sind jedoch erlaubt).run_cpp.shist eine Datei, die die Teilnehmenden aufrufen können, um das gesamte Programm auszuführen.compile_cpp.shist eine Datei, die die Teilnehmenden aufrufen können, um das Programm zu kompilieren.
Die Teilnehmenden erhalten eine .zip-Datei, die vom System heruntergeladen werden kann; nach dem Entpacken (extract) sind darin alle 4 Dateien enthalten. Die Teilnehmenden sollten einen Texteditor oder eine IDE verwenden, um die Datei kang.cpp zu bearbeiten, und das Programm durch Aufrufen von compile_cpp.sh bzw. run_cpp.sh kompilieren oder ausführen.
Wenn die Teilnehmenden die Datei run_cpp.sh aufrufen, um das Programm auszuführen, arbeitet das Programm wie in der Datei grader.cpp festgelegt, deren Funktionsweise im Abschnitt „Beschreibung der Grader-Datei“ erläutert wird.