1922B.md (1821B)
1 Source: https://codeforces.com/problemset/problem/1922/B 2 3 B. Forming Triangles 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You have $n$ sticks, numbered from $1$ to $n$. The length of the $i$-th stick is $2^{a_i}$. 22 23 You want to choose exactly $3$ sticks out of the given $n$ sticks, and form a non-degenerate triangle out of them, using the sticks as the sides of the triangle. A triangle is called non-degenerate if its area is strictly greater than $0$. 24 25 You have to calculate the number of ways to choose exactly $3$ sticks so that a triangle can be formed out of them. Note that the order of choosing sticks does not matter (for example, choosing the $1$-st, $2$-nd and $4$-th stick is the same as choosing the $2$-nd, $4$-th and $1$-st stick). 26 27 Input 28 29 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 Each test case consists of two lines: 32 33 * the first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$); 34 * the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$). 35 36 Additional constraint on the input: the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$. 37 38 Output 39 40 For each test case, print one integer — the number of ways to choose exactly $3$ sticks so that a triangle can be formed out of them. 41 42 Example 43 44 Input 45 46 ``` 47 4 48 49 7 50 51 1 1 1 1 1 1 1 52 53 4 54 55 3 2 1 3 56 57 3 58 59 1 2 3 60 61 1 62 63 1 64 ``` 65 66 Output 67 68 ``` 69 35 70 2 71 0 72 0 73 ``` 74 75 Note 76 77 In the first test case of the example, any three sticks out of the given $7$ can be chosen. 78 79 In the second test case of the example, you can choose the $1$-st, $2$-nd and $4$-th stick, or the $1$-st, $3$-rd and $4$-th stick. 80 81 In the third test case of the example, you cannot form a triangle out of the given sticks with lengths $2$, $4$ and $8$.