Hero World
View as PDFHumanity is in danger because of monsters coming from space. In this precarious situation, a superhero has appeared to rescue humanity from ~n~ monsters.
Initially, the superhero has a power level of ~x~. At step ~i~, the superhero can:
Choose an undefeated monster whose health level does not exceed the superhero's power level.
If such a monster can be chosen, it will be defeated, and the superhero's power level will be multiplied by ~i + 1~; otherwise, the superhero's power level remains the same.
The health level of all undefeated monsters is multiplied by ~i~, regardless of whether the superhero has just defeated a monster.
Calculate the maximum amount of monsters the hero can defeat.
Input
Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 100~). The description of each test case is as follows.
The first line contains two positive integers ~n~ and ~x~ (~1 \le n \le 5000~, ~1 \le x \le 10^{12}~) — the number of monsters and the initial power level of the superhero.
The second line contains ~n~ positive integers ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^{12}~) — the initial health levels of the monsters.
The sum of ~n~ across all test cases is guaranteed not to exceed ~5000~.
Output
For each test case, output a single integer — the maximum number of monsters the superhero can defeat.
Scoring
| Subtask | Score | Constraints |
|---|---|---|
| 1 | ~250~ | ~1 \le x, a_i \le 100~; sum of ~n~ does not exceed ~100~ |
| 2 | ~250~ | No additional constraints |
| Total | ~500~ |
Sample Input 1
2
5 3
1 1 1 1 50
3 2
7 1 1
Sample Output 1
4
2
Notes
The following explains the first test case, with ~-~ representing monsters that have been defeated.
The hero chooses the first monster. After the superhero defeats the first monster, the remaining monsters have health levels of ~[-, 1, 1, 1, 50]~. The superhero's power level is ~6~.
The hero chooses the second monster. After the superhero defeats the second monster, the remaining monsters have health levels of ~[-, -, 2, 2, 100]~. The superhero's power level is ~18~.
The hero chooses the third monster. After the superhero defeats the third monster, the remaining monsters have health levels of ~[-, -, -, 6, 300]~. The superhero's power level is ~72~.
The hero chooses the fourth monster. After the superhero defeats the fourth monster, the remaining monsters have health levels of ~[-, -, -, -, 1200]~. The superhero's power level is ~360~.
No more monsters can be defeated.
Comments
bài làm của bạn rất hay
This comment is hidden due to too much negative feedback. Show it anyway.
Ai lại đi xin downvote, ngược đời -_-'
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
lần sau để code trong phần spoil nha bạn