← 返回题目列表

Codeforces · 1399/C

C. 船只比赛

中文机器翻译题面 查看原题

有 $$$n$$$ 人想参加划船比赛。第 $$$i$$$ 参与者的权重为 $$$w_i$$$。只有两人组成的团队才能参加本次比赛。作为组织者,您认为只允许总重量相同的球队参加是公平的。

因此,如果有 $$$k$$$ 队 $$$(a_1, b_1)$$$, $$$(a_2, b_2)$$$, $$$\dots$$$, $$$(a_k, b_k)$$$,其中 $$$a_i$$$ 是第 $$$i$$$ 队的第一个参赛者的体重, $$$b_i$$$ 是第 $$$i$$$ 队伍中第二名参赛者的体重,则应满足条件 $$$a_1 + b_1 = a_2 + b_2 = \dots = a_k + b_k = s$$$,其中 $$$s$$$ 是每队的总体重。

你的任务是选择这样的$$$s$$$,使得人们可以创建的团队数量尽可能多。请注意,每个参与者最多只能属于一个团队。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 参与者的数量。测试用例的第二行包含 $$$n$$$ 整数 $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le n$$$),其中 $$$w_i$$$ 是第 $$$i$$$ 个参与者的权重。

输出

对于每个测试用例,打印一个整数 $$$k$$$:如果您选择 $$$s$$$ 为最佳,则人们可以与总权重 $$$s$$$ 组成的最大团队数量。

示例

输入 #1

5
5
1 2 3 4 5
8
6 6 6 6 6 6 8 8
8
1 2 2 1 2 1 1 2
3
1 3 3
6
1 1 3 4 2 2

输出 #1

2
3
4
1
2

注意

在示例的第一个测试用例中,我们可以得出 $$$s=6$$$ 的最佳答案。那么第一艘船由参与者 $$$1$$$ 和 $$$5$$$ 使用,第二艘船由参与者 $$$2$$$ 和 $$$4$$$ 使用(索引与权重相同)。

在示例的第二个测试用例中,我们可以得出 $$$s=12$$$ 的最佳答案。然后,前 $$$6$$$ 参与者可以形成 $$$3$$$ 对。

在示例的第三个测试用例中,我们可以得出 $$$s=3$$$ 的最佳答案。答案是 $$$4$$$,因为我们有 $$$4$$$ 参与者,权重为 $$$1$$$ 和 $$$4$$$ 参与者,权重为 $$$2$$$。

在示例的第四个测试用例中,我们可以得出 $$$s=4$$$ 或 $$$s=6$$$ 的最佳答案。

在示例的第五个测试用例中,我们可以得出 $$$s=3$$$ 的最佳答案。请注意,体重为 $$$3$$$ 的参与者无法使用该船,因为列表中没有适合他的配对。