Le travailleur Farmer John veut une clôture à quatre côtés pour ses vaches. Il coupe une planche de longueur entière $N$ ($4\le N\le2,500$) en trois endroits pour obtenir quatre longueurs entières.
Ces longueurs peuvent être tous entiers positifs s’ils forment un quadrilatère. Combien de découpes permettent une clôture complète ?
Notes
- Les découpes diffèrent si l’une coupe à un endroit où l’autre ne coupe pas. Ne supprimez pas les symétries ni autres complications similaires.
- L’aire doit toutefois être supérieure à $0$.
- Réjouissez-vous : la réponse tient dans un entier signé sur 32 bits.
Entrée
- Ligne 1 : entier $N$.
Sortie
- Ligne 1 : un entier, le nombre de découpes en quatre morceaux formant un quadrilatère valide.
Exemples
Entrée 1
6
Sortie 1
6
Remarque
La planche mesure 6.
Il peut obtenir quatre morceaux de 10 façons : $(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)$. Mais les quatre suivantes ne forment pas un quadrilatère : $(1,1,1,3)$, $(1,1,3,1)$, $(1,3,1,1)$, $(3,1,1,1)$.
Sous-tâches
Points : 250.
Auteur du problème : Jeffrey Wang, 2007