Dải ô thứ nhất
Đề bài
Mô tả
Để chinh phục trái tim Yến Nhi, Quang Trí nhận một thử thách hóc búa từ cô. Yến Nhi vẽ trên sàn một dải gồm ô vuông liên tiếp (gọi là dải thứ nhất), các ô được đánh số từ tới từ trái sang phải. Với mỗi ô, Quang Trí phải chọn tô màu đỏ hoặc màu xanh. Mọi ô đều phải được tô màu, tức là Quang Trí không được để trống ô nào.
Yến Nhi có cây bút mực đỏ và cây bút mực xanh để hỗ trợ Quang Trí tô màu. Mỗi cây bút chứa vừa đủ mực để tô đúng một ô với màu tương ứng.
Ban đầu Quang Trí có điểm. Nếu muốn lấy cây bút mực đỏ, Quang Trí bị trừ điểm. Tương tự, nếu muốn lấy cây bút mực xanh, Quang Trí bị trừ điểm. Quy ước .
Ngoài ra, Yến Nhi đưa ra một luật đặc biệt để Quang Trí được cộng điểm. Cô có một dải ô khác độ dài (gọi là dải thứ hai) mà mọi ô đã được tô đỏ hoặc xanh. Với mỗi đoạn liên tiếp độ dài của dải thứ nhất có cách tô trùng với dải thứ hai, Quang Trí được cộng điểm. Cách tô của một đoạn được coi là trùng với cách tô của đoạn kia nếu không tồn tại cặp ô ở cùng vị trí (tính từ trái sang) trong hai đoạn mà có màu khác nhau. Các đoạn được tính có thể chồng lên nhau.
Quang Trí muốn tìm cách tô dải thứ nhất để điểm cuối cùng là lớn nhất (để gây ấn tượng tốt với Yến Nhi). Hãy giúp Quang Trí tìm cách tô tối ưu!
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên , , (, , ): độ dài dải thứ nhất, độ dài dải thứ hai và số điểm thưởng cho mỗi đoạn liên tiếp của dải thứ nhất có cách tô trùng với dải thứ hai.
- Dòng thứ hai chứa số nguyên ().
- Dòng thứ ba chứa số nguyên ().
- Dòng thứ tư chứa một xâu độ dài gồm các ký tự 'R' hoặc 'B': ô tương ứng của dải thứ hai được tô màu đỏ hoặc xanh.
Dữ liệu ra
In ra hai dòng. Dòng đầu tiên là điểm cuối cùng lớn nhất mà Quang Trí đạt được. Dòng thứ hai là một xâu độ dài mô tả cách tô: ký tự thứ là 'R' nếu ô thứ của dải thứ nhất được tô đỏ, ngược lại là 'B'. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.
Ràng buộc
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 2 1 1 2 3 4 5 6 6 5 4 3 2 1 RR |
-1 RRRRRR |
Có hai cách đạt điểm. Dùng bút đỏ: có đoạn liên tiếp trùng với dải thứ hai, điểm là . Dùng bút xanh: không có đoạn nào trùng, điểm là . |
| 6 2 4 1 2 3 4 5 6 6 5 5 3 2 1 RB |
4 RBRBRB |
Dùng bút đỏ và bút xanh, có đoạn trùng: . |
| 6 2 3 1 2 6 4 5 6 6 5 4 3 2 1 RB |
1 RBRBBB |
Dùng bút đỏ và bút xanh, có đoạn trùng: . |
Bình luận