← 返回题目列表

Codeforces · 1408/B

B. 数组总和

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

给定一个由非负整数组成的非递减数组 $$$a_1, a_2, \ldots, a_n$$$。此外,您还会获得一个正整数 $$$k$$$。

您想要找到 $$$m$$$ 非负整数的非递减数组 $$$b_1, b_2, \ldots, b_m$$$,这样:

- 对于所有 $$$1 \leq i \leq m$$$,$$$b_i$$$ 的大小等于 $$$n$$$。
- 对于所有 $$$1 \leq j \leq n$$$,$$$a_j = b_{1, j} + b_{2, j} + \ldots + b_{m, j}$$$。换句话说,数组 $$$a$$$ 是数组 $$$b_i$$$ 的和。
- 对于所有 $$$1 \leq i \leq m$$$,数组 $$$b_i$$$ 中不同元素的数量最多为 $$$k$$$。

求 $$$m$$$ 的最小可能值,或者报告不存在可能的 $$$m$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$):测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$, $$$k$$$ ($$$1 \leq n \leq 100$$$, $$$1 \leq k \leq n$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 100$$$, $$$a_n > 0$$$)。

输出

对于每个测试用例,打印一个整数:$$$m$$$ 的最小可能值。如果没有这样的$$$m$$$,则打印$$$-1$$$。

示例

输入 #1

6
4 1
0 0 0 1
3 1
3 3 3
11 3
0 1 2 2 3 3 3 4 4 4 4
5 3
1 2 3 4 5
9 4
2 2 3 5 7 11 13 13 17
10 7
0 1 1 2 3 3 4 5 5 6

输出 #1

-1
1
2
2
2
1

注意

在第一个测试用例中,不可能有$$$m$$$,因为所有数组的所有元素都应该等于$$$0$$$。但在这种情况下,不可能得到 $$$a_4 = 1$$$ 作为零的总和。

在第二个测试用例中,我们可以取 $$$b_1 = [3, 3, 3]$$$。 $$$1$$$ 是 $$$m$$$ 的最小可能值。

在第三个测试用例中,我们可以取 $$$b_1 = [0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]$$$ 和 $$$b_2 = [0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2]$$$。很容易看出,对于所有$$$i$$$,$$$a_i = b_{1, i} + b_{2, i}$$$,并且$$$b_1$$$和$$$b_2$$$中不同元素的数量等于$$$3$$$(因此最多为$$$3$$$)。可以证明$$$2$$$是$$$m$$$的最小可能值。