Problem Statement
Let's consider a regular polygon on the plane with n vertices, numbered from 0 to n-1, inclusive. The polygon's n-3 diagonals are called a triangulation if no two diagonals intersect at a point strictly inside the polygon. Two triangulations A and B are considered to be distinct if there are two vertices i and j such that A contains the diagonal between vertices i and j, and B doesn't contain this diagonal.
It's not hard to see that every triangulation breaks the polygon into n-2 triangles. The triangulation is called k-isosceles, if there are exactly k isosceles triangles among them. Given
Definition
- Class:
- IsoscelesTriangulations
- Method:
- getCount
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int getCount(int n, int k)
- (be sure your method is public)
Notes
- A triangle is called isosceles if it has at least 2 sides with equal length.
- A regular polygon is a polygon which is equiangular (all angles are congruent) and equilateral (all sides have the same length).
- A diagonal is a line joining two nonadjacent vertices of a polygon.
Constraints
- n will be between 3 and 50, inclusive.
- k will be between 0 and n-2, inclusive.
Examples
4
2
Returns: 2
We can have a diagonal between vertices 0 and 2 or between vertices 1 and 3. In both cases, there are 2 isosceles triangles.
3
0
Returns: 0
The only triangulation of an equilateral triangle contains no diagonals and 1 isosceles triangle (the polygon itself).
5
3
Returns: 5
A regular pentagon has 5 triangulations. Each of them is obtained by connecting one selected vertex with the two others that are not its neighbors, so each triangulation is 3-isosceles.
6
2
Returns: 12
All 2-isosceles triangles of a regular hexagon are shown in the picture below. All isosceles triangles in each triangulation are colored purple.
10
8
Returns: 10
All 8-isosceles triangulations of a regular 10-gon are shown in the picture below. All triangles in each triangulation are isosceles.
3
1
Returns: 1
4
0
Returns: 0
4
1
Returns: 0
5
0
Returns: 0
5
1
Returns: 0
5
2
Returns: 0
6
4
Returns: 2
7
3
Returns: 28
7
4
Returns: 14
8
6
Returns: 4
8
4
Returns: 64
8
2
Returns: 64
9
7
Returns: 9
9
5
Returns: 108
9
4
Returns: 24
9
3
Returns: 288
10
6
Returns: 140
10
5
Returns: 80
10
4
Returns: 560
10
3
Returns: 320
10
2
Returns: 320
36
31
Returns: 14496
14
4
Returns: 60928
34
4
Returns: 21406679
47
11
Returns: 105275978
23
5
Returns: 106887772
26
8
Returns: 83920238
16
4
Returns: 638976
37
9
Returns: 1198520
25
7
Returns: 65975697
12
7
Returns: 480
37
26
Returns: 65855403
29
9
Returns: 74024031
19
3
Returns: 1867776
22
17
Returns: 3696
27
22
Returns: 2232
13
2
Returns: 0
31
1
Returns: 0
12
9
Returns: 0
35
33
Returns: 0
35
0
Returns: 0
50
9
Returns: 58394758
50
47
Returns: 100
50
21
Returns: 31719829
50
39
Returns: 92087776
50
36
Returns: 15420199
50
48
Returns: 0
50
46
Returns: 1000
50
45
Returns: 16000
50
0
Returns: 0
50
1
Returns: 0
50
2
Returns: 101931970
50
3
Returns: 114751022
50
44
Returns: 226000
50
4
Returns: 11410498
50
10
Returns: 112698825
50
7
Returns: 20336526
49
23
Returns: 62241972
50
20
Returns: 28775584
50
25
Returns: 107780782