Read problems statements in mandarin chinese, russian and vietnamese as well. 

You are given N integers. In each step you can choose some K of the remaining numbers and delete them, if the following condition holds: Let the K numbers you've chosen be a_{1}, a_{2}, a_{3}, ..., a_{K} in sorted order. Then, for each i ≤ K - 1, a_{i+1} must be greater than or equal to a_{i} * C.

You are asked to calculate the maximum number of steps you can possibly make.

------ Input ------ 

The first line of the input contains an integer T, denoting the number of test cases. The description of each testcase follows.
The first line of each testcase contains three integers: N, K, and C
The second line of each testcase contains the N initial numbers

------ Output ------ 

For each test case output the answer in a new line.

------ Subtasks ------ 

Subtask #1 (40 points):

1 ≤ N ≤ 10^{3} 
1 ≤ Sum of N over all test cases ≤  10^{3} 

Subtask #2 (60 points):

Original constraints

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 3 * 10^{5}$
$1 ≤ K ≤ 64$
$2 ≤ C ≤ 50$
$1 ≤ a_{i} ≤ 10^{18}$
$1 ≤ Sum of N over all test cases ≤  3 * 10^{5} $

----- Sample Input 1 ------ 
2

6 3 2

4 1 2 2 3 1

6 3 2

1 2 2 1 4 4
----- Sample Output 1 ------ 
1

2
----- explanation 1 ------ 
Testcase 1: You can make one step by choosing {1, 2, 4}.
Testcase 2: You can make one step by choosing {1, 2, 4} and another by choosing {1, 2, 4}.

Difficulty: VERY_HARD
Tags: Greedy algorithms

Sorting

Complete search
Skill types: Complete search

Sorting

Greedy algorithms

Starter code:

Solutions:
def check(arr, x, k, c):
	vec = [[] for i in range(x)]
	l = 0
	for i in range(n):
		if len(vec[l]) == k:
			return True
		elif len(vec[l]) == 0 or vec[l][-1] * c <= arr[i]:
			vec[l].append(arr[i])
			l = (l + 1) % x
	for i in range(x):
		if len(vec[i]) != k:
			return False
	return True
