BALANCE - Cân thằng bằng
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Cân thằng bằng đã từng rất phổ biến trong xã hội loài người, vì tính đơn giản của nó. Cấu tạo của cân gồm hai đĩa A, B được đặt ở hai đầu của một đòn bẩy. Có n quả cân, quả thứ i có khối lượng mi. Để cân một vật, người ta đặt nó vào đĩa A, sau đó thêm một vài quả cân vào các đĩa sao cho cân thăng bằng. Lúc này, cân nặng của vật là tổng khối lượng các quả cân trên đĩa B trừ đi tổng khối lượng các quả cân trên đĩa A, vì cân chỉ thăng bằng khi tổng khối lượng trên đĩa A bằng tổng khối lượng trên đĩa B.

Tuần trước, con chim vừa chở người em đi lấy vàng về, người em tiến hành cân lại số vàng mình nhận được. Để thuận tiện, anh ấy sẽ để nguyên túi vàng và cân một lần thay vì phải tách số vàng ra. Sau khi cân, anh ấy biết chính xác rằng túi vàng nặng M. Sau đó, vì tò mò và đam mê thuật toán, anh ấy thắc mắc là liệu có bao nhiêu cách cân khác nhau? Cụ thể hơn, bạn được cho một vật có khối lượng M, bạn đặt nó vào đĩa A sau đó thêm một số quả cân vào các đĩa sao cho cân thăng bằng. Cần đếm số cách khác nhau để thêm các quả cân như trên. Hai cách được coi là khác nhau nếu tồn tại i, 1 ≤ i ≤ n, sao cho hoặc là trong cách này thì sử dụng quả cân thứ i còn trong cách kia thì không, hoặc là cả hai cách đều sử dụng quả cân thứ i nhưng đặt vào hai đĩa khác nhau.

Dữ liệu vào

• Dòng đầu chứa: n M
• Dòng tiếp theo chứa dãy m

Kết quả

Một số nguyên duy nhất là kết quả bài toán 

Ví dụ

Input

6 10
1 2 3 4 5 6

Output

17

Hạn chế

n ≤ 20, 1 ≤ mi , M ≤ 106 ;
• 50% với n ≤ 10


Nguồn: ĐPT '1819

Back to Top