Hoàng Tử Lai

Điểm: 1,00 (OI)

Giới hạn thời gian: 3.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Giáo sư Severus Snape - Hoàng Tử Lai - đang nấu một loại thuốc phép đặc biệt. Ông có $N$ nguyên liệu, mỗi nguyên liệu $i$ có hai tính chất ma thuật: độ chua $a_{i}$ và độ đắng $b_{i}$ (có thể âm hoặc dương).

Để thuốc phép thành công, Snape cần chọn một tập con các nguyên liệu sao cho tổng độ chua bằng đúng $A$ và tổng độ đắng bằng đúng $B$ .

Hãy đếm số tập con thỏa mãn điều kiện trên. Tập con rỗng (không chọn nguyên liệu nào) cũng được xem xét - nó có tổng độ chua và tổng độ đắng đều bằng $0$ .

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $N$ , $A$ , $B$ .
$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_{i}$ và $b_{i}$ — độ chua và độ đắng của nguyên liệu thứ $i$ .

Dữ liệu ra

In một số nguyên duy nhất - số tập con có tổng độ chua bằng $A$ và tổng độ đắng bằng $B$ .

Ràng buộc

$1 \leq N \leq 36$
$| A |, | B | \leq N \times 10^{9}$
$| a_{i} |, | b_{i} | \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 5 7 3 1 2 6 4 3 1 4	2	Hai tập con thỏa mãn: chọn nguyên liệu {1, 2} có tổng (3+2, 1+6) = (5, 7), hoặc chọn {3, 4} có tổng (4+1, 3+4) = (5, 7).
5 0 0 1 -3 -1 3 2 1 -2 -1 3 2	4	Bốn tập con có tổng (0, 0): tập rỗng, {1, 2} vì (1-1, -3+3) = (0, 0), {3, 4} vì (2-2, 1-1) = (0, 0), và {1, 2, 3, 4} vì (1-1+2-2, -3+3+1-1) = (0, 0).

Bình luận

Không có bình luận tại thời điểm này.