[Solution] Chopping Carrots (Easy Version) solution codeforces

Chopping Carrots (Easy Version) solution codeforces – You are given an array of integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an of length 𝑛n, and an integer 𝑘k.

Table of Contents

[Solution] Chopping Carrots (Easy Version) solution codeforces

The cost of an array of integers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn of length 𝑛n is

max1𝑖𝑛(𝑎𝑖𝑝𝑖)min1𝑖𝑛(𝑎𝑖𝑝𝑖).max1≤i≤n(⌊aipi⌋)−min1≤i≤n(⌊aipi⌋).

Here, 𝑥𝑦⌊xy⌋ denotes the integer part of the division of 𝑥x by 𝑦y. Find the minimum cost of an array 𝑝p such that 1𝑝𝑖𝑘1≤pi≤k for all 1𝑖𝑛1≤i≤n.

Input

The first line contains a single integer 𝑡t (1𝑡1001≤t≤100) — the number of test cases.

The first line of each test case contains two integers 𝑛n and 𝑘k (1𝑛,𝑘30001≤n,k≤3000).

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎1𝑎2𝑎𝑛30001≤a1≤a2≤…≤an≤3000).

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 30003000.

Output

For each test case, print a single integer — the minimum possible cost of an array 𝑝p satisfying the condition above.

[Solution] Chopping Carrots (Easy Version) solution codeforces

Example
input

Copy
7
5 2
4 5 6 8 11
5 12
4 5 6 8 11
3 1
2 9 15
7 3
2 3 5 5 6 9 10
6 56
54 286 527 1436 2450 2681
3 95
16 340 2241
2 2
1 3
output

Copy
2
0
13
1
4
7
0

[Solution] Chopping Carrots (Easy Version) solution codeforces

In the first test case, the optimal array is 𝑝=[1,1,1,2,2]p=[1,1,1,2,2]. The resulting array of values of 𝑎𝑖𝑝𝑖⌊aipi⌋ is [4,5,6,4,5][4,5,6,4,5]. The cost of 𝑝p is max1𝑖𝑛(𝑎𝑖𝑝𝑖)min1𝑖𝑛(𝑎𝑖𝑝𝑖)=64=2max1≤i≤n(⌊aipi⌋)−min1≤i≤n(⌊aipi⌋)=6−4=2. We can show that there is no array (satisfying the condition from the statement) with a smaller cost.

In the second test case, one of the optimal arrays is 𝑝=[12,12,12,12,12]p=[12,12,12,12,12], which results in all 𝑎𝑖𝑝𝑖⌊aipi⌋ being 00.

In the third test case, the only possible array is 𝑝=[1,1,1]p=[1,1,1].

For Solution

Click Here

Leave a Comment