t = int(input())
for _ in range(t):
	(n, k, c) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	arr.sort()
	(l, h) = (0, n // k + 1)
	ans = 0
	while h - l > 1:
		mid = (l + h) // 2
		if check(arr, mid, k, c):
			l = mid
			ans = max(ans, mid)
		else:
			h = mid
	print(ans)


def check(x):
	ls = [[] for _ in range(x)]
	curr = 0
	for i in range(n):
		if len(ls[curr]) == k:
			return True
		if len(ls[curr]) == 0 or ls[curr][-1] * c <= a[i]:
			ls[curr].append(a[i])
			curr = (curr + 1) % x
	if len(ls[curr]) == k:
		return True
	return False
for _ in range(int(input())):
	(n, k, c) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	l = 0
	r = n + 1
	while r - 1 > l:
		mid = (l + r) // 2
		if check(mid):
			l = mid
		else:
			r = mid
	print(l)


def check(arr, noOfSteps, C, K):
	if noOfSteps == 0:
		return True
	steps = []
	for i in range(noOfSteps):
		steps.append([])
	done = 0
	index = 0
	for i in range(len(arr)):
		if len(steps[index]) == 0:
			steps[index].append(arr[i])
			if len(steps[index]) == K:
				done += 1
			index = (index + 1) % noOfSteps
		elif arr[i] >= steps[index][-1] * C:
			steps[index].append(arr[i])
			if len(steps[index]) == K:
				done += 1
			index = (index + 1) % noOfSteps
	if done == noOfSteps:
		return True
	return False
for __ in range(int(input())):
	(N, K, C) = map(int, input().split())
	arr = list(map(int, input().split()))
	if K == 1:
		print(len(arr))
		continue
	arr.sort()
	low = -1
	high = N // K + 1
	while high - low > 1:
		mid = low + (high - low) // 2
		if check(arr, mid, C, K) == True:
			low = mid
		else:
			high = mid
	print(low)


def check(l, a, n, k, c):
	count = 0
	b = {}
	new = 0
	for i in range(l):
		b[i] = []
	for i in range(n):
		if len(b[new]) == 0:
			b[new].append(a[i])
			if len(b[new]) == k:
				count += 1
			new = (new + 1) % l
		elif a[i] >= b[new][-1] * c:
			b[new].append(a[i])
			if len(b[new]) == k:
				count += 1
			new = (new + 1) % l
	if count == l:
		return True
	else:
		return False
t = int(input())
while t > 0:
	(n, k, c) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a.sort()
	r = n // k + 1
	flag = 0
	low = 0
	while r - low > 1:
		mid = low + (r - low) // 2
		boo = check(mid, a, n, k, c)
		if boo:
			flag = 1
			low = mid
		else:
			r = mid
	if flag == 0:
		print('0')
	else:
		print(low)
	t -= 1


def check(x):
	v1 = []
	v2 = []
	for i in range(x):
		v1.append(a[i])
	p = x
	for i in range(1, k):
		v2 = []
		for j in range(len(v1)):
			while p < n and a[p] < v1[j] * c:
				p += 1
			if p >= n:
				return False
			v2.append(a[p])
			p += 1
		v1 = v2.copy()
	return True
for _ in range(int(input())):
	(n, k, c) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	lo = 0
	hi = n + 1
	while hi - lo > 1:
		mid = (lo + hi) // 2
		if check(mid):
			lo = mid
		else:
			hi = mid
	print(lo)


def check(x):
	l1 = [ls[i] for i in range(x)]
	pos = x
	for i in range(1, k):
		for j in range(x):
			while pos < n and ls[pos] < c * l1[j]:
				pos += 1
			if pos >= n:
				return False
			l1[j] = ls[pos]
			pos += 1
	return True
for _ in range(int(input())):
	(n, k, c) = map(int, input().split())
	ls = sorted(list(map(int, input().split())))
	(l, r) = (0, n)
	while r - l > 1:
		m = l + (r - l) // 2
		if check(m):
			l = m
		else:
			r = m
	print(l)


def fun(x):
	arr = [a[i] for i in range(x)]
	zz = x
	for i in range(1, k):
		for j in range(x):
			while zz < n and a[zz] < c * arr[j]:
				zz += 1
			if zz >= n:
				return False
			arr[j] = a[zz]
			zz += 1
	return True
for _ in range(int(input())):
	(n, k, c) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	(l, r) = (0, n)
	while r - l > 1:
		m = l + (r - l) // 2
		if fun(m):
			l = m
		else:
			r = m
	print(l)


def check(m):
	ptr = 0
	ds = [[] for i in range(m)]
	ele = 0
	for i in range(K):
		for j in range(m):
			if len(ds[j]) == 0 and ptr < len(a):
				ds[j].append(a[ptr])
				ele += 1
			else:
				while ptr < len(a) and a[ptr] < ds[j][i - 1] * C:
					ptr += 1
				if ptr < len(a):
					ds[j].append(a[ptr])
					ele += 1
			ptr += 1
	if ele == m * K:
		return 1
	else:
		return 0
T = int(input())
for _ in range(T):
	(N, K, C) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.sort()
	l = 0
	r = len(a) // K
	while l < r:
		mid = l + (r - l + 1) // 2
		if check(mid):
			l = mid
		else:
			r = mid - 1
	print(l)


raw_input = input

def fn(A, n, k, c, x):
	steps = [[] for _ in range(x)]
	j = 0
	for i in range(n):
		if len(steps[j]) == k:
			return True
		if len(steps[j]) == 0 or steps[j][-1] * c <= A[i]:
			steps[j].append(A[i])
			j = (j + 1) % x
	if len(steps[j]) == k:
		return True
	return False
for _ in range(int(raw_input())):
	(n, k, c) = map(int, raw_input().split())
	A = sorted([int(x) for x in raw_input().split()])
	(start, end) = (0, n + 1)
	while start < end - 1:
		mid = (start + end) // 2
		if fn(A, n, k, c, mid):
			start = mid
		else:
			end = mid
	print(start)


def chk(arr, n, k, c, ted):
	ok = 0
	cur = 0
	if ted == ok:
		return True
	it = [-1] * ted
	las = [0] * ted
	for i in range(n):
		if ted == ok:
			return True
		while it[cur] >= k:
			cur = (cur + 1) % ted
		if it[cur] == -1:
			las[cur] = arr[i]
			it[cur] = 1
			if it[cur] == k:
				ok = ok + 1
			cur = cur + 1
		elif las[cur] * c <= arr[i]:
			las[cur] = arr[i]
			it[cur] = it[cur] + 1
			if it[cur] == k:
				ok = ok + 1
			cur = cur + 1
		cur = cur % ted
	return ok == ted

def wrap(arr, n, k, c):
	arr.sort()
	l = -1
	r = n + 1
	while r - l > 1:
		mid = int((l + r) / 2)
		if chk(arr, n, k, c, mid):
			l = mid
		else:
			r = mid
	return l
t = int(input())
while t:
	nkc = input().split()
	N = int(nkc[0])
	K = int(nkc[1])
	C = int(nkc[2])
	arr = [0] * N
	x = input().split()
	for i in range(N):
		arr[i] = int(x[i])
	size = wrap(arr, N, K, C)
	print(size)
	t = t - 1


from math import inf

def fun(a, n, k, c, x):
	j = 0
	vec = [[] for i in range(x)]
	for i in range(n):
		if len(vec[j]) == k:
			return 1
		if len(vec[j]) == 0 or vec[j][-1] * c <= a[i]:
			vec[j].append(a[i])
			j = (j + 1) % x
	if len(vec[j]) == k:
		return 1
	else:
		return 0
for _ in range(int(input().strip())):
	(n, k, c) = map(int, input().strip().split())
	lst = list(map(int, input().strip().split()))
	lst.sort()
	start = 0
	end = n + 1
	while start < end - 1:
		mid = (start + end) // 2
		remain = fun(lst, n, k, c, mid)
		if remain == 1:
			start = mid
		else:
			end = mid
	print(start)


from math import inf

def check(z):
	index = 0
	d = [[] for _ in range(z)]
	for i in range(n):
		if len(d[index]) == 0 or (d[index][-1] * c <= nums[i] and d[index][-1] < inf / c):
			d[index].append(nums[i])
			index = (index + 1) % z
	for i in d:
		if len(i) < k:
			return (d, False)
	return (d, True)
T = int(input())
while T > 0:
	(n, k, c) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	nums.sort()
	lo = 1
	hi = n // k
	res = 0
	while lo <= hi:
		mid = (lo + hi) // 2
		(d, f) = check(mid)
		if f == True:
			res = mid
			lo = mid + 1
		else:
			hi = mid - 1
	print(res)
	T -= 1


def binary(l, n, m, c, k):
	li = []
	for i in range(m):
		li.append(l[i])
		i = m
	for j in range(1, k):
		for h in range(m):
			while i < n and li[h] * c > l[i]:
				i = i + 1
			if i < n:
				li[h] = l[i]
				i = i + 1
			else:
				return False
	return True
for q in range(int(input())):
	a = list(map(int, input().strip().split(' ')))
	n = a[0]
	k = a[1]
	c = a[2]
	li = list(map(int, input().strip().split(' ')))
	li.sort()
	p = 0
	l = 0
	r = n // k
	while l <= r:
		m = (l + r) // 2
		if binary(li, n, m, c, k):
			p = m
			l = m + 1
		else:
			r = m - 1
	print(p)


def find(N, K, C, A):
	start = N // K

	def check(X):
		if X == 0:
			return 1
		AA = [[] for i in range(X)]
		cur = 0
		for i in range(len(A)):
			x = A[i]
			if AA[cur] == []:
				AA[cur] += [x]
				cur = (cur + 1) % X
			elif len(AA[cur]) < K:
				up = AA[cur][-1]
				if x >= C * up:
					AA[cur] += [x]
					cur = (cur + 1) % X
			else:
				count = 0
				while len(AA[cur]) >= K:
					cur = (cur + 1) % X
					count += 1
					if count > X:
						return 1
				up = AA[cur][-1]
				if x >= C * up:
					AA[cur] += [x]
					cur = (cur + 1) % X
		good = 1
		for i in range(X):
			if len(AA[i]) < K:
				good = 0
		return good
	last = start
	if check(start) == 1:
		return start
	else:
		left = 0
		right = start
		mid = (right + left) // 2
		while 1:
			mid = (right + left) // 2
			if check(mid) == 1:
				if mid == left:
					return mid
				left = mid
			else:
				right = mid
		return mid
for _ in range(int(input())):
	(N, K, C) = list(map(int, input().strip().split(' ')))
	A = sorted(list(map(int, input().strip().split(' '))))
	print(find(N, K, C, A))