تعود Bessie من رحلة خارجية طويلة، ويريد Farmer John لافتة جميلة «أهلاً بعودتك للبيت» بمرعاها لاستقبالها. تعلق بين عمودين بسلك طوله $L1$..$L2$ ($1 \le L1 \le L2; L1 \le L2 \le 1,500$).
أبعاد المرعى $W \times H$ ($1 \le W \le 1,000; 1 \le H \le 1,000$)، وعمود بكل نقطة إحداثياتها صحيحة. يختار بالضبط نقطتين من $(W + 1) * (H + 1)$ لتمسكا طرفي سلك اللافتة.
لا يريد إعاقة اللافتة، فلا يكون عمود مباشرة تحت السلك المشدود بين المختارين.
احسب الطرق. العدد كبير وقد لا يكفي عدد صحيح من 32 بت.
المثال $W = 2$ و$H = 1$:
* * *
* * *حجم اللافتة $2..3$؛ هناك $(2+1) * (1+1) = 6$ نقاط و$\binom{6}{2} = (6*5)/(2*1) = 15$ زوجاً ممكناً:
| $(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)$ |
أربعة فقط طولها $2..3$:
| الطول | الطول | ||
|---|---|---|---|
| $(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)$ و$(0,1)-(2,1)$ بهما عمود على الخط بين الطرفين فلا يصلحان.
فقط زوجان من 15 يصلحان.
الإدخال
- السطر 1: الأعداد الصحيحة $W$ و$H$ و$L1$ و$L2$ مفصولة بفراغات.
الإخراج
- السطر 1: عدد صحيح، عدد اللافتات الممكنة.
أمثلة
الإدخال 1
2 1 2 3
الإخراج 1
2
مؤلف المسألة: Nathan Pinsker، 2010