ConvexHexagons
Member SRM 455 · 2009-12-03 · by Seyaua
Problem Statement
Petya likes triangles. He draws a trianglar grid using the following process: He starts off with an equilateral triangle. He then draws points on the edges of this triangle, dividing each edge up into N equal-length segments. Next, he connects each pair of points that is at equal distance from some vertex of the triangle with a straight line, ending up with N*N smaller equilateral triangles. An example of this figure with N = 4 is shown below.
However, he likes hexagons more than he likes triangles. How many non-degenerate convex hexagons can be formed using the line segments in his figure? This number can be very big, so return it modulo 1000000007.
Notes
- The length of each edge of every hexagon must be greater than zero.
Constraints
- N will be between 1 and 500000, inclusive.
3 Returns: 1
4 Returns: 7
There are 7 hexagons:
7 Returns: 232
104 Returns: 635471838
1 Returns: 0
Submissions are judged against all 114 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ConvexHexagons with a public method int find(int N) · 114 test cases · 2 s / 256 MB per case