Des diamants tombent du ciel !
Les diamants sont des carrés tels que dans le plan un diamant centré en (X, Y) aura ses sommets en (X-1, Y), (X, Y+1), (X+1, Y) et (X, Y-1).
Les diamants tombent suivant l'axe y, en X=0.
Le sol est suivant l'axe x.
Le premier diamant s'arrête lorsqu'il rencontre le sol, et s'enfonce, pour finir centré en (0,0).
Les diamants suivant tombent aussi en X=0, et s'ils rencontrent la pointe d'un diamant, glissent soit sur la gauche, soit sur la droite, avec une probabilité égale.
Ils continuent ensuite de glisser, et s'arrêtent quand ils sont bloqués par un autre diamant ou lorsqu'ils s'enfoncent dans le sol comme le premier diamant.
Notre objectif est, connaissant le nombre de diamants qui vont tomber du ciel, de déterminer la probabilité qu'il y ait un diamant à des coordonnées données.
L'entrée comporte le nombre de diamants qui tombent du ciel et les coordonnées (X, Y) pour lesquelles on veut avoir la probabilité, séparés par des espaces.
Le nombre de diamants est limité à 1.000.000.
Les coordonnées sont limitées à +/- 10.000.
La sortie indique la probabilité qu'un diamant soit à l'emplacement indiqué, suivie d'un retour à la ligne.
La sortie doit être indiqué avec une précision à 10^-3 près (0.1234 -> 0.123, 0.1236 -> 0.124) (utilisez le squelette qui fera ça à votre place !).
Si la probabilité est inférieure à 10^-4, on renvoie donc 0.
| Entrée | Sortie |
|---|---|