Bessie kommt von einer langen Auslandsreise zurück, und Farmer John will ein schönes „Willkommen zu Hause“-Banner auf ihrer Weide. Es hängt zwischen zwei Pfosten an einem Draht der Länge $L1$..$L2$ ($1 \le L1 \le L2; L1 \le L2 \le 1,500$).
Die Weide ist $W \times H$ ($1 \le W \le 1,000; 1 \le H \le 1,000$), mit Pfosten an jedem ganzzahligen Punkt. Von $(W + 1) * (H + 1)$ Punkten wählt er genau zwei für die Drahtenden des Banners.
Zur Vermeidung von Störungen darf unter dem straffen Draht zwischen den gewählten Pfosten keiner stehen.
Zähle die Möglichkeiten. Die Zahl ist groß und eine 32-Bit-Ganzzahl reicht vielleicht nicht.
Beispiel $W = 2$, $H = 1$:
* * *
* * *Bannergröße $2..3$; es gibt $(2+1) * (1+1) = 6$ Punkte und $\binom{6}{2} = (6*5)/(2*1) = 15$ mögliche Paare:
| $(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)$ |
Nur vier haben Länge $2..3$:
| Länge | Länge | ||
|---|---|---|---|
| $(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)$ und $(0,1)-(2,1)$ haben einen Pfosten auf der Linie zwischen den Enden und sind ungeeignet.
Nur zwei von 15 Paaren sind geeignet.
Eingabe
- Zeile 1: vier ganze Zahlen $W$, $H$, $L1$, $L2$ mit Leerzeichen.
Ausgabe
- Zeile 1: eine ganze Zahl, die Anzahl möglicher Banner.
Beispiele
Eingabe 1
2 1 2 3
Ausgabe 1
2
Aufgabenautor: Nathan Pinsker, 2010