#PU1135. USACO 2021 US Open, Silver — Problem 2. Do You Know Your ABCs?

USACO 2021 US Open, Silver — Problem 2. Do You Know Your ABCs?

USACO 2021 US Open, Silver — Problem 2. Do You Know Your ABCs?

题目描述

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 AA, BB, and CC (1≤A≤B≤C1\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 NN (4≤N≤74\le N\le 7) distinct integers x1,x2,…,xNx_1,x_2,\ldots,x_N (1≤xi≤1091\le x_i\le 10^9), claiming that each xix_i is one of AA, BB, CC, A+BA+B, B+CB+C, C+AC+A, or A+B+CA+B+C. However, Elsie may be lying; the integers xix_i might not correspond to any valid triple (A,B,C)(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)(A,B,C) that are consistent with the numbers Elsie presented (possibly zero). Each input file will contain TT (1≤T≤1001\le T\le 100) test cases that should be solved independently.

输入格式

The first input line contains TT. Each test case starts with NN, the number of integers Elsie gives to Bessie. The second line of each test case contains NN distinct integers x1,x2,…,xNx_1,x_2,\ldots,x_N.

输出格式

For each test case, output the number of triples (A,B,C)(A,B,C) that are consistent with the numbers Elsie presented.

数据范围

In test cases 1-4, all xix_i are at most 5050. Test cases 5-6 satisfy N=7N=7. Test cases 7-15 satisfy no additional constraints. Problem credits: Benjamin Qi

样例

样例 1

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
1
3
5
1
4
3
0
0
0
1
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).$$