NGUỒN: ĐỀ THI CHỌN ĐỘI TUYỂN DỰ THI HỌC SINH GIỎI QUỐC GIA - 2020 - HẢI PHÒNG
Cho dãy số nguyên dương . Ta định nghĩa dãy tích chênh lệch của dãy trên là một dãy trong đó:
Tức với (nếu không có chỉ số thì ).
Từ dãy , ta có một xâu tương ứng có ký tự chỉ gồm kí tự hoặc phụ thuộc vào dấu của dãy . Cụ thể:
nếu ;
nếu ;
nếu .
Ví dụ: Cho dãy
;
;
;
.
Xâu nhận được là .
Yêu cầu: Cho xâu kí tự gồm ký tự hoặc . Hãy tìm dãy số nguyên dương có thể sinh ra xâu theo mô tả trên. Nếu có nhiều dãy thỏa mãn, in ra dãy có thứ tự từ điển nhỏ nhất.
Dữ liệu vào:
Dòng đầu chứa số nguyên ;
Dòng thứ hai chứa xâu kí tự độ dài chỉ gồm kí tự hoặc .
Dữ liệu ra:
Ghi ra dãy có thứ tự từ điển nhỏ nhất thỏa mãn hoặc in ra nếu không tồn tại dãy nào như vậy.
Các số trên một dòng phải ghi cách nhau bởi ít nhất một dấu cách.
Ví dụ:
Dữ liệu vào:
4
0-+0
Dữ liệu ra:
1 2 3 1
Chú ý: Nếu học sinh chỉ in kết quả trong tất cả các test thì không được điểm của bài toán.
Giới hạn:
số test tương ứng với số điểm có ;
số test khác ứng với số điểm thỏa mãn điều kiện xâu nhập vào chỉ có kí tự ;
số test khác ứng với số điểm thỏa mãn điều kiện xâu nhập vào không có kí tự ;
