Problem S4: Good Triplets

Problem DescriptionCopy Anchor Link

Andrew is a very curious student who drew a circle with the center at $(0,0)$ and an integer circumference of $C \geq 3$. The location of a point on the circle is the counter-clockwise arc length from the right-most point of the circle.

Andrew drew $N \geq 3$ points at integer locations. In particular, the $i$th point is drawn at location $P_i$ $(0 \le P_i \le C-1)$. It is possible for Andrew to draw multiple points at the same location.

A good triplet is defined as a triplet $(a,b,c)$ that satisfies the following conditions:

• $1 \le a < b < c \le N$.

• The origin $(0,0)$ lies strictly inside the triangle with vertices at $P_a$, $P_b$, and $P_c$. In particular, the origin is not on the triangle’s perimeter.

Lastly, two triplets $(a,b,c)$ and $(a',b',c')$ are distinct if $a \ne a'$, $b \ne b'$, or $c \ne c'$.

Andrew, being a curious student, wants to know the number of distinct good triplets. Please help him determine this number.

Input SpecificationCopy Anchor Link

The first line contains the integers $N$ and $C$, separated by one space.

The second line contains $N$ space-separated integers. The $i$th integer is $P_i$ $(0 \le P_i \le C-1)$.

The following table shows how the available 15 marks are distributed.

Output SpecificationCopy Anchor Link

Output the number of distinct good triplets.

Sample InputCopy Anchor Link

8 10 
0 2 5 5 6 9 0 0

Output for Sample InputCopy Anchor Link

6

Explanation of Output for Sample InputCopy Anchor Link

Andrew drew the following diagram.

The origin lies strictly inside the triangle with vertices $P_1$, $P_2$, and $P_5$, so $(1,2,5)$ is a good triplet. The other five good triplets are $(2,3,6)$, $(2,4,6)$, $(2,5,6)$, $(2,5,7)$, and $(2,5,8)$.