Luyện tập

Xem PDF
Thời gian:
Python 3 5.0s
Scratch 10.0s
Tác giả:
corona
Dạng bài
Điểm: 300 (p) Thời gian: 1.1s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Để hỗ trợ các bạn học sinh chuẩn bị tốt cho kỳ thi HSG cấp Thành phố sắp đến, thầy giáo bồi dưỡng chuẩn bị \(n\) bài tập \((1 \leq n \leq 10^5)\). Các bài được đánh số từ \(1\) đến \(n\). Mỗi bài tập nhằm rèn luyện một số kỹ năng cho thí sinh, ví dụ như kỹ thuật lập trình, giải thuật, cấu trúc dữ liệu…

Nhằm định hướng cho quá trình tự luyện tập được hiệu quả, mỗi bài tập có một yêu cầu tối thiểu về trình độ kỹ năng. Để giải được bài thứ \(i\), bạn cần có trình độ kỹ năng tối thiểu là \(a_i\). Điều này có nghĩa là học sinh có thể giải được bài thứ \(i\) khi và chỉ khi có trình độ kỹ năng bằng hoặc lớn hơn \(a_i\). Nếu giải được bài thứ \(i\) trình độ kỹ năng của học sinh sẽ tăng thêm một lượng là \(b_i\) \((1 \leq a_i, b_i \leq 10^9)\). Giả sử ban đầu, trình độ kỹ năng của bạn trước khi làm bài tập là \(c\) \((0 \leq c \leq 10^9)\). Các bài tập có thể được làm theo trình tự bất kỳ tùy chọn.

Ví dụ, với trình độ kỹ năng ban đầu \(c= 1, n= 4\) và các giá trị \(a_i, b_i\) tương ứng là \((1, 10), (21, 5), (1, 10), (100, 100)\), bạn sẽ giải bài \(1\), sau đó làm bài \(3\) và cuối cùng làm bài \(2\). Như vậy bạn sẽ làm được tất cả là \(3\) bài.

Yêu cầu: Cho các số nguyên \(n, c\) và các cặp giá trị \((a_i, b_i)\), \(1 \leq i \leq n\). Hãy xác định số lượng bài tối đa có thể được giải.

Input

  • Dòng đầu tiên chứa 2 số nguyên \(n\) và \(c\).

  • Dòng thứ \(i\) trong \(n\) dòng tiếp theo \((1 \leq i \leq n)\) chứa \(2\) số nguyên \(a_i\) và \(b_i\). Các số trên cùng một dòng được ghi cách nhau bởi \(1\) khoảng trắng.

Output

  • Là một số nguyên xác định số lượng bài tối đa có thể được giải.

Example

Test 1

Input 
4 1
1 10
21 5
1 10
100 100
Output 
3

Bình luận


  • 4
    jumptozero    11:35 a.m. 26 Tháng 6, 2020
    • Mình xin chia sẻ lời giải bài này như sau:
    • Đầu tiên ta sort lại các cặp \((a[i],b[i])\) theo thứ tự tăng dần của \(a[i]\) (Nếu \(a[i]=a[j]\) thì ta tiếp tục so sánh \(b[i]\) và \(b[j]\) theo thứ tự tăng dần).
    • Việc còn lại đơn giản: Đó là duyệt một for, kiểm tra với điều kiện bài toán và tăng biến đêm
    • Dưới đây là code của mình, các bạn có thể tham khảo:
    #include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define manx (ll)(1e5+5)
vector<pair<ll,ll> > v;
ll n,i,res,dem,c,first,second;
int main(){
    cin>>n>>c;
    for(i=0;i<n;i++){
        cin>>first>>second;
        v.push_back({first,second});
    }
    sort(v.begin(),v.end());
    for(i=0;i<n;i++){
        if(c>=v[i].first){
            dem++;
            c+=v[i].second;
        }
        else break;
    }
    cout<<dem;
    return 0;
}
    1 phản hồi