A15518. The Humanoid
编程题
普及/提高-
知识点
题目描述
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:
1. to absorb an astronaut with power strictly less humanoid power;
2. to use green serum, if there is still one left;
3. 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.
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:
1. to absorb an astronaut with power strictly less humanoid power;
2. to use green serum, if there is still one left;
3. 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.
输入格式
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$ .
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$ .
输出格式
For each test case, in a separate line, print the maximum number of astronauts that a humanoid can absorb.
输入输出样例
输入 #1
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
输出 #1
4 3 3 3 0 4 4 3
说明/提示
In the first case, you can proceed as follows:
1. use green serum. $h = 1 \cdot 2 = 2$
2. absorb the cosmonaut $2$ . $h = 2 + \lfloor \frac{1}{2} \rfloor = 2$
3. use green serum. $h = 2 \cdot 2 = 4$
4. absorb the spaceman $1$ . $h = 4 + \lfloor \frac{2}{2} \rfloor = 5$
5. use blue serum. $h = 5 \cdot 3 = 15$
6. absorb the spaceman $3$ . $h = 15 + \lfloor \frac{8}{2} \rfloor = 19$
7. absorb the cosmonaut $4$ . $h = 19 + \lfloor \frac{9}{2} \rfloor = 23$
1. use green serum. $h = 1 \cdot 2 = 2$
2. absorb the cosmonaut $2$ . $h = 2 + \lfloor \frac{1}{2} \rfloor = 2$
3. use green serum. $h = 2 \cdot 2 = 4$
4. absorb the spaceman $1$ . $h = 4 + \lfloor \frac{2}{2} \rfloor = 5$
5. use blue serum. $h = 5 \cdot 3 = 15$
6. absorb the spaceman $3$ . $h = 15 + \lfloor \frac{8}{2} \rfloor = 19$
7. absorb the cosmonaut $4$ . $h = 19 + \lfloor \frac{9}{2} \rfloor = 23$