Der fleißige Farmer John will einen vierseitigen Zaun für die Kühe. Ein Brett ganzzahliger Länge $N$ ($4\le N\le2,500$) wird an drei Stellen in vier ganzzahlige Stücke geschnitten.
Die Längen können beliebige positive ganze Zahlen sein, wenn sie ein Viereck bilden. Wie viele Schnittweisen ergeben einen vollständigen Zaun?
Hinweise
- Schnittweisen sind verschieden, wenn eine einen Schnitt an einer Stelle hat, die die andere nicht hat. Symmetrien und ähnliche Komplikationen nicht entfernen.
- Die Fläche muss aber größer als $0$ sein.
- Erfreulich: die Antwort passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl.
Eingabe
- Zeile 1: ganze Zahl $N$.
Ausgabe
- Zeile 1: ganze Zahl der Schnittweisen in vier Stücke für ein gültiges Viereck.
Beispiele
Eingabe 1
6
Ausgabe 1
6
Hinweis
Das Brett hat Länge 6.
Es gibt 10 Schnittweisen in vier Stücke: $(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)$. Doch folgende vier bilden kein Viereck: $(1,1,1,3)$, $(1,1,3,1)$, $(1,3,1,1)$, $(3,1,1,1)$.
Teilaufgaben
Punkte: 250.
Aufgabenautor: Jeffrey Wang, 2007