Do You Know Your ABCs?

题目描述

Farmer John 的奶牛们每天都会在“mooZ”视频会议平台上进行线上聚会。为了娱乐，她们发明了一个简单的数字游戏在会议中玩。

Elsie 有三个正整数 $A$, $B$, $C$（$1\le A\le B\le C$）。这些整数本应是秘密，所以她不会直接把它们告诉她的姐姐 Bessie。相反，她会告诉 Bessie $N$（$4\le N\le 7$）个互不相同的整数 $x_1,x_2,\ldots,x_N$（$1\le x_i\le 10^9$），并声称每个 $x_i$ 都是 $A$, $B$, $C$, $A+B$, $B+C$, $C+A$ 或 $A+B+C$ 之一。然而，Elsie 可能在撒谎；这些整数 $x_i$ 可能并不对应任何合法的三元组 $(A,B,C)$。

这对 Bessie 来说太难理解了，所以需要你来确定：与 Elsie 给出的数字相一致的三元组 $(A,B,C)$ 的数量（可能为 0）。

每个输入文件包含 $T$（$1\le T\le 100$）组测试用例，它们应当相互独立地求解。

输入格式

第一行输入 $T$。

每个测试用例以 $N$ 开始，表示 Elsie 给 Bessie 的整数个数。 每个测试用例的第二行包含 $N$ 个互不相同的整数 $x_1,x_2,\ldots,x_N$。

输出格式

对于每个测试用例，输出与 Elsie 给出的数字相一致的三元组 $(A,B,C)$ 的数量。

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

提示

对于 $x=\{4,5,7,9\}$，五个可能的三元组如下：

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

SCORING: 在测试用例 1-4 中，所有 $x_i$ 均不超过 $50$。 测试用例 5-6 满足 $N=7$。 测试用例 7-15 不满足额外限制。 题目来源：Benjamin Qi

标签: USACO|2021|Silver

来源

USACO|2021|Silver