Suite aux résultats peu rassurants de l'étude que vous venez de faire sur la proximité des casernes de pompiers au sein de votre ville, les pouvoirs publics envisagent la création d'une caserne supplémentaire.
Vous êtes chargé de déterminer jusqu'à combien on peut réduire la distance maximale d'une intersection à sa caserne la plus proche, telle que définie dans le problème précédent. Pour ce faire, vous pouvez ajouter une caserne à l'intersection la plus appropriée de la ville, sans déplacer les autres.
Ainsi, dans l'exemple ci-contre, où les casernes initiales sont représentées par des points rouges, ajouter la nouvelle caserne au point noir permet d'obtenir une distance maximale de 3, entre chaque intersection et la caserne qui en est la plus proche. En bleu, on a représenté un exemple d'intersection se trouvant à une telle distance après l'ajout de la caserne. |
De plus, dans 50% des tests, on a K <= 100.
Vous devez écrire un seul entier sur la sortie : la distance maximale d'une intersection à la caserne la plus proche, une fois la caserne supplémentaire placée à la meilleure position possible.
entrée :
7 5 0 5 6 3 4 1 5 5 1 0
sortie :
3