Bessie về từ chuyến đi nước ngoài dài, Farmer John muốn băng rôn đẹp «Chào mừng về nhà» ở đồng cỏ đón cô. Treo giữa hai cột bằng dây dài $L1$..$L2$ ($1 \le L1 \le L2; L1 \le L2 \le 1,500$).
Đồng cỏ $W \times H$ ($1 \le W \le 1,000; 1 \le H \le 1,000$), cột ở mọi điểm tọa độ nguyên. Chọn đúng hai trong $(W + 1) * (H + 1)$ điểm giữ hai đầu dây treo băng rôn.
Để không vướng, không cột nào ngay dưới dây căng giữa hai cột chọn.
Đếm cách treo. Số lớn nên số nguyên 32 bit có thể không đủ.
Ví dụ $W = 2$, $H = 1$:
* * *
* * *Cỡ $2..3$, có $(2+1) * (1+1) = 6$ điểm và $\binom{6}{2} = (6*5)/(2*1) = 15$ cặp ứng viên:
| $(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)$ |
Chỉ bốn cặp dài $2..3$:
| Độ dài | Độ dài | ||
|---|---|---|---|
| $(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)$ và $(0,1)-(2,1)$ có cột trên đường giữa hai đầu, không thích hợp.
Chỉ hai cặp trong 15 thích hợp.
Dữ liệu vào
- Dòng 1: bốn số nguyên $W$, $H$, $L1$, $L2$ cách nhau bởi dấu cách.
Dữ liệu ra
- Dòng 1: số nguyên là số băng rôn có thể.
Ví dụ
Dữ liệu vào 1
2 1 2 3
Dữ liệu ra 1
2
Tác giả: Nathan Pinsker, 2010