trang chủ / đề bài / icpc22_nat_b

Xâu nhị phân

Đề bài

Mô tả

Định nghĩa hàm f nhận vào k xâu nhị phân có cùng độ dài m (k là số lẻ) như sau:

  • Kết quả là một xâu nhị phân độ dài m.
  • Xét bit thứ i của k xâu:
    • gọi c0 là số xâu có bit thứ i bằng 0;
    • gọi c1 là số xâu có bit thứ i bằng 1;
    • nếu c0>c1 thì bit thứ i của kết quả là 0, ngược lại bit thứ i của kết quả là 1.

Ví dụ: f(100,111,010)=110.

Cho một tập S gồm n xâu nhị phân cùng độ dài m và một số nguyên lẻ k. Hãy kiểm tra xem S có phải là tập k-đẹp hay không.

Tập S được gọi là k-đẹp khi và chỉ khi với mọi cách chọn k xâu x1,x2,…,xk trong S, xâu f(x1,x2,…,xk) cũng thuộc S. Lưu ý một xâu của S có thể được chọn nhiều lần.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên n, m, k.
  • n dòng tiếp theo, mỗi dòng chứa một xâu nhị phân độ dài m. Các xâu đôi một khác nhau.

Dữ liệu ra

In ra YES nếu S là tập k-đẹp, ngược lại in ra NO.

Ràng buộc

  • 1≤k≤n≤300, k lẻ.
  • 1≤m≤300.

Ví dụ

Input Output Giải thích
3 3 3
100
111
010
NO f(100,111,010)=110 không thuộc S.
4 2 3
00
01
10
11
YES S chứa mọi xâu độ dài 2 nên kết quả luôn thuộc S.

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