يريد Farmer John المجتهد سياجًا رباعي الجوانب للأبقار. لديه لوح بطول صحيح $N$ ($4\le N\le2,500$) يقطعه في ثلاثة مواضع لأربع قطع بأطوال صحيحة.
يجوز أي طول صحيح موجب لكل قطعة إن شكلت سياجًا رباعي الأضلاع. كم طريقة قطع تصنع سياجًا كاملًا؟
ملاحظات
- تختلف طريقتان إذا كان لأحدهما قطع في موضع دون الأخرى. لا تحذف التناظرات ولا تقلق بشأن تعقيدات مشابهة.
- لكن المساحة يجب أن تكون أكبر من $0$.
- افرح: الجواب يتسع له عدد صحيح موقّع من 32 بت.
الإدخال
- السطر 1: العدد الصحيح $N$.
الإخراج
- السطر 1: عدد صحيح، عدد طرق القطع لأربع قطع تشكل رباعيًا صالحًا.
أمثلة
الإدخال 1
6
الإخراج 1
6
ملاحظة
طول اللوح 6.
يمكن قطعه لأربع قطع بعشر طرق: $(1,1,1,3)$; $(1,1,2,2)$; $(1,1,3,1)$; $(1,2,1,2)$; $(1,2,2,1)$; $(1,3,1,1)$; $(2,1,1,2)$; $(2,1,2,1)$; $(2,2,1,1)$; $(3,1,1,1)$. لكن الأربع التالية لا تشكل رباعيًا: $(1,1,1,3)$, $(1,1,3,1)$, $(1,3,1,1)$, $(3,1,1,1)$.
المهام الفرعية
النقاط: 250.
صاحب المسألة: Jeffrey Wang، 2007