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 gồm đúng 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 , giáo sư Awk quan tâm đến hai giá trị sau:
- : độ dài của khối 0 dài nhất trong ,
- : độ dài của khối 1 ngắn nhất trong .
Lưu ý rằng nếu không có khối 0 nào thì . Nếu không có khối 1 nào thì .
Giáo sư Awk nhờ Bash tìm một xâu hài hòa , 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 đúng bằng .
- Giá trị là nhỏ nhất.
Dữ liệu vào
Dòng đầu tiên chứa (): 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 và (, ).
Đảm bảo tổng trên tất cả các bộ dữ liệu không vượt quá .
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
- .
- , , tổng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 2 4 2 |
110 0110 |
Bộ 1: , , giá trị . Bộ 2: , , giá trị . |
| 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, . Bộ 2: không có khối 0, , giá trị . Bộ 3: 5 chữ số 0 chia được nhiều nhất thành 3 khối, nên ; ba khối 0 cần đúng hai khối 1, . Bộ 4: , . |
Bình luận