Grakn Forces 2020 B. Arrays Sum

B. Arrays Sum

Description

You are given a non-decreasing array of non-negative integers a1,a2,…,an. Also you are given a positive integer k.

You want to find m non-decreasing arrays of non-negative integers b1,b2,…,bm, such that:

The size of bi is equal to n for all 1≤i≤m. For all 1≤j≤n, aj=b1,j+b2,j+…+bm,j. In the other word, array a is the sum of arrays bi. The number of different elements in the array bi is at most k for all 1≤i≤m. Find the minimum possible value of m, or report that there is no possible m.

Input

The first line contains one integer t (1≤t≤100): the number of test cases.

The first line of each test case contains two integers n, k (1≤n≤100, 1≤k≤n).

The second line contains n integers a1,a2,…,an (0≤a1≤a2≤…≤an≤100, an>0).

Output

For each test case print a single integer: the minimum possible value of m. If there is no such m, print −1.

Example

input

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

output

-1 1 2 2 2 1

Note

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 a4=1 as the sum of zeros.

In the second test case, we can take b1=[3,3,3]. 1 is the smallest possible value of m.

In the third test case, we can take b1=[0,1,1,1,2,2,2,2,2,2,2] and b2=[0,0,1,1,1,1,1,2,2,2,2]. It’s easy to see, that ai=b1,i+b2,i for all i and the number of different elements in b1 and in b2 is equal to 3 (so it is at most 3). It can be proven that 2 is the smallest possible value of m.

题意： 给定一个数组a，要求构造数组b，b中的数字的种类的个数不能超过k种。使得$a[i]=\sum b[j][i]$，b[j][i]代表第j个b数组的第i个元素的值。最终输出最少需要几个这样的b数组。

题解： 第一次先弄前k个数，之后再弄后k-1个数，其余地方用0填充。

c++ AC 代码

#include<bits/stdc++.h> using namespace std; const int maxn = 200; int vis[maxn]; int main() { int T,x; scanf("%d",&T); while(T--) { memset(vis,0,sizeof(vis)); int n,k; scanf("%d%d",&n,&k); int cnt = 0; for(int i=0;i<n;i++) { scanf("%d",&x); if(!vis[x]) { vis[x] = 1; cnt++; // 记录有多少个不同大小的数 } } if(k == 1 && cnt != 1) puts("-1"); else if(k==1) puts("1"); else if(cnt <= k) puts("1"); else printf("%d\n",1 + (cnt - k + k -2)/(k-1));// cnt - k：除去前k个数，之后的数 然后除以（k-1），因为幺向上取整，所以（cnt - k）+ [(k - 1) - 1] } return 0; }

文章参考自：https://blog.csdn.net/tomjobs/article/details/108904124