trang chủ / đề bài / icpc25_nat_h

Xâu hài hòa

Đề bài

Mô tả

Hôm nay, giáo sư Awk dạy Bash về xâu nhị phân và những tính chất đẹp đẽ của chúng. Một xâu nhị phân độ dài n gồm đúng n ký tự, mỗi ký tự là 0 hoặc 1.

Mọi xâu nhị phân đều có thể được phân tách thành các khối, mỗi khối là một đoạn liên tiếp cực đại gồm các ký tự giống nhau. Ví dụ, xâu nhị phân 1110011011000 được phân tách thành 6 khối: 111, 00, 11, 0, 11 và 000. Ta gọi khối chỉ gồm chữ số 0 là khối 0, và khối chỉ gồm chữ số 1 là khối 1.

Với một xâu nhị phân w, giáo sư Awk quan tâm đến hai giá trị sau:

  • L0: độ dài của khối 0 dài nhất trong w,
  • S1: độ dài của khối 1 ngắn nhất trong w.

Lưu ý rằng nếu w không có khối 0 nào thì L0=0. Nếu w không có khối 1 nào thì S1=0.

Giáo sư Awk nhờ Bash tìm một xâu hài hòa w, là một xâu nhị phân thỏa mãn tất cả các điều kiện sau:

  • Số chữ số 1 trong w đúng bằng k.
  • Giá trị L0·(n+1)−S1 là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa τ (1≤τ≤105): số bộ dữ liệu. Tiếp theo là τ bộ dữ liệu, mỗi bộ gồm một dòng chứa hai số nguyên n và k (1≤n≤105, 0≤k≤n).

Đảm bảo tổng n trên tất cả các bộ dữ liệu không vượt quá 105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một xâu hài hòa. Nếu có nhiều lời giải tối ưu, bạn có thể in ra bất kỳ lời giải nào.

Ràng buộc

  • 1≤τ≤105.
  • 1≤n≤105, 0≤k≤n, tổng n không vượt quá 105.

Ví dụ

Input Output Giải thích
2
3 2
4 2
110
0110
Bộ 1: L0=1, S1=2, giá trị 1·4−2=2. Bộ 2: L0=1, S1=2, giá trị 1·5−2=3.
4
5 0
5 5
7 2
10 3
00000
11111
0010010
0010010010
Ví dụ bổ sung (không có trong đề gốc). Bộ 1: không có khối 1, L0=5. Bộ 2: không có khối 0, S1=5, giá trị −5. Bộ 3: 5 chữ số 0 chia được nhiều nhất thành 3 khối, nên L0=2; ba khối 0 cần đúng hai khối 1, S1=1. Bộ 4: L0=2, S1=1.

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