Arrays Sum

题意翻译

### 题目描述 给你一个序列包含$n$个非负整数的不下降序列 $a_{1},a_{2},...,a_{n}$ ,同时给你一个正整数$k$. 你应找到$m$个不下降的序列 $b_{1},b_{2},...,b_{n}$ 满足: 1) 序列 $b_{i}$ 的大小为 $n$ $(1 \leq i \leq m)$. 2) $a_{j}=b_{1,j}+b_{2,j}+...+b_{m,j}(1 \leq j \leq n)$. 3) 序列 $b_{i}$ 中不同数字最多只有 $k$ 个 $(1 \leq i \leq m)$. 如果有解,求 $m$ 的最小值. 如果无解输出$-1$. ### 样例解释 对于测试数据一:没有$m$符合要求,因为所有序列$b$的所有数值应均为$0($因为$k=1,a_{1}=a_{2}=a_{3}=0)$,但这样便不可能使$b_{1,4}+b_{2,4}+...+b_{m,4}=1$$($因为$a_{4}=1$$)$. 对于测试数据二:$m$最小为$1$,可以取$b_{1}$=$[3,3,3]$. 对于测试数据三:$m$最小为$2$,可以取$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]$,可见这两个序列满足上述要求.

题目描述

You are given a non-decreasing array of non-negative integers $ a_1, a_2, \ldots, a_n $ . Also you are given a positive integer $ k $ . You want to find $ m $ non-decreasing arrays of non-negative integers $ b_1, b_2, \ldots, b_m $ , such that: - The size of $ b_i $ is equal to $ n $ for all $ 1 \leq i \leq m $ . - For all $ 1 \leq j \leq n $ , $ a_j = b_{1, j} + b_{2, j} + \ldots + b_{m, j} $ . In the other word, array $ a $ is the sum of arrays $ b_i $ . - The number of different elements in the array $ b_i $ is at most $ k $ for all $ 1 \leq i \leq m $ . Find the minimum possible value of $ m $ , or report that there is no possible $ m $ .

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \leq t \leq 100 $ ): the number of test cases. The first line of each test case contains two integers $ n $ , $ k $ ( $ 1 \leq n \leq 100 $ , $ 1 \leq k \leq n $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 100 $ , $ a_n > 0 $ ).

输出格式

For each test case print a single integer: the minimum possible value of $ m $ . If there is no such $ m $ , print $ -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

说明

In the first test case, there is no possible $ m $ , because all elements of all arrays should be equal to $ 0 $ . But in this case, it is impossible to get $ a_4 = 1 $ as the sum of zeros. In the second test case, we can take $ b_1 = [3, 3, 3] $ . $ 1 $ is the smallest possible value of $ m $ . In the third test case, we can take $ b_1 = [0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2] $ and $ b_2 = [0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2] $ . It's easy to see, that $ a_i = b_{1, i} + b_{2, i} $ for all $ i $ and the number of different elements in $ b_1 $ and in $ b_2 $ is equal to $ 3 $ (so it is at most $ 3 $ ). It can be proven that $ 2 $ is the smallest possible value of $ m $ .