1942C1.md (2814B)
1 Source: https://codeforces.com/problemset/problem/1942/C1 2 3 C1. Bessie's Birthday Cake (Easy Version) 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 [Proof Geometric Construction Can Solve All Love Affairs - manbo-p](https://soundcloud.com/alice-law-314125270/manbo-p-proof-geometric-construction-can-solve-all-love-affairs) 22 23 ⠀ 24 25 This is the easy version of the problem. The only difference between the two versions is the constraint on $y$. In this version $y = 0$. You can make hacks only if both versions are solved. 26 27 Bessie has received a birthday cake from her best friend Elsie, and it came in the form of a regular polygon with $n$ sides. The vertices of the cake are numbered from $1$ to $n$ clockwise. You and Bessie are going to choose some of those vertices to cut non-intersecting diagonals into the cake. In other words, the endpoints of the diagonals must be part of the chosen vertices. 28 29 Bessie would only like to give out pieces of cake which result in a triangle to keep consistency. The size of the pieces doesn't matter, and the whole cake does not have to be separated into all triangles (other shapes are allowed in the cake, but those will not be counted). 30 31 Bessie has already chosen $x$ of those vertices that can be used to form diagonals. She wants you to choose no more than $y$ other vertices such that the number of triangular pieces of cake she can give out is maximized. 32 33 What is the maximum number of triangular pieces of cake Bessie can give out? 34 35 Input 36 37 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 38 39 The first line of each test case consists of three integers, $n$, $x$, and $y$ ($4 \leq n \leq 10^9$, $2 \leq x \leq \min(n, 2 \cdot 10^5)$, $y = 0$) — the number of sides of the polygon, number of vertices Bessie has chosen, and the maximum number of other vertices you can choose. 40 41 The second line consists of $x$ distinct integers from $1$ to $n$, representing the vertices Bessie has chosen. 42 43 It is guaranteed the sum of $x$ over all test cases does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test case, output a single integer: the maximum number of non-intersecting triangular pieces of cake she can give out. 48 49 Example 50 51 Input 52 53 ``` 54 3 55 56 8 4 0 57 58 1 6 2 5 59 60 8 8 0 61 62 1 3 2 5 4 6 7 8 63 64 4 2 0 65 66 1 3 67 ``` 68 69 Output 70 71 ``` 72 2 73 6 74 2 75 ``` 76 77 Note 78 79 In test cases $1$, $2$ and $3$, you can get $2$, $6$ and $2$ non-intersecting triangular pieces of cake, respectively. A possible construction is shown in the following pictures: 80 81 The green dots represent vertices that can be used, the blue lines represent diagonals that are drawn, and the red numbers represent triangles that are counted. 82 83 