JOI 2018 - Dango Maker
Xem PDFBạn là một thợ làm bánh chuyên nghiệp, chuyên làm dango, một loại bánh viên ngọt của Nhật Bản. Bây giờ, bạn chuẩn bị xiên các viên bánh vào que.
Các viên bánh được đặt trên một bảng gồm \(N\) hàng và \(M\) cột, mỗi ô chứa một viên. Mỗi viên có một trong ba màu: đỏ (R), xanh lá (G) hoặc trắng (W).
Để tạo một xiên bánh, bạn chọn ba viên ở ba ô liên tiếp theo chiều từ trái sang phải hoặc từ trên xuống dưới, rồi xiên chúng theo đúng thứ tự đó. Bạn chỉ muốn tạo các xiên có màu lần lượt là đỏ, xanh lá, trắng. Không được dùng một viên bánh cho nhiều hơn một xiên.
Cho màu của tất cả các viên bánh trên bảng, hãy tìm số xiên bánh nhiều nhất có thể tạo ra.
Dữ liệu vào
Đọc từ đầu vào chuẩn:
- Dòng đầu chứa hai số nguyên \(N,M\), cách nhau bởi dấu cách.
- Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa một xâu độ dài \(M\), chỉ gồm các ký tự
R,G,W. Ký tự thứ \(j\) là màu của viên bánh ở hàng thứ \(i\) tính từ trên xuống và cột thứ \(j\) tính từ trái sang phải.
Dữ liệu ra
Ghi một dòng chứa số xiên bánh nhiều nhất có thể tạo ra, mỗi xiên gồm ba màu đỏ, xanh lá, trắng theo đúng thứ tự.
Ràng buộc
- \(1\le N\le3000\).
- \(1\le M\le3000\).
- Mỗi hàng của bảng là một xâu độ dài \(M\) chỉ gồm
R,G,W.
Phân nhóm
- (13 điểm) \(N\le4\) và \(M\le4\).
- (20 điểm) \(N\le10\) và \(M\le10\).
- (67 điểm) Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
3 4
RGWR
GRGG
RGWWOutput
3Giải thích
Có thể tạo ba xiên như sau. Các tọa độ dưới đây có dạng (hàng, cột), tính từ trên xuống và từ trái sang phải:
- Chọn ba viên liên tiếp từ ô \((1,1)\) theo chiều từ trái sang phải: \((1,1),(1,2),(1,3)\).
- Chọn ba viên liên tiếp từ ô \((1,4)\) theo chiều từ trên xuống dưới: \((1,4),(2,4),(3,4)\).
- Chọn ba viên liên tiếp từ ô \((3,1)\) theo chiều từ trái sang phải: \((3,1),(3,2),(3,3)\).
Trong mỗi trường hợp, xiên các viên theo thứ tự vừa chọn. Không thể tạo bốn xiên, nên đáp án là \(3\).
Ví dụ 2
Input
4 4
RGWR
GRRG
WGGW
WWWROutput
4Giải thích
Có thể tạo bốn xiên, mỗi xiên theo đúng thứ tự các viên được liệt kê:
- Từ ô \((1,1)\) theo chiều từ trái sang phải: \((1,1),(1,2),(1,3)\).
- Từ ô \((1,4)\) theo chiều từ trên xuống dưới: \((1,4),(2,4),(3,4)\).
- Từ ô \((2,2)\) theo chiều từ trên xuống dưới: \((2,2),(3,2),(4,2)\).
- Từ ô \((2,3)\) theo chiều từ trên xuống dưới: \((2,3),(3,3),(4,3)\).
Không thể tạo năm xiên, nên đáp án là \(4\).
Ví dụ 3
Input
5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGWOutput
6Nguồn
JOI 2017/2018, vòng chung kết, bài Dango Maker. Đề do Japanese Committee for the International Olympiad in Informatics công bố. Đề gốc tiếng Anh. Bản dịch tiếng Việt theo CC BY-SA 4.0.
Kỳ thi:
- JOI 2017/2018 - Vòng chung kết (2 Tháng 1., 2018)
Bình luận