Bessie torna da un lungo viaggio all’estero e Farmer John vuole un bel «Bentornata a casa» nel suo pascolo. Lo striscione pende tra due pali su filo lungo $L1$..$L2$ ($1 \le L1 \le L2; L1 \le L2 \le 1,500$).
Il pascolo è $W \times H$ ($1 \le W \le 1,000; 1 \le H \le 1,000$), con palo a ogni punto intero. Sceglie esattamente due fra $(W + 1) * (H + 1)$ punti per le estremità del filo dello striscione.
Nessun palo deve stare direttamente sotto il filo teso tra i due scelti, per non interferire.
Conta i modi. Sono molti, un intero a 32 bit può non bastare.
Esempio $W = 2$, $H = 1$:
* * *
* * *Dimensione $2..3$; ci sono $(2+1) * (1+1) = 6$ punti e $\binom{6}{2} = (6*5)/(2*1) = 15$ coppie possibili:
| $(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)$ |
Solo quattro hanno lunghezza $2..3$:
| Lunghezza | Lunghezza | ||
|---|---|---|---|
| $(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)$ e $(0,1)-(2,1)$ hanno palo sulla linea tra estremi e non vanno bene.
Solo due su 15 sono ammissibili.
Input
- Riga 1: quattro interi $W$, $H$, $L1$, $L2$ separati da spazi.
Output
- Riga 1: un intero, il numero di striscioni possibili.
Esempi
Input 1
2 1 2 3
Output 1
2
Autore: Nathan Pinsker, 2010