Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

You are a warrior and you have to fight $N$ enemy warriors (numbered $1$ through $N$) one by one, in any order you choose. You have to win as many of these fights as possible.

Each warrior has some amount of power, which changes when the warrior fights. For each $i$, the $i$-th enemy warrior has power $P_{i}$. When you have power $x$ and you fight an enemy warrior with power $y$, the following happens:
if $x > y$, you kill the enemy warrior and your power changes to $2(x-y)$
otherwise (if $x ≤ y$), the enemy warrior kills you

You should answer $Q$ queries. In each query, you are given your initial power $X$ and you should find the maximum number of warriors you can kill if you are starting with power $X$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $Q$.
The second line contains $N$ space-separated integers $P_{1}, P_{2}, \ldots, P_{N}$.
$Q$ lines follow. Each of these lines contains a single integer $X$ describing a query.

------  Output ------
For each query, print a single line containing one integer — the maximum number of warriors you can kill.

------  Constraints  ------
$1 ≤ T ≤ 10$
$1 ≤ N, Q ≤ 10^{5}$
$1 ≤ P_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ X ≤ 10^{9}$

----- Sample Input 1 ------ 
1
3 4
1 2 1
10
2
3
1
----- Sample Output 1 ------ 
3
2
3
0

Source: codechef | Difficulty: VERY_HARD
Tags: Greedy algorithms

Sorting

Mathematics

Complete search


Solutions:
import math
import bisect
T = int(input())
while T > 0:
	T -= 1
	(N, Q) = map(int, input().split(' '))
	B = [] * Q
	A = list(map(int, input().split(' ')))
	for i in range(0, Q):
		B.append(int(input()))
	A = sorted(A)
	c = 0
	V = []
	m = A[0] + 1
	V.append(m)
	r = 2
	for i in range(1, N):
		if r > A[i]:
			r = 2 * (r - A[i])
			V.append(m)
		else:
			c = math.floor((A[i] - r) / 2 ** i) + 1
			m += c
			V.append(m)
			r = 2 * (r + 2 ** i * c - A[i])
	for q in B:
		print(bisect.bisect_right(V, q))


import math
import bisect
T = int(input())
for t in range(0, T):
	line = input().split()
	n = int(line[0])
	q = int(line[1])
	warriors = input().split()
	warriors = list(map(int, warriors))
	warriors.sort()
	queries = []
	for i in range(0, q):
		queries.insert(i, int(input()))
	minW = []
	Min = warriors[0] + 1
	minW.append(Min)
	rem = 2
	for i in range(1, n):
		if rem > warriors[i]:
			rem = 2 * (rem - warriors[i])
			minW.append(Min)
		else:
			c = math.floor((warriors[i] - rem) / 2 ** i) + 1
			Min += c
			minW.append(Min)
			rem = 2 * (rem + 2 ** i * c - warriors[i])
	for q in queries:
		print(bisect.bisect_right(minW, q))


from bisect import bisect_left, bisect_right
life_limit = 2 * 10 ** 9
T = int(input())
for test in range(T):
	(N, Q) = [int(v) for v in input().split()]
	P = [int(v) for v in input().split()]
	P.sort()
	data = []
	killed = 1
	X = P[0] + 1
	life = 2
	power = 2
	while True:
		while killed < N and life > P[killed] and (life <= life_limit):
			life = 2 * (life - P[killed])
			killed += 1
			power *= 2
		if life > life_limit or killed == N:
			data.append((X, N))
			break
		data.append((X, killed))
		needed = (P[killed] - life) // power + 1
		X += needed
		life = 2 * (life + needed * power - P[killed])
		killed += 1
		power *= 2
	for query in range(Q):
		X = int(input())
		pos = bisect_right(data, (X + 1, 0)) - 1
		if pos == -1:
			print(0)
		else:
			print(data[pos][1])


import math
import bisect
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split(' '))
	p = [int(y) for y in input().split()]
	p.sort()
	z1 = p[0]
	z2 = z1 + 1
	reminder = 2
	min_power = [z2]
	for i1 in range(1, n):
		z1 = p[i1]
		if reminder <= z1:
			diff = z1 - reminder
			inc = math.floor(diff / 2 ** i1)
			inc = inc + 1
			reminder = 2 ** i1 * inc + reminder
			z2 = z2 + inc
		min_power.append(z2)
		reminder = 2 * (reminder - z1)
	for i2 in range(q):
		x = int(input())
		ans = bisect.bisect_right(min_power, x)
		print(ans)


from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n
		self.lista = [[_] for _ in range(n)]

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]
		self.lista[a] += self.lista[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def prime_factors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def all_factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def fibonacci_modP(n, MOD):
	if n < 2:
		return 1
	return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n, p):
	if p <= n:
		return 0
	res = p - 1
	for i in range(n + 1, p):
		res = res * cached_fn(InverseEuler, i, p) % p
	return res

def binary(n, digits=20):
	b = bin(n)[2:]
	b = '0' * (digits - len(b)) + b
	return b

def is_prime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def generate_primes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	return prime
factorial_modP = []

def warm_up_fac(MOD):
	global factorial_modP, fac_warm_up
	if fac_warm_up:
		return
	factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
	for i in range(2, fac_warm_up_size):
		factorial_modP[i] = factorial_modP[i - 1] * i % MOD
	fac_warm_up = True

def InverseEuler(n, MOD):
	return pow(n, MOD - 2, MOD)

def nCr(n, r, MOD):
	global fac_warm_up, factorial_modP
	if not fac_warm_up:
		warm_up_fac(MOD)
		fac_warm_up = True
	return factorial_modP[n] * (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD) % MOD) % MOD

def test_print(*args):
	if testingMode:
		print(args)

def display_list(list1, sep=' '):
	stdout.write(sep.join(map(str, list1)) + '\n')

def display_2D_list(li):
	for i in li:
		print(i)

def prefix_sum(li):
	sm = 0
	res = []
	for i in li:
		sm += i
		res.append(sm)
	return res

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result

def ncr(n, r):
	return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))

def binary_search(i, li):
	fn = lambda x: li[x] - x // i
	x = -1
	b = len(li)
	while b >= 1:
		while b + x < len(li) and fn(b + x) > 0:
			x += b
		b = b // 2
	return x
TestCases = True
fac_warm_up_size = 10 ** 5 + 100
optimise_for_recursion = False

def main():
	(n, q) = get_tuple()
	li = get_list()
	li.sort()
	dp = [[li[0] + 1, 2]]
	for (i, ele) in enumerate(li):
		if i == 0:
			continue
		sp = dp[-1][1]
		sp_global = dp[-1][0]
		if sp <= ele:
			x = (ele - sp) // 2 ** i + 1
			sp_global += x
			sp += x * 2 ** i
		dp.append([sp_global, 2 * (sp - ele)])
	for _ in range(q):
		query = get_int()
		index = bisect_left(dp, [query + 1, 0])
		print(index)
if TestCases:
	for i in range(get_int()):
		main()
else:
	main() if not optimise_for_recursion else threading.Thread(target=main).start()