USACO 2021 - Open - Bronze - Acowdemia I

View as PDF

Submit solution

Points: 0.05 (partial)
Time limit: 0.5s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=1131
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cô bò Bessie đã tham gia khóa học đào tạo Tiến sĩ ngành Khoa học máy tính với niềm đam mê Tin học và ước mơ trở thành tiến sĩ. Trong thời gian nghiên cứu hàn lâm, Bessie đã xuất bản ~N~ bài nghiên cứu ~(1 \le N \le 10^5)~ và bài nghiên cứu thứ ~i~ đã được trích dẫn ~c_i~ ~(0 \le c_i \le 10^5)~ lần từ những bài nghiên cứu khác trong giới nghiên cứu.

Bessie biết rằng sự thành công của một giảng viên được tính bằng chỉ số ~h~ của họ. Chỉ số ~h~ được định nghĩa là số ~h~ lớn nhất sao cho giảng viên đó có ít nhất ~h~ bài nghiên cứu, mỗi bài có ít nhất ~h~ lần trích dẫn. Ví dụ, một giảng viên có ~4~ bài nghiên cứu và lượng trích dẫn là ~(1, 100, 2, 3)~ có chỉ số ~h~ là ~2~, còn nếu lượng trích dẫn là ~(1, 100, 3, 3)~ thì chỉ số ~h~ của người đó là ~3~.

Để tăng chỉ số ~h~ của cô ấy, Bessie dự định sẽ viết một bài báo trích dẫn một số bài nghiên cứu của cô. Tuy nhiên, bởi vì số lượng trang có hạn, Bessie chỉ có thể trích dẫn tối đa ~L~ ~(0 \le L \le 10^5)~ bài nghiên cứu trong bài báo này. Đương nhiên, bài báo này không thể trích dẫn một bài nghiên cứu nhiều lần.

Hãy giúp Bessie xác định chỉ số ~h~ lớn nhất mà cô ấy có thể đạt được sau khi viết bài báo này.

Input

Dòng đầu tiên chứa ~2~ số nguyên ~N~ và ~L~.

Dòng thứ hai chứa ~N~ số nguyên ~c_1, c_2, \ldots, c_N~ cách nhau bởi một dấu cách.

Output

In ra chỉ số ~h~ cao nhất Bessie có thể đạt được.

Sample Input 1

4 0
1 100 2 3

Sample Output 1

2

Giải thích: Trong ví dụ này, Bessie không thể trích dẫn bài nghiên cứu nào. Như đã nói ở trên, chỉ số ~h~ của ~(1, 100, 2, 3)~ là 2.

Sample Input 2

4 1
1 100 2 3

Sample Output 1

3

Giải thích: Trong ví dụ này, nếu Bessie trích dẫn bài nghiên cứu thứ ba thì lượng trích dẫn sẽ trở thành ~(1, 100, 3, 3)~ và có chỉ số ~h~ là 3.

Ràng buộc

  • Các test 1-7 thỏa mãn ~N \le 100~.
  • Các test 8-10 thỏa mãn ~N \le 1000~.
  • Các test 11-17 thỏa mãn ~N \le 10^5~.

Comments

