← 返回题目列表

AtCoder · past202309_g

G. N个三角形

中文机器翻译题面 查看原题

问题陈述

有 3N 坚持。的长度 i- 第根棍子是 A_i.

有多少种方法可以将它们分组为三元组,以便它们形成 N 三角形?

这里有两种形成方式 N 当且仅当存在以一种方式形成三角形而以另一种方式不形成三角形的三元组时,三角形才能被区分。
更多详细信息,请参见样本输入的描述 1.

约束

  • 1 \leq N \leq 4
  • 1 \leq A_i \leq 100
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 \ldots A_{3N}

输出

打印答案。


示例输入 1

2
3 3 3 4 4 6

示例输出 1

7

我们表示为 (i,j,k) 由以下三根棍子组成的三角形: i-th, j-th,以及 k-th。

有以下七种方式。请注意,等长的棍子是有区别的。

  • (1,2,3),(4,5,6)
  • (1,2,4),(3,5,6)
  • (1,2,5),(3,4,6)
  • (1,3,4),(2,5,6)
  • (1,3,5),(2,4,6)
  • (2,3,4),(1,5,6)
  • (2,3,5),(1,4,6)

另一方面,例如 1-st, 2-nd,和 6第根棍子不形成三角形。


示例输入 2

4
100 100 100 100 100 100 100 100 100 100 100 100

示例输出 2

15400