No.3128 Isosceles Triangle
タグ : / 解いたユーザー数 108
作問者 : 👑
loop0919
/ テスター :
lif4635
Iroha_3856
ルク
問題文
茜ちゃんと葵ちゃんは、幾何の勉強をしています。
勉強を進めていくうちに、二等辺三角形に興味を持ったようです。
長さ $N$ の数列 $A = (A_1, A_2, \cdots, A_N)$ が与えられます。
以下の条件を満たす整数の組 $(i, j, k)$ の個数を求めてください。
- $1 \leq i < j < k \leq N$
- 辺の長さがそれぞれ $A_i, A_j, A_k$ となる、非退化な（正三角形を除く）二等辺三角形が存在する。
非退化な三角形とは
非退化な三角形とは、$3$ つの頂点が同一直線上に並ばない三角形を指します。
制約
- $3 \leq N \leq 3 \times 10^5$
- $1 \leq A_i \leq 10^9 ~ (1 \leq i \leq N)$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
出力
問題文中の条件を満たす整数の組 $(i, j, k)$ の個数を出力してください。
サンプル
サンプル1
入力
5 2 2 3 5 5
出力
4
$(i, j, k) = (1, 2, 3), (1, 4, 5), (2, 4, 5), (3, 4, 5)$ の $4$ つが条件を満たします。
例えば $(i, j, k) = (1, 2, 3)$ のとき、辺の長さがそれぞれ $A_1 = 2,~ A_2 = 2,~ A_3 = 3$ となる非退化な二等辺三角形が存在します。
ただし、$(i, j, k) = (1, 2, 5)$ のとき、辺の長さがそれぞれ $2, 2, 5$ となる非退化な二等辺三角形が存在しないため、条件を満たさないことに注意してください。
サンプル2
入力
3 10 10 10
出力
0
正三角形を除いて数えることに注意してください。
サンプル3
入力
15 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
出力
79
サンプル4
入力
12 2 5 6 5 6 5 6 2 5 2 5 6
出力
118
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。