All submissions for this problem are available.
There are N boxes numbered from 1..N which need to be filled with candies. Assume there are infinite candies. The boxes are arranged in increasing order of capacity, and the ith box has capacity i. Every box has a specific cost ci. You fill candies in rounds. In every round, you pick a subset of boxes and fill them with candies. This subset should be such that each subsequent box picked in a round should be more spacious than the previous one. Also, the difference in cost of consecutive boxes should be at least K.
What is the least number of rounds in which all boxes could be filled.
The first line contains the number of test cases T. T test cases follow.
Each case contains an integer N and K on the first line, followed by integers c1,...,cn on the second line.
1 <= T <= 100
1 <= N <= 300
1 <= ci <= 1000
1 <= K <= 1000
Output T lines, one for each test case, containing the minimum number of rounds in which all boxes could be filled.
Input: 2 3 2 5 4 7 5 1 5 3 4 5 6 Output: 2 1
For the first example, you can fill the boxes of cost 5 and 7 in the first round and the box with cost 4 in the next round. Note that the boxes with cost 5 and 4 cannot be filled consecutively because the costs should differ by at least K (which is 2). Also, the boxes cannot be filled in order 5,7,4 in one round because the boxes filled in a round should be in increasing capacity.
|Time Limit:||2.09701 - 4.19403 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions