Making Triangles 2
Time limit0.5sMemory limit1024 MB
Count the number of distinct triangles whose three sides are positive integers summing to n, up to congruence, where each side is a whole number of matchsticks.
- Level
Medium6 of 10
- Topics
- Math, Combinatorics, Implementation, Brute force
- Solved
- No attempts yet
Problem
You are given several matchsticks of equal length. You will arrange them on a plane to make triangles. A side of a triangle can be made by joining several matchsticks in a straight line, but you cannot bend or break a matchstick to form part of a side. Given the number of matchsticks, write a program that finds the number of distinct triangles that can be made using these matchsticks.
For example, the distinct triangles that can be made with 9 matchsticks are the 3 shown in Figure 1.
Figure 1
- You must use all the given matchsticks to make one triangle.
- If no triangle can be made, print 0. For example, when the number of given matchsticks is 1, 2, or 4, no triangle can be made.
- Congruent triangles count as the same triangle. For example, the triangles in Figure 2 that can be made with 5 matchsticks count as the same triangle.
Figure 2
Input
The first line gives the number of matchsticks. The number of matchsticks is between 1 and 1010 inclusive.
Output
On the first line, print the number of triangles that can be made.