trang chủ / đề bài / icpc21_mb_d

Tập xâu nhị phân

Đề bài

Mô tả

Cho S là một tập các xâu. Ký hiệu S* là tập gồm xâu rỗng và mọi xâu thu được bằng cách ghép nối các xâu thuộc S (mỗi xâu trong S có thể được dùng nhiều lần).

Cho n xâu T1,…,Tn. Với mỗi Ti, hãy tìm số ký tự ít nhất cần xóa khỏi Ti để xâu còn lại thuộc {0,01,10}*.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n.
  • n dòng tiếp theo, mỗi dòng chứa một xâu Ti gồm các ký tự '0' và '1'.

Dữ liệu ra

In ra n dòng, dòng thứ i chứa một số nguyên là số ký tự ít nhất cần xóa khỏi Ti.

Ràng buộc

  • 1≤n≤106.
  • Tổng độ dài các xâu Ti không vượt quá 106.

Ví dụ

Input Output Giải thích
2
00110
110
0
1
00110 = 0 + 01 + 10 nên không cần xóa. Với 110, xóa một ký tự 1 được 10.
3
1
0101
1100
1
0
1
Ví dụ bổ sung (không có trong đề gốc). 0101 = 01 + 01; với 1100, xóa ký tự 1 đầu tiên được 100 = 10 + 0.

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