← 返回题目列表

Codeforces · 1942/C1

C1. 贝西的生日蛋糕(简单版)

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

这是问题的简单版本。两个版本之间的唯一区别是对 $$$y$$$ 的约束。在此版本中$$$y = 0$$$。只有两个版本都解决了,你才能进行黑客攻击。

Bessie 收到了她最好的朋友 Elsie 寄来的生日蛋糕,它是一个正多边形,有 $$$n$$$ 边。蛋糕的顶点顺时针编号为从 $$$1$$$ 到 $$$n$$$。您和贝西将选择其中一些顶点来将不相交的对角线切入蛋糕。换句话说,对角线的端点必须是所选顶点的一部分。

Bessie 只想分发一块蛋糕,形成三角形以保持一致性。块的大小并不重要,整个蛋糕不必分成所有三角形(蛋糕中允许有其他形状,但这些不会被计算在内)。

Bessie 已经选择了 $$$x$$$ 个可用于形成对角线的顶点。她希望你选择不超过 $$$y$$$ 个其他顶点,这样她可以给出的三角形蛋糕的数量就最大化。

贝西最多能给出多少块三角形蛋糕?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行由三个整数组成,$$$n$$$、$$$x$$$ 和 $$$y$$$ ($$$4 \leq n \leq 10^9$$$, $$$2 \leq x \leq \min(n, 2 \cdot 10^5)$$$, $$$y = 0$$$) — 边数多边形的数量、Bessie 选择的顶点数以及您可以选择的其他顶点的最大数量。

第二行由 $$$x$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$,代表 Bessie 选择的顶点。

保证所有测试用例的 $$$x$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数:她可以给出的不相交三角形蛋糕的最大数量。

示例

输入 #1

3
8 4 0
1 6 2 5
8 8 0
1 3 2 5 4 6 7 8
4 2 0
1 3

输出 #1

2
6
2

注意

在测试用例$$$1$$$、$$$2$$$和$$$3$$$中,分别可以得到$$$2$$$、$$$6$$$和$$$2$$$不相交的三角形蛋糕。下图显示了一种可能的结构:

绿点代表可以使用的顶点,蓝线代表绘制的对角线,红色数字代表计算的三角形。