Hero World
Xem dạng PDFNhân loại đang gặp nguy hiểm vì những con quái vật đến từ không gian. Trong tình huống khó khăn này, một siêu anh hùng đã xuất hiện để giải cứu nhân loại khỏi ~n~ con quái vật.
Ban đầu, siêu anh hùng có chỉ số sức mạnh là ~x~. Ở bước thứ ~i~, siêu anh hùng có thể:
Chọn một con quái vật chưa bị tiêu diệt sao cho chỉ số máu của quái vật không vượt quá chỉ số sức mạnh của anh hùng.
Nếu anh hùng chọn được một con quái vật như vậy, con quái vật này sẽ bị tiêu diệt và chỉ số sức mạnh của anh hùng được tăng lên ~i + 1~ lần; ngược lại, chỉ số sức mạnh của anh hùng giữ nguyên.
Chỉ số máu của các con quái vật chưa bị tiêu diệt tăng lên ~i~ lần, bất kể anh hùng có vừa tiêu diệt được con quái nào hay không.
Hãy tính xem siêu anh hùng có thể tiêu diệt tối đa bao nhiêu con quái vật.
Input
Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \leq t \leq 100~). Mô tả của mỗi test case như sau.
Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~x~ (~1 \le n \le 5000~, ~1 \le x \le 10^{12}~) — số lượng các con quái vật và chỉ số sức mạnh ban đầu của siêu anh hùng.
Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^{12}~) — chỉ số máu ban đầu của các con quái vật.
Đảm bảo rằng tổng của ~n~ qua tất cả các test case không vượt quá ~5000~.
Output
Với mỗi test case, in ra một số nguyên duy nhất — số con quái vật tối đa anh hùng có thể tiêu diệt.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~250~ | ~1 \le x, a_i \le 100~; tổng của ~n~ không vượt quá ~100~ |
| 2 | ~250~ | Không có giới hạn gì thêm |
| Tổng | ~500~ |
Sample Input 1
2
5 3
1 1 1 1 50
3 2
7 1 1
Sample Output 1
4
2
Notes
Dưới đây là giải thích cho test case đầu tiên, với ký hiệu ~-~ đại diện cho quái vật đã bị tiêu diệt.
Anh hùng chọn quái vật đầu tiên. Sau khi anh hùng tiêu diệt quái vật đầu tiên, các quái vật còn lại có chỉ số máu là ~[-, 1, 1, 1, 50]~. Chỉ số sức mạnh của anh hùng là ~6~.
Anh hùng chọn quái vật thứ hai. Sau khi anh hùng tiêu diệt quái vật thứ hai, các quái vật còn lại có chỉ số máu là ~[-, -, 2, 2, 100]~. Chỉ số sức mạnh của anh hùng là ~18~.
Anh hùng chọn quái vật thứ ba. Sau khi anh hùng tiêu diệt quái vật thứ ba, các quái vật còn lại có chỉ số máu là ~[-, -, -, 6, 300]~. Chỉ số sức mạnh của anh hùng là ~72~.
Anh hùng chọn quái vật thứ tư. Sau khi anh hùng tiêu diệt quái vật thứ tư, quái vật còn lại có chỉ số máu là ~[-, -, -, -, 1200]~. Chỉ số sức mạnh của anh hùng là ~360~.
Không còn quái vật nào có thể bị tiêu diệt nữa.
Bình luận
bài làm của bạn rất hay
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Ai lại đi xin downvote, ngược đời -_-'
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
lần sau để code trong phần spoil nha bạn