Nối bit
Đề bài
Mô tả
Có thật nhiều bit thì nên làm gì? Tất nhiên là nối chúng lại với nhau!
Hôm nay ở lớp, Minh được học về biểu diễn nhị phân của số nguyên và rất hào hứng muốn thực hành.
Ban đầu, Minh có một đồ thị gồm đỉnh, đánh số từ đến , chưa có cạnh nào. Sau đó Minh viết ra biểu diễn nhị phân của mọi số nguyên từ đến . Sau khi viết biểu diễn nhị phân của số nguyên , Minh thêm một cạnh nối mỗi cặp đỉnh sao cho bit thứ và bit thứ của đều bằng .
Cụ thể hơn, với mỗi số nguyên từ đến :
- Gọi là bit thấp nhất của , trong đó là bit thấp nhất. Có thể thêm các số ở đầu để biểu diễn nhị phân của có ít nhất bit.
- Với mọi cặp chỉ số () mà , Minh thêm một cạnh nối đỉnh thứ và đỉnh thứ .
Sau khi thêm xong mọi cạnh, Minh muốn biết đồ thị có liên thông hay không. Hãy giúp Minh trả lời câu hỏi này.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (), số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ có dạng:
- Dòng đầu tiên chứa số nguyên ().
- Dòng thứ hai chứa một xâu là biểu diễn nhị phân của (). Dữ liệu bảo đảm xâu này không có chữ số ở đầu.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra trên một dòng YES nếu đồ thị liên thông, ngược lại in NO.
Ràng buộc
- , xâu nhị phân của không có chữ số ở đầu
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 100 3 111 |
NO YES |
Bộ thứ nhất (, ): khi viết (001), (010) và (100) không có cạnh nào được thêm; khi viết (011) thêm cạnh . Đỉnh không nối được với đỉnh và nên đồ thị không liên thông. Bộ thứ hai (, ): ngoài cạnh từ số , số (101) thêm cạnh , số (110) thêm cạnh , số (111) thêm cả ba cạnh; đồ thị liên thông. |
| 5 1 0 2 10 2 11 4 101 3 1000 |
YES NO YES NO YES |
Ví dụ bổ sung. Bộ thứ nhất: đồ thị chỉ có một đỉnh nên liên thông. Bộ thứ tư: không số nào từ đến có bit thứ bằng , nên đỉnh cô lập. Bộ thứ năm: số thêm cả ba cạnh. |
Bình luận