Traditionelles Spiel#11730
Vor vielen Jahren, als Chmyaaax noch nicht böse war, liebte er es, ein traditionelles Spiel aus den Stämmen des Link-Cut-Planetensystems mit Anton zu spielen. Das Spiel findet auf einem 1 \times n Brett statt, auf dem jede Zelle ein Zahlenpaar a_i, b_i enthält, alle Zahlen sind unterschiedlich. Es gibt auch ein Spielstück, das sich anfangs in Position befindet, und eine magische Waage, die anfangs beträgt. Die Spieler ziehen abwechselnd, wobei Chmyaaax zuerst zieht.
Angenommen, das Spielstück befindet sich derzeit in Zelle .
In seinem Zug kann Chmyaaax das Stück um Zellen nach vorne bewegen, wobei k > 0 ist, und k \cdot a_i Münzen von der Waage abziehen und die Position des Stücks auf i + k ändern.
In seinem Zug kann Anton das Stück um Zellen nach hinten bewegen, wobei k > 0 ist, und k \cdot b_i Münzen zur Waage hinzufügen und die Position des Stücks auf i - k ändern, oder er kann Magie verwenden, um das Stück zur letzten Zelle zu bewegen, wobei er (n - i) \cdot b_i Münzen zur Waage hinzufügt und das Stück auf Position setzt.
Zu jedem Zeitpunkt darf das Stück nicht vom Brett fallen (d.h., seine Position muss größer als und kleiner als n + 1 sein). Das Spiel endet, wenn das Stück Zelle erreicht. Chmyaaax' Ziel ist es, die Waage zu maximieren, während Antons Ziel darin besteht, sie zu minimieren. Wenn beide Spieler optimal spielen, wie hoch wird die Waage am Ende des Spiels sein? Es kann gezeigt werden, dass unter diesen Bedingungen das Spiel nicht unendlich fortgesetzt wird.
Die erste Zeile enthält eine ganze Zahl (2 \le n \le 10^6) — die Größe des Brettes, auf dem das Spiel stattfindet.
Die zweite Zeile enthält ganze Zahlen a_i (-10^9 \le a_i \le 10^9).
Die dritte Zeile enthält ganze Zahlen b_i (-10^9 \le b_i \le 10^9).
Für jedes Paar von und , so dass i \neq j und 1 \le i, j \le n, gilt a_i \neq a_j, b_i \neq b_j, a_i \neq b_j und für jedes (1 \le i \le n) gilt a_i \neq b_i.
Sie müssen den Wert der Waage am Ende des Spiels ausgeben, wenn beide Spieler optimal spielen.
Beispiel
34
7 2 3 4 5 6 9 8 10 1 19 12 13 14 15 16 17 18 11 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
7 2 3 4 5 6 9 8 10 1 19 12 13 14 15 16 17 18 11 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34-231Beispiel
3
2 10 3
15 3 720Beispiel
Beispiel 1
Beispiel 2
Im ersten Testbeispiel ist es für Chmyaaax optimal, vom Start zum Ende zu springen und die Waage um 33 \cdot 7 = 231 zu verringern, wodurch die Waage erreicht. Es kann bewiesen werden, dass es keine Strategie für ihn gibt, mit der er eine größere Waage erreichen kann.
Im zweiten Testbeispiel kann Chmyaaax zur Zelle springen und die Waage auf -5 \cdot 2 = -10 ändern, Anton kann das Stück zur letzten Zelle bewegen und der Waage 15 \cdot 2 = 30 hinzufügen, wodurch die Waage beträgt.
( Punkte): n \le 20;
( Punkte): n \le 50, -200 \le a_i, b_i \le 200;
( Punkte): n \le 5000;
( Punkte): n \le 10^5;
( Punkte): keine zusätzlichen Einschränkungen.