The Humanoid (Codeforces 1759E)
Tags: DP, sortings

There are $$$n$$$ astronauts working on some space station. An astronaut with the number $$$i$$$ ($$$1 \le i \le n$$$) has power $$$a_i$$$.An evil humanoid has made his way to this space station. The power of this humanoid is equal to $$$h$$$. Also, the humanoid took with him two green serums and one blue serum.In one second , a humanoid can do any of three actions:  to absorb an astronaut with power strictly less humanoid power;  to use green serum, if there is still one left;  to use blue serum, if there is still one left. When an astronaut with power $$$a_i$$$ is absorbed, this astronaut disappears, and power of the humanoid increases by $$$\lfloor \frac{a_i}{2} \rfloor$$$, that is, an integer part of $$$\frac{a_i}{2}$$$. For example, if a humanoid absorbs an astronaut with power $$$4$$$, its power increases by $$$2$$$, and if a humanoid absorbs an astronaut with power $$$7$$$, its power increases by $$$3$$$.After using the green serum, this serum disappears, and the power of the humanoid doubles, so it increases by $$$2$$$ times.After using the blue serum, this serum disappears, and the power of the humanoid triples, so it increases by $$$3$$$ times.The humanoid is wondering what the maximum number of astronauts he will be able to absorb if he acts optimally.

Input: The first line of each test contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of test cases.The first line of each test case contains integers $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — number of astronauts and $$$h$$$ ($$$1 \le h \le 10^6$$$) — the initial power of the humanoid.The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^8$$$) — powers of astronauts.It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, in a separate line, print the maximum number of astronauts that a humanoid can absorb.

Note: In the first case, you can proceed as follows:   use green serum. $$$h = 1 \cdot 2 = 2$$$  absorb the cosmonaut $$$2$$$. $$$h = 2 + \lfloor \frac{1}{2} \rfloor = 2$$$  use green serum. $$$h = 2 \cdot 2 = 4$$$  absorb the spaceman $$$1$$$. $$$h = 4 + \lfloor \frac{2}{2} \rfloor = 5$$$  use blue serum. $$$h = 5 \cdot 3 = 15$$$  absorb the spaceman $$$3$$$. $$$h = 15 + \lfloor \frac{8}{2} \rfloor = 19$$$  absorb the cosmonaut $$$4$$$. $$$h = 19 + \lfloor \frac{9}{2} \rfloor = 23$$$ 

Sample Inputs:
8
4 1
2 1 8 9
3 3
6 2 60
4 5
5 1 100 5
3 2
38 6 3
1 1
12
4 6
12 12 36 100
4 1
2 1 1 15
3 5
15 1 13

Sample Outputs:
4
3
3
3
0
4
4
3

Solution (Python):
def solve(h, i=0, g=2, b=1):
    while c[i] < h:
        h += c[i] // 2
        i += 1
        if i == n:
            return i
    (a1, a2) = (0, 0)
    if g:
        a1 = solve(h * 2, i, g - 1, b)
    if b:
        a2 = solve(h * 3, i, g, b - 1)
    return max(a1, a2, i)
for _ in range(int(input())):
    (n, h) = map(int, input().split())
    c = list(map(int, input().split()))
    c.sort()
    print(solve(h))

Solution (Python):
def f(h, i=0, k1=2, k2=1):
    while m[i] < h:
        h += m[i] // 2
        i += 1
        if i == len(m):
            return i
    (a1, a2) = (0, 0)
    if k1 > 0:
        a1 = f(h * 2, i, k1 - 1, k2)
    if k2 > 0:
        a2 = f(h * 3, i, k1, k2 - 1)
    return max(a1, a2, i)
for t in range(int(input())):
    (n, h) = map(int, input().split())
    m = sorted(list(map(int, input().split())))
    print(f(h))

Solution (Python):
import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 998244353
INF = float('inf')

def inp():
    return int(sys.stdin.readline())

def inpl():
    return list(map(int, sys.stdin.readline().split()))

def inpl_1():
    return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

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

def inpl_1m():
    return map(lambda x: int(x) - 1, sys.stdin.readline().split())

def inps():
    tmp = sys.stdin.readline()
    return list(tmp[:len(tmp) - 1])

def inpsl(x):
    tmp = sys.stdin.readline()
    return list(tmp[:x])

def err(x):
    print(x)
    exit()
sys.setrecursionlimit(10 ** 8)
for _ in range(inp()):
    (n, h) = inplm()
    a = inpl()
    a.sort()

    def dfs(i, g, b, h):
        while i < n:
            ast = a[i]
            if h > ast:
                h += ast // 2
                i += 1
                continue
            else:
                break
        if i == n:
            return n
        mx = i
        if g:
            mx = max(mx, dfs(i, g - 1, b, h * 2))
        if b:
            mx = max(mx, dfs(i, g, b - 1, h * 3))
        return mx
    print(dfs(0, 2, 1, h))