Bessie revient d’un long voyage à l’étranger. Farmer John veut une jolie bannière « Bienvenue à la maison » dans son pâturage pour son arrivée. Elle pend entre deux poteaux sur un fil de longueur $L1$..$L2$ ($1 \le L1 \le L2; L1 \le L2 \le 1,500$).
Le pâturage mesure $W \times H$ ($1 \le W \le 1,000; 1 \le H \le 1,000$) avec un poteau à chaque point entier. Parmi ces $(W + 1) * (H + 1)$ points, il en choisit exactement deux pour les extrémités du fil.
Pour éviter toute gêne à la bannière, aucun poteau ne doit être directement sous le fil tendu entre les deux choisis.
Trouvez le nombre de façons de la suspendre. Il est grand et un entier de 32 bits pourrait ne pas suffire.
Exemple avec $W = 2$, $H = 1$ :
* * *
* * *La taille est $2..3$. Il y a $(2+1) * (1+1) = 6$ points et $\binom{6}{2} = (6*5)/(2*1) = 15$ paires potentielles :
| $(0,0)-(0,1)$ | $(0,0)-(2,1)$ | $(0,1)-(2,1)$ | $(1,1)-(2,0)$ |
| $(0,0)-(1,0)$ | $(0,1)-(1,0)$ | $(1,0)-(1,1)$ | $(1,1)-(2,1)$ |
| $(0,0)-(1,1)$ | $(0,1)-(1,1)$ | $(1,0)-(2,0)$ | $(2,0)-(2,1)$ |
| $(0,0)-(2,0)$ | $(0,1)-(2,0)$ | $(1,0)-(2,1)$ |
Seules quatre ont une longueur $2..3$ :
| Longueur | Longueur | ||
|---|---|---|---|
| $(0,0)-(2,0)$ | $2.00$ | $(0,1)-(2,0)$ | $2.24$ |
| $(0,0)-(2,1)$ | $2.24$ | $(0,1)-(2,1)$ | $2.00$ |
$(0,0)-(2,0)$ et $(0,1)-(2,1)$ ont un poteau sur la ligne entre leurs extrémités et ne conviennent pas.
Seules deux paires sur 15 conviennent.
Entrée
- Ligne 1 : quatre entiers $W$, $H$, $L1$, $L2$ séparés par des espaces.
Sortie
- Ligne 1 : un entier, le nombre de bannières possibles.
Exemples
Entrée 1
2 1 2 3
Sortie 1
2
Auteur : Nathan Pinsker, 2010