Cái túi 2

View as PDF

Submit solution

Points: 0.69 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đã hết mùa khế. Trái khế cuối cùng đã rơi và giờ chỉ còn Khánh với cái cây toàn lá là lá. Khánh nhìn cây khế mà tiếc đứt ruột, nước mắt lã chã rơi. Vàng đâu nữa mà xài đây, ơi hỡi! Ngày nọ, con chim to to đó lại đến. Khế đâu ra mà cho nó ăn nữa bây giờ. Nhưng lạ lùng thay, chim to không đòi ăn khế. Số là vợ chim sai chim đi tìm dưa leo cho cô nàng đắp mặt. Chim to ngồi than với Khánh rằng nó đã đi một vòng Trái Đất rồi mà không tìm được trái dưa leo đủ to để đắp vừa khuôn mặt vợ ~y~. Tưởng gì, dưa leo thì Khánh chẳng thiếu vì Khánh ngày nào cũng đắp mặt mà:) Khánh lôi trong tủ lạnh ra một trái dưa leo khổng lồ bự bằng cây dừa đưa cho chim to. Chim to cảm ơn rối rít, rồi lại chở Khánh ra đảo để ...vơ vét.

Lần này, chim to muốn trả ơn Khánh hậu hĩnh hơn nên tặng Khánh một núi đá quý. Có ~N~ loại đá quý. Mỗi loại đá lại có trọng lượng, giá trị và số lượng riêng. Rút kinh nghiệm đợt ~1~, Khánh đã cố may một cái túi bự gấp ~10~ lần cái túi lần trước mà vẫn không sao cho hết đống đá quý đó vào được. Trái tim Khánh không thể chịu thêm nỗi đau nào quá lớn nữa. Các bạn hãy giúp anh ấy chọn các viên đá cần lấy sao cho anh ấy càng giàu càng tốt và dĩ nhiên là cái túi vẫn không được rách.

Input

  • Dòng ~1~: Hai số nguyên: Số loại đá quý ~N~ (~1 \leq N \leq 100~) và sức chứa của cái túi ~M~ (~1 \le M \le 10000~).
  • ~N~ dòng tiếp theo: Mỗi dòng ghi ~3~ số nguyên: Khối lượng ~W_{i}~, giá trị ~V_{i}~ và số lượng ~A_{i}~ của viên đá thứ ~i~ (~1 \le W_{i}~, ~V_{i}~, ~A_{i} \le 1000~).

Output

  • Ghi một số nguyên duy nhất là giá trị lớn nhất thu được.

Sample Input

3 4
1 4 2
2 7 2
3 6 1

Sample Output

15

Comments

Please read the guidelines before commenting.



  • 27
    marvinthang   commented on March 21, 2022, 10:38 a.m. edited

    My solution:

    Với mỗi loại đá ~i~, ta chia nó thành ~A_i~ loại đá riêng biệt và QHĐ cái túi như bình thường.

    ĐPT: ~O(N * max_A * M)~.

    Cải tiến:

    Thay vì chia thành ~A_i~ loại đá thì ta chia thành ~log_2 A_i~ loại.

    Gọi ~k~ là số lớn nhất thỏa mãn ~2^0 + 2^1 + ... + 2^k = 2^{k + 1} - 1 \le A_i~.

    Khi đó ta có thể chia thành ~k~ cái túi như trên và thêm 1 cái túi chứa những viên đá còn lại, khi đó bằng cách chọn 1 vài túi ta luôn có thể tạo ra mọi giá trị ~\le A_i~.

    Chứng minh:

    Hiển nhiên ta có thể tạo được mọi giá trị trong đoạn ~[0, 2^{k + 1} - 1]~.

    Gọi ~x~ là số đá còn lại, ta cần chứng minh có thể tạo được mọi số đá trong đoạn ~[2^{k + 1}, A_i]~.

    Ta luôn có thể tạo được mọi số trong đoạn ~[x, x + 2^{k + 1} - 1]~.

    Ta thấy ~x \le 2^{k + 1} - 1~ (vì nếu ~x \ge 2^{k + 1}~ thì ~2 ^ {k + 2} - 1 \le A_i~, khi đó ~k~ không còn là số lớn nhất thỏa mãn) ~\le A_i = x + 2^{k + 1} - 1~.

    ~\Rightarrow [2^{k + 1}, A_i] \subset [x, x + 2^{k + 1} - 1]~ (đpcm).

    ĐPT: ~O(N * log_2 max_A * M)~.

    Code mẫu: Ideone.