Farmer John החרוץ רוצה גדר בת ארבע צלעות לפרות. לוח באורך שלם $N$ ($4\le N\le2,500$) ייחתך בשלושה מקומות לארבעה קטעים באורכים שלמים.
כל אורך שלם חיובי מותר אם הקטעים יוצרים מרובע. כמה דרכי חיתוך מאפשרות גדר מלאה?
הערות
- הדרכים שונות אם אחת חותכת במקום שבו השנייה אינה. אין לבטל סימטריות או סיבוכים דומים.
- אך השטח חייב להיות גדול מ־$0$.
- שמחו: התשובה נכנסת לשלם בעל סימן של 32 ביט.
קלט
- שורה 1: שלם $N$.
פלט
- שורה 1: שלם, מספר הדרכים לארבעה קטעים שיוצרים מרובע תקין.
דוגמאות
קלט 1
6
פלט 1
6
Note
אורך הלוח 6.
יש 10 דרכים לארבעה קטעים: $(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