Please read the guidelines before commenting.



  • 1
    k65vnu  commented on June 17, 2022, 8:24 a.m. edited

    Bạn ra đề có thể giải thích tại sao testcase 8 lại ra kết quả là 1000 thay vì 999?

    Test cho 1000 bài đăng, mỗi bài có số lượt trích dẫn là 999. số trích dẫn tối đa L = 999. Như vậy nếu update thêm 1 trích dẫn cho 999 bài nghiên cứu thì chỉ số h vẫn phải là 999 chứ (có 999 bài có lượng trích dẫn là 1000). tại sao lại +1 thành 1000? (trong đáp án thì test 8 có outPut là 1000.


    • 1
      TotallySomeone  commented on July 2, 2022, 3:04 p.m.

      ơ kìa ông, cái này tôi giải thích còn được, cần gì ông ra đề giải thích :)) test có 999 số 999 và 1 số 1000 nữa mà, sau khi sửa ta có THÊM 999 bài trích dẫn 1000 nữa nên tổng cộng là 999 + 1 có sẵn = 1000, tất cả đều = 1000, vậy nên đáp án là 1000


  • 1
    buiminhkien2005  commented on Oct. 21, 2021, 1:00 p.m.

    Cho mình hỏi lỗi "Unexpected EOF in the participant's output" là lỗi gì vậy ạ :<


    • 1
      leduykhongngu  commented on Oct. 21, 2021, 1:09 p.m.

      Bạn in ra không đủ dữ liệu đề bài yêu cầu.


  • 1
    mhieu0601  commented on Aug. 2, 2021, 8:41 a.m. edit 2

    Trong 2 VD mẫu mình không hiểu sao nó có 1 bài trích dẫn có 1 lần mà sao không cần tính đến vậy. Mình cx không hiểu rõ đề bài viết gì luôn.


    • 10
      darkkcyan  commented on Aug. 3, 2021, 4:41 a.m.

      Đề bài nói rằng cần phải có ~h~ bài có ít nhất ~h~ lần trích dẫn. Nói cách khác, mỗi bài viết được chọn phải có số lần trích dẫn không ít hơn số bài viết được chọn.

      Ở ví dụ 1 thì ~h = 2~, vì ta có thể chọn ra 2 bài có ít nhất số lần trích dẫn là 2, là 1 trong các cặp số sau:

      • ~(100, 2)~
      • ~(2, 3)~
      • ~(100, 3)~

      Ở ví dụ 2, nếu ta thực hiện trích dẫn thêm bài viết thứ 3 để cho nó lên thành 3 lần trích dẫn, vậy mảng ~c~ sẽ là ~(1, 100, 3, 3)~, và như vậy chọn ~h=3~ bài cuối vì chúng có ít nhất 3 lần trích dẫn.


      • 0
        mhieu0601  commented on Sept. 1, 2021, 6:43 a.m.

        thank bạn trước lâu rồi mình vào làm mà hiểu nhầm đề nên lúc đó chưa làm được câu này giờ được bạn chỉ lại mình mới làm được !


      • -8
        codernhi  commented on Aug. 10, 2021, 1:40 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


        • 14
          darkkcyan  commented on Aug. 11, 2021, 8:57 a.m. edited

          Haiz

          Ví dụ một đã cho ta mảng ~c~ gồm các phần tử ~1, 100, 2, 3~. Tức bài viết thứ nhất đã có 1 lần trích dẫn, bài viết thứ 2 đã có 100 lần trích dẫn. Bài viết thứ 3 có 2 lần, và bài viết thứ 4 có 3 lần trích dẫn.

          Ở ví dụ 1, ~L = 0~, tức ta không được phép trích 1 bài viết nào nữa, do đó mảng ~c~ ở đây không có gì thay đổi.

          Đề bài nói rằng cần phải có ~h~ bài có ít nhất ~h~ lần trích dẫn. Với ~h~ bằng 2, ta có các cách lấy 2 bài sau:

          1. ~(1, 100)~
          2. ~(1, 2)~
          3. ~(1, 3)~
          4. ~(100, 2)~
          5. ~(100, 3)~
          6. ~(2, 3)~

          Cách lấy bài thứ 1, 2 hoặc 3 đều không thỏa mãn, bởi vì số lượng trích dẫn của bài viết đầu tiên là ~1~, nhỏ hơn ~h = 2~. 3 cách cuối thỏa mãn, bởi vì cả 2 số đều lớn hơn hoặc bằng ~h = 2~. Và rõ ràng ta có ít nhất 1 cách lấy 2 bài viết có số lần trích dẫn không nhỏ hơn 2 (mà ở đây có hẳn 3 cách), nên ta ta nói ~h = 2~ là đáp án.

          Tuy là tất cả các cách lấy với số ~1~ đều không thỏa mãn, nhưng ta không quan tâm những cách lấy không thỏa mãn. Nếu có ít nhất 1 cách lấy thỏa mãn, thì chỉ số ~h~ đang xét là chỉ số thỏa mãn.

          ~h = 1~ không phải là đáp án của bài toán, bởi vì tuy là cả 4 cách lấy bài viết thỏa mãn gồm có 1 bài và các bài đều có số lượng trích dẫn không quá 1, ta cần in ra ~h~ có giá trị lớn nhất.

          ~h = 3~ không phải là đáp án cho bài toán. Nếu liệt kê tất cả các cách lấy bài viết gồm 3 bài viết ra, kiểu cũng lấy phải bài viết gồm 1 lần trích dẫn, hoặc bài viết gồm 2 lần trích dẫn, hoặc cả 2, mà nếu ~h = 3~, ta cần tất cả các bài viết mà ta lấy không nhỏ hơn ~h = 3~ lần trích dẫn. Vì không có cách lấy nào thỏa mãn ~h = 3~, nên ~h = 3~ không phải là đáp án.


        • 15
          Mike4235  commented on Aug. 11, 2021, 8:48 a.m. edited

          Một input có 2 dòng, ví dụ 1 có input là:

          4 0
          1 100 2 3
          

          chứ không phải

          1 100 2 3
          

          Số 1 ở đây nghĩa là bài nghiên cứu thứ nhất của Bessie ban đầu có 1 lần trích dẫn. Mục input đã chú thích rõ ràng.