## CCC '22 S4 - Good Triplets

View as PDF

Points: 15 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem types
##### Canadian Computing Competition: 2022 Stage 1, Senior #4

Andrew is a very curious student who drew a circle with the center at and an integer circumference of . The location of a point on the circle is the counter-clockwise arc length from the right-most point of the circle.

Andrew drew points at integer locations. In particular, the point is drawn at location . It is possible for Andrew to draw multiple points at the same location.

A good triplet is defined as a triplet that satisfies the following conditions:

• .
• The origin lies strictly inside the triangle with vertices at , , and . In particular, the origin is not on the triangle's perimeter.

Lastly, two triplets and are distinct if , , or .

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

#### Input Specification

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

The second line contains space-separated integers. The integer is .

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

marksNone
marksNone
marks are all distinct (i.e., every location contains at most one point)
marksNone

#### Output Specification

Output the number of distinct good triplets.

#### Sample Input

8 10
0 2 5 5 6 9 0 0

#### Output for Sample Input

6

#### Explanation of Output for Sample Input

Andrew drew the following diagram.

The origin lies strictly inside the triangle with vertices , , and , so is a good triplet. The other five good triplets are , , , , and .