codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$