golds
Xem PDF
Điểm:
100 (p)
Thời gian:
2.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Trong chuyện cổ tích cây khế, con chim ăn khế và trả vàng cho người em.
Chim chở người em đến chỗ chứa vàng, ở đó có n cục vàng. Cục thứ \(i\) có khối lượng là \(m_i\).
Túi ba gang có sức chứa là \(M\), hãy đếm xem có bao nhiêu cách để người em chọn các cục vàng để lấy. Hai cách lấy được coi là khác nhau nếu tồn tại \(i\) sao cho ở cách lấy này có lấy cục thứ \(i\) còn ở cách kia thì không.
Input
- Dòng 1: \(n, M\)
- Dòng 2: \(m_1, m_2,. . . ,m_n\)
Output
- Ghi ra một số duy nhất là kết quả tìm được.
Scoring
- \(n \le 40\) ; \(1 \le m_i\) , \(M \le 10^6\)
- Subtask \(1\) (\(50\%\) số điểm): \(n \le 20\)
Example
Test 1
Input
4 10
3 10 5 4Output
8
Bình luận
tác giả cho xin cái note đi ạ khó hiểu quá :v
có 8 cách lấy (số ở dưới là giá trị của từng cục vàng):
[], [3], [10], [5], [4], [3, 5], [5, 4], [3, 4]
(trong đó [] có nghĩa là không lấy cục nào)