Prologin
2024
Énoncé¶
Aujourd'hui, Joseph Marchand a décidé de vendre des crêpes lui aussi. Malheureusement, il est arrivé un peu tard : tous les autres marchands ont déjà positionné leur stand, et Joseph doit se faire une place parmi eux, en choisissant une des positions restantes.
On considère encore la plage comme un segment de la position 0 (le plus à l'ouest), à la position $N$ (le plus à l'est de la plage).
Les clients vont toujours acheter leurs crêpes auprès du marchand le plus proche d'eux, sans regarder les différences de prix ou de garnitures (c'est les vacances après tout, le moindre effort est épuisant). Joseph Marchand veut se placer afin d'avoir la plus grande zone d'influence possible sur les clients. Il doit se placer sur une position entière où un marchand n'est pas déjà installé. On rappelle que la zone d'influence d'un marchand est l'ensemble des points (pas forcément entiers) de la plage dont il est plus proche que n'importe quel autre marchand.
Joseph cherche à savoir quelle serait la taille de la plus grande zone d'influence qu'il peut avoir, arrondie à l'entier inférieur.
Entrée¶
L'entrée contiendra trois lignes. La première donnera la longueur $N$ de la plage (considérée comme une ligne droite), la deuxième le nombre $M$ de marchands déjà arrivés sur place, et la troisième listera les emplacements $E_i$ de ces marchands (numéros croissants compris entre $0$ et $N$).
Sortie¶
Vous afficherez un entier, la taille de la zone d'influence maximale que peut avoir Joseph.
Contraintes¶
- $1 \le N \le 1\ 000\ 000$
- $1 \le M \le 10\ 000$
- $1 \le E_i \le N$
