Triples - MCPT: Mackenzie Competitive Programming Team

Triples

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 1.0s

Memory limit: 64M

Problem type

Given an array of integers, $a$ ~a~, compute the number of unique ways to satisfy the equation $a_i + a_j = a_k$ ~a_i + a_j = a_k~, where $i \neq j \neq k$ ~i \neq j \neq k~ and $a_i \leq a_j$ ~a_i \leq a_j~. To be unique, each counted equation after being filled in must never have been counted before.

Input Specification

The first line will contain a single integer $N$ ~N~, $3 \leq N \leq 5000$ ~3 \leq N \leq 5000~.

The next line will contain $N$ ~N~ space separated integers, describing the array. $1 \leq a_i \leq 10^6$ ~1 \leq a_i \leq 10^6~

Output Specification

The output will contain a single line, the number of unique triples that can be formed by the array.

Sample Input 1

4
1 5 3 2

Sample Output 1

Explanation for Sample 1

The unique equations are $1 + 2 = 3$ ~1 + 2 = 3~ and $2 + 3 = 5$ ~2 + 3 = 5~

Sample Input 2

5
1 1 1 2 3

Sample Output 2

Explanation for Sample 2

The unique equations are $1 + 1 = 2$ ~1 + 1 = 2~ and $1 + 2 = 3$ ~1 + 2 = 3~

Comments

0

MstrPikachu commented on Jan. 5, 2020, 10:29 p.m.

For the second sample, why is $N$ ~N~ equal to 4 when there are 5 elements in the array?

0

_ commented on Jan. 7, 2020, 1:49 a.m.

Fixed