P16217 [ECUSTPC 2025] Clone Strike

Maddy and Baddy decide to compete in a battle of wits. Initially, Maddy and Baddy have a multiset $S$ of $n$ positive integers: $S = \{a_1, a_1 + d, a_1 + 2d, \dots, a_1 + (n-1)d\}$. They decide to play a game with the following rules: - Maddy moves first, and Maddy and Baddy take turns. - On each move, the current player must add one positive integer into $S$. - The game ends after each player has made $m$ moves. - Maddy’s goal is to make the final $k$-connectivity number of $S$ as large as possible, while Baddy’s goal is to make it as small as possible. The $k$-connectivity number is defined as follows: - First sort $S$. For each pair of adjacent numbers, if their difference is greater than $k$, increase the connectivity number by 1. **The connectivity number starts at 1.** - An equivalent definition is: build a graph where each element of $S$ is a vertex, and add an edge between two vertices if their difference is at most $k$. The $k$-connectivity number is the number of connected components. Assume both Maddy and Baddy are perfectly smart and always choose the best strategy. Please compute the value of the $k$-connectivity number when the game ends.

The first line contains an integer $T$ ($1 \le T \le 100$), the number of test cases. For each test case, the only line contains five integers $n, a_1, d, m$ and $k$ ($1 \le n, a_1, m \le 100$, $0 \le d, k \le 100$), representing the initial size of $S$, the first term and common difference of the arithmetic progression, the number of rounds, and the parameter $k$, respectively.

For each test case, output one integer $ans$ in one line, meaning the $k$-connectivity number of $S$ at the end of the game when both Maddy and Baddy play optimally.

### Explanation for Sample 1 For the first sample, the initial $S = \{(2 + 0 \times 3), (2 + 1 \times 3), (2 + 2 \times 3)\} = \{2, 5, 8\}$. One possible sequence of moves is: - Maddy adds 13, $S = \{2, 5, 8, 13\}$. - Baddy adds 3, $S = \{2, 3, 5, 8, 13\}$. - Maddy adds 18, $S = \{2, 3, 5, 8, 13, 18\}$. - Baddy adds 7, $S = \{2, 3, 5, 7, 8, 13, 18\}$. After sorting, the adjacent differences are $D_1 = 1$, $D_2 = 2$, $D_3 = 2$, $D_4 = 1$, $D_5 = 5$, $D_6 = 5$. There are 2 differences greater than $k = 2$, so the $k$-connectivity number is 3. Translated by ChatGPT 5