Chọn Đội tuyển HSGQG Quảng Trị 2024 - EXCHANGE
Xem dạng PDF
An rất thích sưu tập tem và An đã sưu tập được nhiều con tem quý. Tại một buổi trưng bày các con tem cổ của những người sưu tập tem trong thành phố, An phát hiện ra một con tem cổ mà An rất thích và đã mất rất nhiều công sức tìm kiếm lâu nay. An muốn mua lại con tem đó nhưng chủ nhân của con tem không bán mà chỉ đồng ý trao đổi bằng những con tem mà An đang có.
Bộ sưu tập của An có ~N~ con tem, đánh số từ ~1~ đến ~N~. Con tem thứ ~i~ có giá trị ~C_i~ với ~i = 1, 2, \ldots, N~. Các con tem có giá trị bằng nhau được xem là cùng một loại. Chủ nhân của con tem mà An muốn đổi yêu cầu An phải đổi bằng một số con tem và tổng giá trị của các con tem đó phải lớn hơn hoặc bằng ~P~.
An rất muốn sở hữu con tem cổ nhưng cũng cân nhắc cách đổi sao cho giữ lại cho mình nhiều loại tem khác nhau nhất và tổng giá trị các con tem đem trao đổi càng nhỏ càng tốt.
Yêu cầu: Bạn hãy tìm cách trao đổi giúp An có được con tem như mong muốn.
Input
Dữ liệu vào từ tệp văn bản EXCHANGE.INP gồm:
Dòng đầu tiên chứa hai số nguyên ~N~ và ~P~ (~1 \leq N, P \leq 6 \times 10^4~);
Dòng tiếp theo chứa ~N~ số chuyên không âm ~C_1, C_2, \ldots, C_N~ và ~P \leq C_1 + C_2 + \cdots + C_N \leq 2 \times P~.
Các số trên cùng một dòng cách nhau bằng dấu cách.
Output
Kết quả ghi ra tệp văn bản EXCHANGE.OUT gồm:
Dòng thứ nhất ghi hai số nguyên dương ~D~ và ~S~ (~S \geq P~) với ~D~ là số lượng loại tem khác nhau còn lại sau khi trao đổi và ~S~ là tổng giá trị các con tem đem ra trao đổi;
Dòng thứ hai ghi ~K~ số nguyên ~C_{i_1}, C_{i_2}, \ldots, C_{i_K}~ là giá trị các con tem đem ra trao đổi theo thứ tự không giảm.
Các số trên một dòng ghi cách nhau bằng dấu cách.
Nếu chỉ đúng giá trị ~D~ thì được ~20\%~ số điểm của test đó.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20\%~ | ~n \leq 20~ |
| 2 | ~25\%~ | ~C_i \neq C_j~ với mỗi cặp ~(i, j)~ (~1 \leq i \text{ < } j \leq N~) |
| 3 | ~20\%~ | ~N, P \leq 5 \times 10^3~ |
| 4 | ~35\%~ | Không có ràng buộc gì thêm |
Sample Input 1
8 21
5 5 5 0 7 4 7 9
Sample Output 1
4 21
4 5 5 7
Sample Input 2
7 100
90 2 2 3 3 6 6
Sample Output 2
3 101
2 3 6 90
Notes
Ở test ví dụ ~1~, ta có hai cách để đổi, ngoài test ví dụ ta cũng có thể dùng các con tem ~(4, 5, 5, 7)~ để đổi
Ở test ví dụ ~2~, để còn lại 3 loại team ~(2, 3, 6)~, cần phải đổi các con tem với tổng là 101
Bình luận