Lop B 2026 - Contest #8 - Duyet phan tap

Bạn được cho một mảng gồm \(n\) số. Có bao nhiêu cách chọn tập hợp con các số có tổng \(x\)?

Input

Dòng đầu tiên là hai số \(n\) và \(x\) : kích thước mảng và tổng bắt buộc.

Dòng thứ hai chứa \(n\) số nguyên \(t_1,t_2,…, t_n\): các số trong mảng.

Output

In ra số cách bạn có thể tạo ra tổng \(x\).

Example

4 5
1 2 3 2

3

Trong một chuyến phiêu lưu đầy thử thách, bạn theo chân chú chim thần kỳ đến một hang động chứa kho báu. Hang động này được canh giữ bởi một loài chim khổng lồ - Hắc Điểu. Tuy nhiên, chú chim thần kỳ giúp bạn vượt qua Hắc Điểu và tiến vào nơi cất giữ những khối vàng quý giá.

Hang động chứa \(n\) khối vàng, mỗi khối có khối lượng là \(m_i\). Tuy nhiên, bạn chỉ có một chiếc túi ba gang với sức chứa tối đa là \(M\). Nhiệm vụ của bạn là tìm xem có bao nhiêu cách khác nhau để chọn một số khối vàng sao cho tổng khối lượng không vượt quá \(M\).

Hãy nhớ rằng, hai cách được coi là khác nhau nếu tồn tại ít nhất một khối vàng mà cách này chọn nhưng cách kia thì không, bất kể thứ tự lựa chọn

Input

Dữ liệu được nhập từ tiêu chuẩn đầu vào với cấu trúc sau:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(M\) \((1 \leq n \leq 40, 1 \leq M \leq 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên \(m_1, m_2, \ldots, m_n\) \((1 \leq m_i \leq M)\), biểu thị khối lượng của từng khối vàng.

Output

In ra một số duy nhất là tổng số cách có thể chọn các khối vàng sao cho tổng khối lượng không vượt quá \(M\).

Example

4 10
3 10 5 4

8

Trong một công ty công nghệ lớn, bạn được giao nhiệm vụ tổ chức một hội thảo chuyên đề cho \(N\) nhân viên. Mỗi nhân viên được đánh giá bằng một chỉ số đặc biệt gọi là độ tin cậy (\(a_i\)), biểu thị khả năng thực hiện các nhiệm vụ quan trọng của họ.

Nhiệm vụ của bạn là chia \(N\) nhân viên thành hai nhóm Group A và Group B, với các yêu cầu sau:

• Mỗi nhân viên thuộc đúng một nhóm.
• Sự chênh lệch về tổng độ tin cậy giữa hai nhóm là nhỏ nhất có thể.

Hãy tìm cách phân chia tối ưu và báo cáo giá trị độ chênh lệch nhỏ nhất cũng như số lượng cách phân chia đạt được kết quả này.

Input

Dữ liệu đầu vào gồm:

• Dòng đầu chứa một số nguyên \(N\) \((2 \leq N \leq 32)\), là số nhân viên.
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) \((1 \leq a_i \leq 10^9)\), là độ tin cậy của các nhân viên.

Output

In ra hai số nguyên \(u\) và \(v\):

• \(u\): độ chênh lệch nhỏ nhất giữa tổng độ tin cậy của hai nhóm.
• \(v\): số lượng cách phân chia đạt được độ chênh lệch nhỏ nhất.

Example

5
1 5 6 7 8

1 3

Lan đang học cách điều khiển một con robot mà cô ấy vừa nhận được như một món quà.
Robot bắt đầu tại tọa độ \((0,0)\) trên mặt phẳng toạ độ và Lan muốn robot di chuyển đến điểm \((x_g, y_g)\).

Lan có một danh sách gồm \(N\) hướng dẫn, với \(1 \le N \le 40\).
Hướng dẫn thứ \(i\) sẽ khiến robot di chuyển \(x_i\) đơn vị theo trục hoành và \(y_i\) đơn vị theo trục tung.
Giá trị âm tương ứng với việc di chuyển sang trái hoặc đi xuống.

Với mỗi \(K\) từ \(1\) đến \(N\), hãy xác định số cách chọn đúng \(K\) hướng dẫn từ \(N\) hướng dẫn ban đầu sao cho sau khi thực hiện các hướng dẫn này (theo bất kỳ thứ tự nào), robot dừng lại chính xác tại điểm \((x_g, y_g)\).

\InputFile

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa hai số nguyên \(x_g, y_g\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i, y_i\).

Các giá trị \(x_g, y_g, x_i, y_i\) nằm trong đoạn \([-10^9, 10^9]\).

Đảm bảo:

• \((x_g, y_g) \ne (0, 0)\)
• \((x_i, y_i) \ne (0, 0)\) với mọi \(i\).

\OutputFile
In ra \(N\) dòng.
Dòng thứ \(K\) chứa số cách chọn đúng \(K\) hướng dẫn sao cho robot kết thúc tại \((x_g, y_g)\).

Example

7
5 10
-2 0
3 0
4 0
5 0
0 10
0 -10
0 10

0
2
0
3
0
1
0