Các lá bài Blackjack

View as PDF
Submit solution
Points: 0.56 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem source:
Sưu tầm
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Blackjack là trò chơi đánh bài khá phổ biến, mục tiêu là có được những lá bài mà tổng của nó là lớn nhất nhưng không vượt quá ~21~. Lấy ý tưởng từ trò chơi này các bạn khaihanhdk, huytion156, thanhdat01234 đã sáng tạo ra một phiên bản mới của trò chơi cho riêng mình.

Trong phiên bản trò chơi mới này các bạn đã viết lên mỗi lá bài một số nguyên dương. Người tham gia trò chơi được cung cấp một tập gồm ~N~ lá bài và một số nguyên dương ~M~. Nhiệm vụ của người chơi là phải chọn ra ~3~ lá bài từ tập lá bài đã cho sao cho tổng các số trên ~3~ lá bài đã chọn là lớn nhất và không vượt quá ~M~.

Input

  • Dòng đầu ghi số nguyên dương ~N~, ~M~ ~(N \le 10000~, ~M \le 500000)~.
  • ~N~ dòng sau ghi ~N~ số nguyên dương đôi một khác nhau là các số được ghi trên ~N~ lá bài ~(1 \leq a_{i} \leq 10000)~.

Output

Ghi trên một dòng duy nhất là kết quả bài toán. Test luôn đảm bảo có kết quả.

Sample Input

6 20 7 9 6 2 1 5

Sample Output

20

Note

Chọn các lá bài mang số ~9~, ~6~, ~5~ ta có ~9 + 6 + 5 = 20 \le M~

Comments

Please read the guidelines before commenting.


  • 0
    kuriyama_san  commented on Sept. 7, 2024, 2:09 a.m.

    Bài này các bạn sắp xếp mảng A, rồi với mỗi A[k], dùng two pointers để tìm cặp A[i], A[j] có tổng = m - A[k]

    • Với TH A[i] + A[j] = m - A[k] thì in ra m luôn
    • Với TH A[i] + A[j] < m - A[k] thì cập nhật kỉ lục của A[i] + A[j] + A[k], tăng i
    • Với TH A[i] + A[j] > m - A[k] thì giảm j

    Đồng thời phải liên tục kiểm tra cho i, j, k khác nhau đôi một ĐPT O(n^2)


  • 0
    Spectrum3563  commented on Aug. 9, 2024, 10:57 a.m.

    Nếu ~n <= 10^4~ thì ~O(n^2 log(n))~ có chạy được không nhỉ


  • 4
    giabaotq07  commented on Feb. 5, 2024, 2:51 p.m.

    6 20 10 7 6 8 5 1 test chưa kĩ nha ad ơi xem mấy code top1 dùng test này toàn sai ra 19 nhưng đúng ra là 20


  • -11
    CodeGod  commented on Oct. 25, 2023, 3:00 a.m.

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


  • -16
    CodeGod  commented on Oct. 18, 2023, 1:01 a.m. ← edit 4

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


  • -9
    An250506  commented on June 28, 2023, 8:41 a.m.

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


    • 1
      OrzSeaPosjtive  commented on June 28, 2023, 2:43 p.m.

      bro ~n \leq 10^4~


      • -10
        An250506  commented on June 29, 2023, 3:10 a.m.

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