trang chủ / đề bài / icpc24_mb_g

Xâu đẹp

Đề bài

Mô tả

Xâu nhị phân là xâu chỉ gồm các ký tự 0 và 1. Một xâu nhị phân được gọi là đẹp nếu với mỗi ký tự 1 trong xâu, số ký tự 0 liên tiếp tính từ nó sang trái đến ký tự 1 gần nhất (hoặc đến đầu xâu) bằng số ký tự 0 liên tiếp tính từ nó sang phải đến ký tự 1 gần nhất (hoặc đến cuối xâu). Nói cách khác, với mỗi ký tự 1, số ký tự 0 liên tiếp ngay bên trái nó bằng số ký tự 0 liên tiếp ngay bên phải nó. Ví dụ, xâu 0001000 là xâu đẹp, còn xâu 001010 không đẹp vì bên trái ký tự 1 đầu tiên có hai ký tự 0, còn bên phải nó chỉ có một ký tự 0.

Cho một xâu nhị phân, bạn cần xóa một số ký tự của nó để được một xâu đẹp. Hãy in ra độ dài lớn nhất của xâu đẹp có thể nhận được bằng cách xóa các ký tự của xâu đã cho. Xâu kết quả phải chứa ít nhất một ký tự 1.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n: độ dài xâu nhị phân (1≤n≤500000).
  • Dòng thứ hai chứa xâu gồm n ký tự, mỗi ký tự là 0 hoặc 1. Dữ liệu đảm bảo xâu chứa ít nhất một ký tự 1.

Dữ liệu ra

In ra một số nguyên là độ dài lớn nhất của xâu đẹp nhận được.

Ràng buộc

  • 1≤n≤500000
  • Xâu chỉ gồm các ký tự 0 và 1, có ít nhất một ký tự 1.

Ví dụ

Input Output Giải thích
10
0000010100
7 Xóa ký tự 1 cuối cùng và hai ký tự 0 đầu tiên để được xâu 0001000.
4
1111
4 Xâu 1111 đã là xâu đẹp, không cần xóa ký tự nào.
7
0101001
5 Xóa hai ký tự cuối để được xâu đẹp 01010.

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