3454. Trapezoid Counting (Large)

单点时限: 4.0 sec

内存限制: 256 MB

In this problem, we will consider a trapezoid to be a convex quadrilateral with exactly one pair of parallel sides. If the lengths of the two non-parallel sides are equal, we say the trapezoid is isosceles.

You have some wooden sticks of various lengths, and you need to pick exactly four of them to form the four sides of an isosceles trapezoid. How many different sets of four sticks will allow this? Even if two sticks have the same length, they are considered to be different sticks. Sticks could not be bended and broke into parts.


The first line of the input gives the number of test cases, $T$. $T$ test cases follow; each consists of two lines. The first line consists of one integer $N$, the number of sticks. The second line consists of $N$ integers; the $i$-th of these, $L_i$, represents the length of the $i$-th stick.

  • Limits: $1 \le T \le 100, 1 \le L_i \le 10^9$.
  • Small dataset: $1 \le N \le 50$.
  • Large dataset: $1 \le N \le 5000$.


For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1), and $y$ is the number of different sets of four sticks that can form an isosceles trapezoid, as described above.


2 3 3 4 3
1 5 3 1
2 2 3 3
999999998 999999999 999999999 1000000000
3 4 1 4 2 5 3 1 3
Case #1: 5
Case #2: 0
Case #3: 0
Case #4: 1
Case #5: 73


In Sample Case #1, there are five ways to choose four out of the five given sticks, and any one of those five sets of four sticks can be used to form an isosceles trapezoid.

In Sample Case #2, note that the set {1, 1, 3, 5} cannot form an isosceles trapezoid, even though two of its sticks are of equal length.

In Sample Case #3, note that the set {2, 2, 3, 3} can form a rectangle, but in this problem, a rectangle is not considered to be an isosceles trapezoid.

8 人解决,11 人已尝试。

10 份提交通过,共有 17 份提交。

5.9 EMB 奖励。

创建: 6 年,6 月前.

修改: 6 年,6 月前.

最后提交: 3 年,7 月前.

来源: Kickstart 2017 Round E