trang chủ / đề bài / icpc23_reg_l

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 m đỉnh, đánh số từ 0 đến m−1, 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ừ 1 đến n. Sau khi viết biểu diễn nhị phân của số nguyên x, Minh thêm một cạnh nối mỗi cặp đỉnh (i,j) sao cho bit thứ i và bit thứ j của x đều bằng 1.

Cụ thể hơn, với mỗi số nguyên x từ 1 đến n:

  • Gọi xm−1xm−2…x0 là m bit thấp nhất của x, trong đó x0 là bit thấp nhất. Có thể thêm các số 0 ở đầu để biểu diễn nhị phân của x có ít nhất m bit.
  • Với mọi cặp chỉ số (i,j) (0≤i<j≤m−1) mà xi=xj=1, Minh thêm một cạnh nối đỉnh thứ i và đỉnh thứ j.

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 t (1≤t≤103), số bộ dữ liệu. Tiếp theo là t bộ dữ liệu, mỗi bộ có dạng:

  • Dòng đầu tiên chứa số nguyên m (1≤m≤103).
  • Dòng thứ hai chứa một xâu là biểu diễn nhị phân của n (0≤n<2103). Dữ liệu bảo đảm xâu này không có chữ số 0 ở đầ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

  • 1≤t≤103
  • 1≤m≤103
  • 0≤n<2103, xâu nhị phân của n không có chữ số 0 ở đầu

Ví dụ

Input Output Giải thích
2
3
100
3
111
NO
YES
Bộ thứ nhất (m=3, n=4): khi viết 1 (001), 2 (010) và 4 (100) không có cạnh nào được thêm; khi viết 3 (011) thêm cạnh (0,1). Đỉnh 2 không nối được với đỉnh 0 và 1 nên đồ thị không liên thông. Bộ thứ hai (m=3, n=7): ngoài cạnh (0,1) từ số 3, số 5 (101) thêm cạnh (0,2), số 6 (110) thêm cạnh (1,2), số 7 (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ừ 1 đến 5 có bit thứ 3 bằng 1, nên đỉnh 3 cô lập. Bộ thứ năm: số 7 thêm cả ba cạnh.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0