Mirko đã tìm thấy một tấm bảng trên đường, tấm bảng bao gồm $R \times S$ ô (hình vuông đơn vị) được sắp xếp thành $R$ hàng và $S$ cột. Tại thời điểm Mirko tìm thấy tấm bảng, tất cả các ô đều có màu trắng. Mirko quyết định tô màu đen một số ô. Sau khi làm xong, anh ấy gửi tấm bảng cho bạn mình là Slavko cùng với thông điệp sau:
"Slavko thân mến, mình thách cậu tìm ra số lượng hình chữ nhật ít nhất có thể để bao phủ tất cả các ô màu đen. Trong đó, không được có ô màu trắng nào bị bao phủ bởi hình chữ nhật, không được có ô màu đen nào bị bao phủ bởi hai hoặc nhiều hình chữ nhật, và không được có hình chữ nhật nào nằm ngoài phạm vi của tấm bảng."
Như bạn có thể đoán, Slavko không thể vượt qua thử thách này nên đã nhờ bạn giúp đỡ.
Dữ liệu vào
Dòng đầu tiên chứa các số tự nhiên $R$ và $S$ đại diện cho kích thước tấm bảng của Mirko.
Trong mỗi $R$ dòng tiếp theo chứa $S$ ký tự đại diện cho các ô trên tấm bảng của Mirko. Cụ thể hơn, ký tự 'B' biểu thị ô màu trắng và ký tự 'C' biểu thị ô màu đen.
Dữ liệu ra
Trong mỗi $R$ dòng của kết quả, bạn cần in ra $S$ số cách nhau bởi dấu cách đại diện cho lời giải cho thử thách của Mirko.
Các ô được bao phủ bởi hình chữ nhật đầu tiên cần được đánh dấu bằng số 1, các ô được bao phủ bởi hình chữ nhật thứ hai cần được đánh dấu bằng số 2, và cứ tiếp tục như vậy cho đến hình chữ nhật cuối cùng, thứ $N$, với các ô được bao phủ bởi nó được đánh dấu bằng số $N$. Các ô không được bao phủ bởi bất kỳ hình chữ nhật nào, tức là các ô màu trắng, cần được đánh dấu bằng số 0.
Chấm điểm
Các bộ dữ liệu kiểm thử mà lời giải của bạn vi phạm bất kỳ điều kiện nào trong đề bài sẽ được chấm 0 điểm.
Các bộ dữ liệu kiểm thử mà lời giải của bạn bao phủ đúng tất cả các ô màu đen nhưng không sử dụng số lượng hình chữ nhật tối thiểu sẽ được chấm:
$$0.75 \cdot (A / B)^{10} \cdot X$$
điểm, trong đó $A$ là số lượng hình chữ nhật tối ưu, $B$ là số lượng hình chữ nhật trong lời giải của bạn, và $X$ là số điểm của bộ dữ liệu kiểm thử đó.
Tất nhiên, các bộ dữ liệu kiểm thử mà lời giải của bạn bao phủ đúng tất cả các ô màu đen bằng cách sử dụng số lượng hình chữ nhật tối ưu sẽ mang lại cho bạn toàn bộ số điểm dự kiến.
Các giới hạn bổ sung cho các bộ dữ liệu kiểm thử:
- Các bộ dữ liệu từ 1 đến 5: $1 \le R, S \le 26$
- Các bộ dữ liệu từ 6 đến 10: $1 \le R, S \le 100$
- Các bộ dữ liệu từ 11 đến 15: $1 \le R, S \le 250$
- Các bộ dữ liệu từ 16 đến 20: $1 \le R, S \le 500$
Ví dụ
Dữ liệu vào 1
4 5 CCBCB CCBBB CCCBB CCCBB
Dữ liệu ra 1
1 1 0 2 0 1 1 0 0 0 3 3 3 0 0 3 3 3 0 0
Dữ liệu vào 2
7 5 CCCBB BCBBB BCCCB BCCCB CCCCC BBBBB BCCCB
Dữ liệu ra 2
1 1 1 0 0 0 2 0 0 0 0 3 3 3 0 0 3 3 3 0 4 4 4 4 4 0 0 0 0 0 0 5 5 5 0
Dữ liệu vào 3
5 11 BBCCCBCCCBC BCCBCBBCCCC CCCCBCCCCCC BCBCCCBCCCB CCCCBCBBCCB
Dữ liệu ra 3
0 0 1 1 1 0 2 2 2 0 3 0 4 4 0 5 0 0 6 6 6 3 7 7 7 7 0 8 8 6 6 6 3 0 9 0 10 10 10 0 6 6 6 0 11 11 11 11 0 12 0 0 13 13 0