Bao phủ phép OR
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho $N$ phần tử, phần tử thứ $i$ có giá trị nguyên không âm $A_i$ và chi phí $C_i$. Gọi $T = A_1 \mid A_2 \mid \dots \mid A_N$ là phép OR theo bit của toàn bộ $N$ phần tử.
Bạn cần chọn ra một tập con các phần tử (có thể rỗng nếu $T = 0$) sao cho phép OR theo bit của các phần tử được chọn đúng bằng $T$, đồng thời tổng chi phí là nhỏ nhất.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 20$).
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $A_i, C_i$ ($0 \le A_i < 2^{30}$, $1 \le C_i \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 3 3 10 5 2 6 3 |
5 |
| 4 1 5 2 5 4 5 7 12 |
12 |
Giới hạn
- $1 \le N \le 20$.
- $0 \le A_i < 2^{30}$, $1 \le C_i \le 10^9$.
Community Discussion