Thả bóng
Đề bài
Mô tả
Ở vòng thứ hai của Kỳ thi Hunter, các thí sinh phải đối mặt với một bài toán còn khó hơn, đòi hỏi cả sự nhanh nhẹn lẫn kỹ năng toán học.
Sau khi vào Hội trường thi của vòng hai, các thí sinh thấy một bảng lưới thẳng đứng khổng lồ gồm các ô trống, vật cản và băng chuyền. Bảng gồm phần giống hệt nhau, mỗi phần có kích thước ( hàng, cột), xếp chồng lên nhau theo chiều dọc. Để vượt qua vòng thi, mỗi thí sinh phải thả đúng một quả bóng vào bảng và đạt điểm cao nhất có thể.
Ví dụ, với , , và phần được mô tả ở ví dụ thứ nhất, bảng gồm hàng: hàng , và hàng , là các hàng R..?. và .X..., còn hàng và hàng là các ô điểm 100 100 7 100 8.
Mỗi ô của bảng thuộc một trong các loại sau:
- Ô trống. Quả bóng rơi xuyên qua ô này.
- Vật cản, chặn không cho bóng di chuyển. Nếu quả bóng rơi xuống trên đỉnh một vật cản, nó không thể đi đâu được nữa và bài thi kết thúc.
- Băng chuyền. Mọi băng chuyền đều nằm ngang và có hướng sang trái hoặc sang phải. Một số băng chuyền đã được đặt sẵn hướng, bạn phải đặt hướng cho các băng chuyền còn lại. Theo hướng của mình, băng chuyền đẩy quả bóng sang trái hoặc sang phải một ô. Nếu quả bóng bị đẩy ra ngoài bảng hoặc vào một vật cản, bài thi kết thúc ngay lập tức.
- Ký tự R và L biểu diễn băng chuyền đã được đặt hướng sang phải và sang trái, còn ? biểu diễn băng chuyền chưa được đặt hướng.
- Lưu ý rằng hai băng chuyền ở hai phần khác nhau được coi là khác nhau. Bạn có thể đặt hướng khác nhau cho chúng, kể cả khi chúng ở cùng một vị trí trong phần của mình.
- Ô điểm. Một ô thuộc loại này khi và chỉ khi nó nằm ở hàng cuối cùng của một phần nào đó. Ô này chứa một số nguyên là số điểm bạn nhận được khi quả bóng rơi vào ô. Quả bóng rơi xuyên qua ô này và bắt đầu đi vào phần tiếp theo, hoặc nếu đây là phần cuối cùng thì bài thi kết thúc.
Vì thời gian thi có hạn, bài thi cũng kết thúc khi quả bóng đã đi qua ô.
Điểm cuối cùng của bạn là tổng số điểm nhận được tới khi bài thi kết thúc. Bạn không bắt buộc phải làm quả bóng rơi tới đáy bảng. Để vượt qua vòng thi, bạn phải chọn cách đặt hướng các băng chuyền và chọn vị trí thả quả bóng (thả vào một cột, từ phía trên hàng đầu tiên của bảng) sao cho điểm cuối cùng lớn nhất. Bạn có làm được không?
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , và (, ).
dòng tiếp theo, mỗi dòng chứa đúng ký tự mô tả hàng đầu của một phần. Mỗi ký tự là một trong các ký tự sau:
- dấu chấm: ô trống;
- X: vật cản;
- R: băng chuyền đã được đặt hướng sang phải;
- L: băng chuyền đã được đặt hướng sang trái;
- ?: băng chuyền chưa được đặt hướng.
Dòng cuối cùng chứa đúng số nguyên, số thứ là , số điểm ở cột thứ của hàng cuối cùng trong mỗi phần ().
Dữ liệu ra
In ra một số nguyên là điểm cuối cùng lớn nhất.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 5 2 R..?. .X... 100 100 7 100 8 |
16 | Đặt băng chuyền ở hàng thứ nhất sang phải (R) và băng chuyền ở hàng thứ tư sang trái (L), rồi thả bóng vào cột thứ : ở mỗi phần, bóng bị đẩy sang cột và rơi xuống ô điểm . Cột và đưa bóng xuống trên đỉnh vật cản, nên không lấy được điểm . |
| 2 3 1 X.. .?. 10 1000 1 |
10 | Thả bóng vào cột và đặt băng chuyền sang trái: bóng rơi xuống ô điểm . Không có cách nào để bóng rơi vào ô điểm . |
| 2 3 100 X.. .?. 10 1000 1 |
100 | Nếu bóng rơi vào cột , nó rơi xuống trên đỉnh vật cản của phần tiếp theo. Thả bóng vào cột được điểm ở mỗi phần trong phần. |
Bình luận