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
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.
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.
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
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
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≤𝑖≤𝑛(⌊𝑎𝑖𝑝𝑖⌋)=6−4=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].