1759E.md (2679B)
1 Source: https://codeforces.com/problemset/problem/1759/E 2 3 E. The Humanoid 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There are $n$ astronauts working on some space station. An astronaut with the number $i$ ($1 \le i \le n$) has power $a_i$. 22 23 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. 24 25 In one second , a humanoid can do any of three actions: 26 27 1. to absorb an astronaut with power strictly less humanoid power; 28 2. to use green serum, if there is still one left; 29 3. to use blue serum, if there is still one left. 30 31 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$. 32 33 After using the green serum, this serum disappears, and the power of the humanoid doubles, so it increases by $2$ times. 34 35 After using the blue serum, this serum disappears, and the power of the humanoid triples, so it increases by $3$ times. 36 37 The humanoid is wondering what the maximum number of astronauts he will be able to absorb if he acts optimally. 38 39 Input 40 41 The first line of each test contains an integer $t$ ($1 \le t \le 10^4$) — number of test cases. 42 43 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. 44 45 The second line of each test case contains $n$ integers $a_i$ ($1 \le a_i \le 10^8$) — powers of astronauts. 46 47 It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$. 48 49 Output 50 51 For each test case, in a separate line, print the maximum number of astronauts that a humanoid can absorb. 52 53 Example 54 55 Input 56 57 ``` 58 8 59 60 4 1 61 62 2 1 8 9 63 64 3 3 65 66 6 2 60 67 68 4 5 69 70 5 1 100 5 71 72 3 2 73 74 38 6 3 75 76 1 1 77 78 12 79 80 4 6 81 82 12 12 36 100 83 84 4 1 85 86 2 1 1 15 87 88 3 5 89 90 15 1 13 91 ``` 92 93 Output 94 95 ``` 96 4 97 3 98 3 99 3 100 0 101 4 102 4 103 3 104 ``` 105 106 Note 107 108 In the first case, you can proceed as follows: 109 110 1. use green serum. $h = 1 \cdot 2 = 2$ 111 2. absorb the cosmonaut $2$. $h = 2 + \lfloor \frac{1}{2} \rfloor = 2$ 112 3. use green serum. $h = 2 \cdot 2 = 4$ 113 4. absorb the spaceman $1$. $h = 4 + \lfloor \frac{2}{2} \rfloor = 5$ 114 5. use blue serum. $h = 5 \cdot 3 = 15$ 115 6. absorb the spaceman $3$. $h = 15 + \lfloor \frac{8}{2} \rfloor = 19$ 116 7. absorb the cosmonaut $4$. $h = 19 + \lfloor \frac{9}{2} \rfloor = 23$