Énoncé
On considère ici une variante du jeu Risk dans laquelle un combat se déroule de la façon suivante :
Il y a deux joueurs : l'attaquant et le défenseur.
On dénote n le nombre d'unités de l'attaquant et m celui du défenseur.
On itère le procédé suivant :
L'attaquant jette min(3,n) dés et retient les deux meilleurs jets a1 et b1 (a1 >= b1) ou seulement a1 s'il n'a qu'une unité.
Le défenseur jette min(2,m) dés et obtient a2 et b2 (a2 >= b2) ou seulement a2 s'il n'a qu'une seule unité.
On compare ensuite a1 avec a2, et b1 avec b2 si les deux camps ont au moins deux unités. Pour chaque comparaison, l'attaquant perd une unité si son score est inférieur ou égal à celui du défenseur, sinon c'est le défenseur qui perd une unité.
L'attaque se termine lorsqu'un des deux joueurs n'a plus d'unité.
Voici un exemple :
l'attaquant attaque avec 3 unités et le défenseur en a autant.
La première itération donne : a1 = 6, b1 = 3 et a2 = 5, b2 = 5.
Chaque camp perd donc une unité.
L'attaquant n'a plus que deux jets de dés car n = 2.
La seconde itération donne : a1 = 6, b1 = 5 et a2 = 5, b2 = 4.
Le défenseur perd deux unités et perd donc le combat.
Dans cet exercice on cherche à trouver pour une valeur n fixée le nombre minimal d'unités que doit posséder le défenseur pour avoir une probabilité donnée de remporter le combat. On s'autorise 2s de temps d'exécution pour cet exercice, même s'il est possible de le faire en moins d'une seconde.
Entrée
L'entrée comporte sur une première ligne le nombre n (<1000) d'unités pour l'attaquant, suivie d'un retour à la ligne. Sur une seconde ligne se lit la probabilité minimale p que le défenseur doit avoir de remporter le combat. À noter que p peut être une valeur "assez" précise, de sorte qu'estimer la probabilité en réalisant un grand nombre de lancés n'est pas recommandé.
Sortie
La sortie comporte la valeur minimale m d'unités pour le défenseur pour que ses chances de remporter le combat soient d'au moins p. Ce nombre sera toujours inférieur à 1000.
Exemples
Squelette CamlLight
Squelette OCaml