trang chủ / đề bài / icpc19_nat_d

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 K phần giống hệt nhau, mỗi phần có kích thước (R+1)×C (R+1 hàng, C 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 R=2, C=5, K=2 và phần được mô tả ở ví dụ thứ nhất, bảng gồm 6 hàng: hàng 1, 2 và hàng 4, 5 là các hàng R..?. và .X..., còn hàng 3 và hàng 6 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 1020 ô.

Đ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 3 số nguyên R, C và K (1≤R,C≤50, 1≤K≤109).

R dòng tiếp theo, mỗi dòng chứa đúng C ký tự mô tả R 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 C số nguyên, số thứ i là ai, số điểm ở cột thứ i của hàng cuối cùng trong mỗi phần (1≤ai≤109).

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

  • 1≤R,C≤50
  • 1≤K≤109
  • 1≤ai≤109

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ứ 4: ở mỗi phần, bóng bị đẩy sang cột 5 và rơi xuống ô điểm 8. Cột 1 và 2 đưa bóng xuống trên đỉnh vật cản, nên không lấy được điểm 100.
2 3 1
X..
.?.
10 1000 1
10 Thả bóng vào cột 2 và đặt băng chuyền sang trái: bóng rơi xuống ô điểm 10. Không có cách nào để bóng rơi vào ô điểm 1000.
2 3 100
X..
.?.
10 1000 1
100 Nếu bóng rơi vào cột 1, 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 3 được 1 điểm ở mỗi phần trong 100 phần.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0