Alice et Bob jouent à un jeu sur une grille de $N$ lignes et $M$ colonnes, où $M$ est pair. Il existe également un entier positif $K$. Initialement, chaque cellule de la grille contient une valeur comprise entre $0$ et $K$ inclus, et chaque cellule est non marquée. Les joueurs jouent à tour de rôle, Alice commençant en premier. Le jeu se termine lorsque le joueur dont c'est le tour ne peut plus effectuer de coup.
À chaque tour, un joueur sélectionne une cellule non marquée de la grille et un entier $a$ compris entre $0$ et $K$ inclus. Ensuite, il définit la valeur de cette cellule à $a$ et marque toutes les cellules de la même colonne que celle sélectionnée (y compris la cellule sélectionnée).
L'asymétrie de la grille est la somme des différences absolues entre la valeur d'une cellule et sa cellule correspondante lors d'une réflexion horizontale par rapport au milieu de la grille, sur toutes ces paires de cellules. Plus formellement, elle est définie par :
$$\sum_{1 \le i \le N} \left( \sum_{1 \le j \le M/2} |g_{i,j} - g_{i,M-j+1}| \right)$$
où $g_{i,j}$ est la valeur de la cellule située à la $i$-ème ligne en partant du haut et à la $j$-ème colonne en partant de la gauche. Par exemple, la grille $2 \times 4$ suivante a une asymétrie de $|8-0| + |4-2| + |6-6| + |7-9| = 12$.
| 8 | 4 | 2 | 0 |
|---|---|---|---|
| 6 | 7 | 9 | 6 |
Alice souhaite minimiser l'asymétrie de la grille à la fin du jeu, tandis que Bob souhaite la maximiser. Si les deux joueurs jouent de manière optimale, quelle est l'asymétrie de la grille finale ?
Entrée
La première ligne de l'entrée contient trois entiers séparés par des espaces $N$, $M$ et $K$ ($1 \le N, M \le 2000$, $M$ est pair, $1 \le K \le 10^9$).
Les $N$ lignes suivantes contiennent chacune $M$ entiers, où la $i$-ème ligne contient les entiers $g_{i,1}, \dots, g_{i,M}$ ($0 \le g_{i,j} \le K$), les valeurs des cellules de gauche à droite dans la $i$-ème ligne en partant du haut.
Le tableau suivant montre la répartition des 25 points disponibles :
| Points attribués | Bornes sur $N$ | Bornes sur $M$ | Bornes sur $K$ |
|---|---|---|---|
| 2 points | $N = 1$ | $2 \le M \le 2000$ | $1 \le K \le 10^9$ |
| 3 points | $1 \le N \le 2000$ | $M = 2$ | $K = 1$ |
| 3 points | $1 \le N \le 2000$ | $M = 2$ | $1 \le K \le 10$ |
| 3 points | $1 \le N \le 2000$ | $M = 2$ | $1 \le K \le 10^9$ |
| 4 points | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $K = 1$ |
| 4 points | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $1 \le K \le 10$ |
| 6 points | $1 \le N \le 2000$ | $2 \le M \le 2000$ | $1 \le K \le 10^9$ |
Sortie
Affichez un seul entier, l'asymétrie de la grille finale si Alice et Bob jouent de manière optimale.
Exemples
Exemples 1
3 2 1 1 0 1 0 0 0
Sortie 1
2
Remarque 1
Il n'y a que 2 colonnes, donc chaque joueur effectuera 1 coup. Alice commençant, elle peut effectuer les coups suivants :
- Sélectionner l'une des cellules avec une valeur de 1 dans la première colonne et définir sa valeur à 0. Ensuite, le coup optimal pour Bob est de définir la valeur de la cellule sur la même ligne dans la deuxième colonne à 1. La grille finale sera comme la grille originale avec exactement l'une des deux premières lignes de 0 et 1 inversée. Une telle grille a une asymétrie de $|1-0| + |0-1| + |0-0| = 2$.
- Sélectionner l'une des cellules dans la deuxième colonne et les deux premières lignes et définir sa valeur à 1. Ensuite, le coup optimal pour Bob est de définir la valeur de la cellule sur la même ligne dans la première colonne à 0. Encore une fois, la grille finale sera comme la grille originale avec exactement l'une des deux premières lignes de 0 et 1 inversée. Une telle grille a une asymétrie de 2.
- Sélectionner l'une des cellules dans la troisième ligne et définir sa valeur à 1. Ensuite, le coup optimal pour Bob peut être de définir la valeur de l'autre cellule dans la troisième ligne à 0. Notez que la cellule sélectionnée avait déjà la valeur 0, et qu'un tel coup est autorisé. Ensuite, la grille finale aura un 0 et un 1 dans chaque ligne, résultant en une asymétrie de 3.
- Sélectionner n'importe quelle cellule et définir sa valeur à sa valeur actuelle. Ensuite, le coup optimal pour Bob est de définir la valeur de la cellule dans la colonne restante non marquée et la troisième ligne à 1. La grille finale aura un 0 et un 1 dans chaque ligne, résultant en une asymétrie de 3.
Nous voyons que peu importe la façon dont Alice joue son coup, Bob sera capable de jouer de telle sorte que l'asymétrie soit d'au moins 2. Si Alice sélectionne son premier coup de manière optimale, elle peut s'assurer que Bob ne puisse pas rendre l'asymétrie finale supérieure à 2. Ainsi, l'asymétrie si les deux joueurs jouent de manière optimale est 2.
Exemples 2
1 10 21 4 2 0 6 7 6 9 9 10 21
Sortie 2
55
Remarque 2
Il n'y a qu'une seule ligne, donc pour chaque coup, le joueur actuel sélectionnera une cellule non marquée et la définira à n'importe quelle valeur entre 0 et 21 inclus. Le jeu se termine après que chaque joueur a effectué 5 coups, ce qui entraîne le marquage des 10 cellules.
Exemples 3
4 6 986754321 219759391 882760615 762656191 423465948 621463211 136889371 215621504 385106915 740086459 417915224 551800597 572994766 176308756 365311996 635683450 907755406 590000050 586083433 607011121 457147795 837558908 684766852 946836347 303039615
Sortie 3
3972378656
Remarque 3
Notez que la réponse peut ne pas tenir dans un entier 32 bits.