309917: CF1759E. The Humanoid
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
The Humanoid
题意翻译
## 题目描述 有 $n$ 名宇航员,他们每个人有大小为 $a_i$ 的能量。一个初始具有 $h$ 单位能量的邪恶的人形生物来这里吸收宇航员们的能量。 人型生物可以做以下三个动作: - 吸收一个能量值严格低于当前人型生物的宇航员。 - 将自身的能量值翻倍 ($\times 2$), 这个操作最多能进行两次。 - 将自身的能量值翻三倍 ($\times 3$), 这个操作最多能进行一次。 其中,当一名具有 $a_i$ 能量的宇航员被吸收时,这名宇航员消失,人型生物的能量增加 $\lfloor {a_i\over 2} \rfloor$。 请你帮他算一算,如果他用最佳方案进行操作,他最多能吸收几名宇航员的能量? ## 输入格式 第一行包含一个整数 $t\ (1\leq t \leq 10^4)$, 表示数据组数。 对于每组数据,第一行包含两个整数 $n\ (1\leq n \leq 2\cdot 10^5),h\ (1\leq h \leq 10^6)$, 分别代表宇航员人数和人形生物的初始能量。第二行包含 $n$ 个整数 $a_i\ (1\leq a_i \leq 10^8)$, 表示每名宇航员的能量。 保证 $\sum n\leq 2\cdot 10^5$。 ## 输出格式 对于每组数据,在单独的一行里输出一个整数,表示人形生物可以吸收宇航员的最大数量。题目描述
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.输入输出格式
输入格式
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 $ .
输出格式
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 $Input
题意翻译
## 题目描述 有 $n$ 名宇航员,他们每个人有大小为 $a_i$ 的能量。一个初始具有 $h$ 单位能量的邪恶的人形生物来这里吸收宇航员们的能量。 人型生物可以做以下三个动作: - 吸收一个能量值严格低于当前人型生物的宇航员。 - 将自身的能量值翻倍 ($\times 2$), 这个操作最多能进行两次。 - 将自身的能量值翻三倍 ($\times 3$), 这个操作最多能进行一次。 其中,当一名具有 $a_i$ 能量的宇航员被吸收时,这名宇航员消失,人型生物的能量增加 $\lfloor {a_i\over 2} \rfloor$。 请你帮他算一算,如果他用最佳方案进行操作,他最多能吸收几名宇航员的能量? ## 输入格式 第一行包含一个整数 $t\ (1\leq t \leq 10^4)$, 表示数据组数。 对于每组数据,第一行包含两个整数 $n\ (1\leq n \leq 2\cdot 10^5),h\ (1\leq h \leq 10^6)$, 分别代表宇航员人数和人形生物的初始能量。第二行包含 $n$ 个整数 $a_i\ (1\leq a_i \leq 10^8)$, 表示每名宇航员的能量。 保证 $\sum n\leq 2\cdot 10^5$。 ## 输出格式 对于每组数据,在单独的一行里输出一个整数,表示人形生物可以吸收宇航员的最大数量。Output
题意翻译:
题目描述:
有 $n$ 名宇航员,他们每个人有大小为 $a_i$ 的能量。一个初始具有 $h$ 单位能量的邪恶的人形生物来这里吸收宇航员们的能量。
人型生物可以做以下三个动作:
- 吸收一个能量值严格低于当前人型生物的宇航员。
- 将自身的能量值翻倍 ($\times 2$), 这个操作最多能进行两次。
- 将自身的能量值翻三倍 ($\times 3$), 这个操作最多能进行一次。
其中,当一名具有 $a_i$ 能量的宇航员被吸收时,这名宇航员消失,人型生物的能量增加 $\lfloor {a_i\over 2} \rfloor$。
请你帮他算一算,如果他用最佳方案进行操作,他最多能吸收几名宇航员的能量?
输入格式:
第一行包含一个整数 $t\ (1\leq t \leq 10^4)$, 表示数据组数。
对于每组数据,第一行包含两个整数 $n\ (1\leq n \leq 2\cdot 10^5),h\ (1\leq h \leq 10^6)$, 分别代表宇航员人数和人形生物的初始能量。第二行包含 $n$ 个整数 $a_i\ (1\leq a_i \leq 10^8)$, 表示每名宇航员的能量。
保证 $\sum n\leq 2\cdot 10^5$。
输出格式:
对于每组数据,在单独的一行里输出一个整数,表示人形生物可以吸收宇航员的最大数量。题意翻译: 题目描述: 有 $n$ 名宇航员,他们每个人有大小为 $a_i$ 的能量。一个初始具有 $h$ 单位能量的邪恶的人形生物来这里吸收宇航员们的能量。 人型生物可以做以下三个动作: - 吸收一个能量值严格低于当前人型生物的宇航员。 - 将自身的能量值翻倍 ($\times 2$), 这个操作最多能进行两次。 - 将自身的能量值翻三倍 ($\times 3$), 这个操作最多能进行一次。 其中,当一名具有 $a_i$ 能量的宇航员被吸收时,这名宇航员消失,人型生物的能量增加 $\lfloor {a_i\over 2} \rfloor$。 请你帮他算一算,如果他用最佳方案进行操作,他最多能吸收几名宇航员的能量? 输入格式: 第一行包含一个整数 $t\ (1\leq t \leq 10^4)$, 表示数据组数。 对于每组数据,第一行包含两个整数 $n\ (1\leq n \leq 2\cdot 10^5),h\ (1\leq h \leq 10^6)$, 分别代表宇航员人数和人形生物的初始能量。第二行包含 $n$ 个整数 $a_i\ (1\leq a_i \leq 10^8)$, 表示每名宇航员的能量。 保证 $\sum n\leq 2\cdot 10^5$。 输出格式: 对于每组数据,在单独的一行里输出一个整数,表示人形生物可以吸收宇航员的最大数量。
题目描述:
有 $n$ 名宇航员,他们每个人有大小为 $a_i$ 的能量。一个初始具有 $h$ 单位能量的邪恶的人形生物来这里吸收宇航员们的能量。
人型生物可以做以下三个动作:
- 吸收一个能量值严格低于当前人型生物的宇航员。
- 将自身的能量值翻倍 ($\times 2$), 这个操作最多能进行两次。
- 将自身的能量值翻三倍 ($\times 3$), 这个操作最多能进行一次。
其中,当一名具有 $a_i$ 能量的宇航员被吸收时,这名宇航员消失,人型生物的能量增加 $\lfloor {a_i\over 2} \rfloor$。
请你帮他算一算,如果他用最佳方案进行操作,他最多能吸收几名宇航员的能量?
输入格式:
第一行包含一个整数 $t\ (1\leq t \leq 10^4)$, 表示数据组数。
对于每组数据,第一行包含两个整数 $n\ (1\leq n \leq 2\cdot 10^5),h\ (1\leq h \leq 10^6)$, 分别代表宇航员人数和人形生物的初始能量。第二行包含 $n$ 个整数 $a_i\ (1\leq a_i \leq 10^8)$, 表示每名宇航员的能量。
保证 $\sum n\leq 2\cdot 10^5$。
输出格式:
对于每组数据,在单独的一行里输出一个整数,表示人形生物可以吸收宇航员的最大数量。题意翻译: 题目描述: 有 $n$ 名宇航员,他们每个人有大小为 $a_i$ 的能量。一个初始具有 $h$ 单位能量的邪恶的人形生物来这里吸收宇航员们的能量。 人型生物可以做以下三个动作: - 吸收一个能量值严格低于当前人型生物的宇航员。 - 将自身的能量值翻倍 ($\times 2$), 这个操作最多能进行两次。 - 将自身的能量值翻三倍 ($\times 3$), 这个操作最多能进行一次。 其中,当一名具有 $a_i$ 能量的宇航员被吸收时,这名宇航员消失,人型生物的能量增加 $\lfloor {a_i\over 2} \rfloor$。 请你帮他算一算,如果他用最佳方案进行操作,他最多能吸收几名宇航员的能量? 输入格式: 第一行包含一个整数 $t\ (1\leq t \leq 10^4)$, 表示数据组数。 对于每组数据,第一行包含两个整数 $n\ (1\leq n \leq 2\cdot 10^5),h\ (1\leq h \leq 10^6)$, 分别代表宇航员人数和人形生物的初始能量。第二行包含 $n$ 个整数 $a_i\ (1\leq a_i \leq 10^8)$, 表示每名宇航员的能量。 保证 $\sum n\leq 2\cdot 10^5$。 输出格式: 对于每组数据,在单独的一行里输出一个整数,表示人形生物可以吸收宇航员的最大数量。