P16217 [ECUSTPC 2025] 克隆之击

Maddy 和 Baddy 决定通过智慧的方法一较高下！ Maddy 和 Baddy 初始有一个含有 $n$ 个正整数的多重集合 $S = \{a_1, a_1 + d, a_1 + 2d, \dots, a_1 + (n-1)d\}$，她们决定玩一个游戏，游戏规则如下： - 由 Maddy 开始操作，Maddy 和 Baddy 轮流操作。 - 每位玩家操作时需要 $S$ 中加入一个正整数。 - 当每位玩家都操作了 $m$ 次后，游戏结束。 - Maddy 的目标是让最终 $S$ 的 $k$-连通数尽可能大，Baddy 的目标是让最终 $S$ 的 $k$-连通数尽可能小。 其中的 $k$-连通数定义如下： - 先将 $S$ 排序，对于每组相邻的数，若其差大于 $k$，则将连通数增加 1，**连通数初始为 1。** - 一个等价的定义是在图上把 $S$ 上的元素作为顶点，差不大于 $k$ 的顶点之间连边，$k$-连通数即为连通块的数量。 假设 Maddy 和 Baddy 都是无比智慧的，在进行游戏时总会选择最优的策略，请帮助她们求出游戏结束时 $k$-连通数的值。

第一行输入一个整数 $T$ ($1 \le T \le 100$)，表示数据组数。 每组测试数据输入的唯一一行输入 5 个整数 $n, a_1, d, m$ 和 $k$ ($1 \le n, a_1, m \le 100$，$0 \le d, k \le 100$)，分别表示初始 $S$ 的大小，等差数列的首项和公差，游戏的轮数，参量 $k$ 的值。

每组测试数据输出一行一个整数 $ans$，表示在 Maddy 和 Baddy 选择最优的策略的情况下，游戏结束时 $S$ 的 $k$-连通数的值。

### 样例 1 解释 对于第 1 个样例，初始的 $S = \{(2 + 0 \times 3), (2 + 1 \times 3), (2 + 2 \times 3)\} = \{2, 5, 8\}$，下给出一个可能的双方策略： - Maddy 加入一个 13，$S = \{2, 5, 8, 13\}$； - Baddy 加入一个 3，$S = \{2, 3, 5, 8, 13\}$； - Maddy 加入一个 18，$S = \{2, 3, 5, 8, 13, 18\}$； - Baddy 加入一个 7，$S = \{2, 3, 5, 7, 8, 13, 18\}$。 排序后相邻差依次为 $D_1 = 1$，$D_2 = 2$，$D_3 = 2$，$D_4 = 1$，$D_5 = 5$，$D_6 = 5$，比 $k = 2$ 大的共有 2 个，$k$-连通数为 3。