Kẻ thù
View as PDFStatement
Nguyễn Chí Hùng - một guitar bass, thu âm, kỹ thuật viên âm thanh và cũng là một siêu anh hùng, đang thực hiện nhiệm vụ bảo vệ thành phố khỏi những tên ác nhân nguy hiểm. Thành phố có rất nhiều ác nhân, nhưng chỉ một số tên là trùm đầu sỏ cần bị hạ gục để giải cứu thành phố. Ban đầu, Hùng có một lượng sức mạnh S.
Để hạ gục một trùm đầu sỏ, sức mạnh của Hùng phải cao hơn hoặc bằng sức mạnh của tên trùm đó. Mỗi lần tiêu diệt một trùm thành công, Hùng sẽ nhận được điểm thưởng, giúp tăng thêm sức mạnh cho lần đối đầu tiếp theo. Tuy nhiên, Hùng cần phải tính toán kỹ vì không phải tên trùm nào cũng có thể hạ gục ngay từ đầu.
Nhiệm vụ của bạn là giúp Hùng tìm số lượng trùm tối đa mà anh ấy có thể tiêu diệt để giải cứu thành phố.
Input, Output và Subtasks
Input: (ENEMY.INP)
- Gồm hai số nguyên n và S tương ứng với số lượng trùm trong thành phố và sức mạnh ban đầu của Hùng.
- n dòng tiếp theo: mỗi dòng chứa F_{i}, G_{i} tương ứng sức mạnh và điểm thưởng của trùm thứ i.
Output: (ENEMY.OUT)
- In ra một số nguyên duy nhất là số lượng trùm tối đa mà Hùng có thể tiêu diệt.
Subtasks
- Subtask chung: 1 \leq F_{i}, G_{i}, S \leq 10^{9};
- Subtask 1 (20%): 1 \leq n \leq 10
- Subtask 2 (30%): 1 \leq n \leq 10^{3}
- Subtask 2 (50%): 1 \leq n \leq 10^{5}
Sample #1
Input (ENEMY.INP)
5 2
6 1
7 3
4 2
10 5
12 4
Output (ENEMY.OUT)
0
Notes
- Hùng bắt đầu với 2 điểm sức mạnh nhưng không đủ để tiêu diệt bất kỳ trùm nào, vì tất cả các trùm đều có sức mạnh lớn hơn.
Sample #2
Input (ENEMY.INP)
5 3
10 7
5 3
14 10
1 2
2 1
Output (ENEMY.OUT)
3
Notes
- Ban đầu, Hùng có 3 điểm sức mạnh.
- Hùng tiêu diệt trùm có 2 điểm sức mạnh và nhận 1 điểm thưởng, tăng sức mạnh lên 4.
- Sau đó, Hùng tiêu diệt trùm có 1 điểm sức mạnh và nhận 2 điểm thưởng, tăng sức mạnh lên 6.
- Tiếp theo, Hùng tiêu diệt trùm có 5 điểm sức mạnh và nhận 3 điểm thưởng, tăng sức mạnh lên 9.
- Hùng không thể tiêu diệt thêm trùm nào có sức mạnh lớn hơn 9. Vì vậy, đáp án là 3.
Comments