Zebra
Đề bài
Mô tả
Oleg ghi lại lịch sử những ngày mình đã sống. Mỗi ngày được đánh dấu là ngày tốt (ký hiệu là ) hoặc ngày xấu (ký hiệu là ).
Một dãy các ngày không rỗng được gọi là một zebra nếu nó bắt đầu bằng một ngày xấu, kết thúc bằng một ngày xấu, và các ngày tốt, xấu xen kẽ nhau. Ví dụ, các dãy , , là zebra, còn , , thì không.
Lịch sử của Oleg được cho dưới dạng một xâu gồm các ký tự và theo thứ tự thời gian. Hãy chia lịch sử này thành một số dãy con, mỗi dãy con là một zebra. Mỗi ngày phải thuộc đúng một dãy con, và trong mỗi dãy con các ngày phải giữ nguyên thứ tự thời gian (dãy con không nhất thiết gồm các ngày liên tiếp).
Nếu có cách chia, hãy in ra một cách bất kỳ. Nếu không, in ra .
Dữ liệu vào
Một dòng duy nhất chứa xâu không rỗng gồm các ký tự và .
Dữ liệu ra
Nếu không thể chia, in ra .
Ngược lại, dòng đầu in số nguyên (), là số dãy con. Trong dòng tiếp theo, dòng thứ in số nguyên (độ dài dãy con thứ ), tiếp theo là chỉ số của các ngày tạo thành dãy con đó theo thứ tự tăng dần. Các ngày được đánh số bắt đầu từ .
Mỗi chỉ số từ đến phải xuất hiện đúng một lần. Các dãy con có thể in theo thứ tự bất kỳ. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.
Ràng buộc
- chỉ gồm các ký tự và
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 0010100 | 3 1 1 5 2 3 4 5 6 1 7 |
Chia thành ba zebra: ngày (1) cho xâu 0, các ngày (2,3,4,5,6) cho xâu 01010, và ngày (7) cho xâu 0. Nhiều cách chia khác cũng được chấp nhận. |
| 111 | -1 | Không ngày nào là ngày xấu nên không thể tạo bất kỳ zebra nào. |
Bình luận