VOI 22 Bài 1 - Chọn cặp

Xem dạng PDF

Gửi bài giải

Điểm: 0,50 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 512M
Input: PAIR.INP
Output: PAIR.OUT

Nguồn bài:
Kỳ thi Học sinh giỏi Quốc gia 2022 - Ngày 1
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hưởng ứng phong trào thi đua học tập của trường, cô giáo chủ nhiệm lớp của Nam muốn chọn các cặp đôi bạn giúp đỡ nhau cùng tiến. Lớp của Nam có ~n~ học sinh, được đánh số từ ~1~ đến ~n~, học sinh thứ ~i~ có chỉ số học lực ~a_i~. Để có được sự cân bằng giữa các cặp bạn cùng tiến, cô giáo muốn chọn các cặp bạn có tổng chỉ số học lực đôi một giữa các cặp chênh nhau không quá một giá trị nhỏ ~d~ sao cho mỗi bạn xuất hiện trong không quá một cặp. Cô giáo mong muốn chọn được nhiều cặp như vậy nhất.

Yêu cầu: Cho biết số học sinh của lớp và chỉ số học lực của từng học sinh, hãy tính số cặp bạn cùng tiến nhiều nhất mà có tổng chỉ số học lực đôi một giữa các cặp chênh nhau không quá ~d~.

Dữ liệu

Vào từ file văn bản PAIR.INP:

  • Dòng đầu tiên chứa hai số nguyên không âm ~n, d~ (~n \ge 2~);
  • Dòng thứ hai chứa ~n~ số nguyên dương, số thứ ~i~ là chỉ số học lực ~a_i~ của học sinh thứ ~i~ (~1 \le i \le n~, ~a_i \le 10^9~).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản PAIR.OUT một số nguyên duy nhất là số cặp nhiều nhất tìm được.

Ràng buộc

  • Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn: ~n \le 10~; ~d = 0~;
  • ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn: ~n \le 200~; ~d = 0~;
  • ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn: ~n \le 2000~; ~d = 0~;
  • ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn: ~n \le 200~; ~d = 1~;
  • ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài thỏa mãn: ~n \le 2000~; ~d = 1~.

Ví dụ

Input
7 1
9 1 2 4 5 6 8
Output
3
Giải thích

Một phương án chọn được nhiều nhất cặp các bạn học sinh với tổng học lực đôi một chênh nhau không quá ~1~ là:

$$\begin{array}{rcl} 1 + 8 &=& 9; \\ 2 + 6 &=& 8; \\ 4 + 5 &=& 9. \end{array}$$

Một phương án khác cũng chọn được ~3~ cặp là:

$$\begin{array}{rcl} 1 + 9 &=& 10; \\ 2 + 8 &=& 10; \\ 4 + 6 &=& 10. \end{array}$$


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 5
    tretrauvl  đã bình luận lúc 15, Tháng 1, 2024, 8:37

    Bạn em phatnguyen code ac nhưng lại sai test này:

    Input:
    7 0
    1 4 2 9 9 9 5
    
    Output: 
    2
    

    • 0
      phatnguyen  đã bình luận lúc 15, Tháng 1, 2024, 9:07 chỉnh sửa

      ok cảm ơn bạn, mình đã fix rồi


  • -62
    nhatquang1310  đã bình luận lúc 28, Tháng 9, 2023, 14:24

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -37
    dvquang  đã bình luận lúc 12, Tháng 7, 2023, 3:28

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -34
    taintedsilk  đã bình luận lúc 17, Tháng 3, 2023, 13:08 sửa 8

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -39
    vanhieu  đã bình luận lúc 6, Tháng 12, 2022, 7:19

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -13
    nguot  đã bình luận lúc 15, Tháng 4, 2022, 4:28

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.