Making Triangles with Matchsticks

Interview

Time limit1sMemory limit128 MB

Summary
Given n identical matchsticks, count the number of non-congruent integer-sided triangles whose perimeter equals n.
Level

Easy3 of 10

Topics
Math, Combinatorics, Brute force
Solved
No attempts yet

Problem

You are given several matchsticks, all with the same length. Use all of them in the plane to form exactly one triangle.

A side of the triangle may be made by placing several matchsticks in a straight line. A matchstick may not be bent or cut to make part of a side.

Given the number of matchsticks, find how many distinct triangles can be made using every matchstick. Congruent triangles are counted as the same triangle.

With 9 matchsticks, there are 3 distinct triangles, as shown below.

Figure 1

Keep the following rules in mind.

  1. Every given matchstick must be used, and exactly one triangle must be formed.
  2. If no triangle can be formed, print 0. This happens when the number of matchsticks is 1, 2, or 4.
  3. Congruent triangles are considered the same. For instance, the following two triangles made with 5 matchsticks are the same triangle.

Figure 2

Input

The first line contains the number of matchsticks n.

1 <= n <= 50,000

Output

Print the number of distinct triangles that can be made.

Examples1

  1. Example 1

    Input
    9
    Expected output
    3