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