Tô màu bằng số là một trò chơi đố nổi tiếng. Trong phiên bản một chiều của trò chơi, có một hàng gồm \(n\) ô, đánh số từ \(0\) đến \(n-1\) từ trái sang phải. Mỗi ô phải được tô đen hoặc trắng. Ký tự X biểu thị ô đen và _ biểu thị ô trắng.

Người chơi được cho một dãy gợi ý \(c=[c_0,\ldots,c_{k-1}]\) gồm \(k\) số nguyên dương. Các ô đen phải tạo thành đúng \(k\) khối liên tiếp, ngăn cách nhau bởi ít nhất một ô trắng. Khối thứ \(i\) từ trái sang, đánh số từ \(0\), phải có đúng \(c_i\) ô đen.

Ví dụ, với \(n=10\) và \(c=[3,4]\), cách tô _XXX__XXXX hợp lệ. Cách tô XXXX_XXX__ không hợp lệ vì hai khối có độ dài sai thứ tự. Cách tô __XXXXXXX_ cũng không hợp lệ vì chỉ có một khối đen thay vì hai khối tách biệt.

Bạn được cho một phần lời giải: ngoài \(n\) và \(c\), màu của một số ô đã được xác định là đen hoặc trắng. Một lời giải đúng phải thỏa mãn các gợi ý và giữ nguyên màu đã biết. Hãy xác định những ô đen trong mọi lời giải đúng, những ô trắng trong mọi lời giải đúng, và những ô có thể nhận cả hai màu ở các lời giải đúng khác nhau.

Dữ liệu luôn có ít nhất một lời giải đúng.

Chi tiết cài đặt

Trong C++, cài đặt hàm khai báo trong paint.h:

std::string solve_puzzle(std::string s, std::vector<int> c);

Trong Java, cài đặt phương thức sau trong lớp paint:

public String solve_puzzle(String s, int[] c)

Trong C, giao diện là:

void solve_puzzle(int n, char* s, int k, int* c, char* result);

• s: xâu độ dài \(n\). Với \(0 \le i < n\), s[i] là X nếu ô \(i\) phải đen, _ nếu phải trắng, và . nếu chưa có thông tin.
• c: mảng độ dài \(k\) chứa các gợi ý theo thứ tự từ trái sang phải.
• Với C++ và Java, trả về xâu độ dài \(n\). Ký tự thứ \(i\) phải là X nếu ô đó đen trong mọi lời giải đúng, _ nếu trắng trong mọi lời giải đúng, hoặc ? nếu có cả lời giải tô đen và lời giải tô trắng ô đó.
• Với C, n là độ dài s, k là số gợi ý. Ghi \(n\) ký tự của đáp án vào mảng result được cấp sẵn thay vì trả về xâu.

Mã ASCII của X, _, ., ? lần lượt là \(88,95,46,63\). Ký tự chưa biết ở đầu vào là ., còn ký tự chưa xác định được ở đầu ra là ?.

Nộp phần cài đặt hàm, không viết hàm main; sử dụng các tệp mẫu của ngôn ngữ tương ứng trong gói đính kèm. Khi nộp bằng C trên LQDOJ, dùng #include "paint.h" thay cho #include "paint_c.h" trong tệp mẫu; header dùng chung cung cấp đúng giao diện C ở trên.

Ràng buộc

• \(1 \le n \le 200\,000\).
• \(1 \le k \le n\) và \(1 \le c_i \le n\) với mọi \(0 \le i < k\).
• s chỉ gồm các ký tự X, _, ..
• Có ít nhất một lời giải đúng phù hợp với s và c.

Phân nhóm

Mỗi subtask được tính trọn số điểm khi tất cả các test của subtask đó đều đúng; nếu không, subtask được \(0\) điểm. Các ràng buộc chung luôn áp dụng.

Ví dụ

Lời gọi thứ nhất:

solve_puzzle("..........", [3, 4])

Có đúng sáu cách tô hợp lệ:

XXX_XXXX__
XXX__XXXX_
XXX___XXXX
_XXX_XXXX_
_XXX__XXXX
__XXX_XXXX

Các ô \(2,6,7\) luôn đen. Mỗi ô còn lại đều có thể đen hoặc trắng tùy lời giải, nên đáp án là ??X???XX??.

Lời gọi thứ hai:

solve_puzzle("........", [3, 4])

Chỉ có một cách tô hợp lệ, nên đáp án là XXX_XXXX.

Lời gọi thứ ba:

solve_puzzle("..._._....", [3])

Không thể đặt khối ba ô đen vào giữa hai ô trắng \(3\) và \(5\), nên ô \(4\) cũng phải trắng. Đáp án là ???___????.

Lời gọi thứ tư:

solve_puzzle(".X........", [3])

Chỉ có hai cách tô hợp lệ là XXX_______ và _XXX______. Do đó đáp án là ?XX?______.

Trình chấm mẫu

Trình chấm mẫu đọc dòng đầu chứa xâu s; dòng tiếp theo chứa \(k\), rồi đến \(k\) số \(c_0,\ldots,c_{k-1}\). Chương trình in xâu kết quả của solve_puzzle trên một dòng.

..........
2 3 4

??X???XX??

........
2 3 4

XXX_XXXX

..._._....
1 3

???___????

.X........
1 3

?XX?______

Nguồn

IOI 2016, ngày thi thứ hai, bài Paint By Numbers. Đề tiếng Việt và gói tệp dành cho thí sinh được đính kèm.