USACO

USACO 2021 US Open, Silver

Problem 2. Do You Know Your ABCs?

Contest has ended.

Log in to allow submissions in analysis mode

Farmer John's cows have been holding a daily online gathering on the "mooZ" video meeting platform. For fun, they have invented a simple number game to play during the meeting to keep themselves entertained.

Elsie has three positive integers $A$ , $B$ , and $C$ ( $1\le A\le B\le C$ ). These integers are supposed to be secret, so she will not directly reveal them to her sister Bessie. Instead, she tells Bessie $N$ ( $4\le N\le 7$ ) distinct integers $x_1,x_2,\ldots,x_N$ ( $1\le x_i\le 10^9$ ), claiming that each $x_i$ is one of $A$ , $B$ , $C$ , $A+B$ , $B+C$ , $C+A$ , or $A+B+C$ . However, Elsie may be lying; the integers $x_i$ might not correspond to any valid triple $(A,B,C)$ .

This is too hard for Bessie to wrap her head around, so it is up to you to determine the number of triples $(A,B,C)$ that are consistent with the numbers Elsie presented (possibly zero).

Each input file will contain $T$ ( $1\le T\le 100$ ) test cases that should be solved independently.

INPUT FORMAT (input arrives from the terminal / stdin):

The first input line contains

$T$ .

Each test case starts with $N$ , the number of integers Elsie gives to Bessie.

The second line of each test case contains $N$ distinct integers $x_1,x_2,\ldots,x_N$ .

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output the number of triples

$(A,B,C)$ that are consistent with the numbers Elsie presented.

SAMPLE INPUT:

10
7
1 2 3 4 5 6 7
4
4 5 7 8
4
4 5 7 9
4
4 5 7 10
4
4 5 7 11
4
4 5 7 12
4
4 5 7 13
4
4 5 7 14
4
4 5 7 15
4
4 5 7 16

SAMPLE OUTPUT:

For $x=\{4,5,7,9\}$ , the five possible triples are as follows:

$(2, 2, 5), (2, 3, 4), (2, 4, 5), (3, 4, 5), (4, 5, 7).$

SCORING:

In test cases 1-4, all $x_i$ are at most $50$ .
Test cases 5-6 satisfy $N=7$ .
Test cases 7-15 satisfy no additional constraints.

Problem credits: Benjamin Qi

Contest has ended. No further submissions allowed.