TAMCAM - Tam Cam
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Năm nào cũng vậy, khi mọi người nô nức rủ nhau đi chơi xuân cũng là lúc mẹ con Cám ngồi bày mưu tính kế để bắt Tấm phải ở nhà. Lần này Cám lấy những hạt thóc và hạt gạo đặt vào các ô của một bảng ô vuông kích thước m×n, mỗi ô đặt tối đa một hạt. Xong đâu đấy Cám gọi Tấm ra yêu cầu phải nhặt ra khỏi bảng một số ít nhất các hạt sao cho trên mỗi hàng cũng như trên mỗi cột của bảng còn lại, số hạt thóc bằng số hạt gạo, khi nào làm xong và đúng mới được đi chơi. Sau một hồi loay hoay không làm được, Tấm òa khóc nức nở, Bụt hiện lên hỏi “Vì sao con khóc?”…
Sau khi nghe Tấm kể lại sự tình, Bụt nói: “lần này mẹ con nó chơi khó thế thì ta cũng đành bó tay thôi, nhưng mà ta còn một cách: con gửi cái bảng này lên trang VNOI.INFO , thế nào cũng có người giúp con”. Nói xong Bụt biến mất.
Câu chuyện tiếp theo như thế nào các bạn làm xong sẽ biết…
Dữ liệu
- Dòng 1 chứa hai số nguyên dương m,n≤100 cách nhau đúng một dấu cách.
- m dòng tiếp theo, dòng thứ i chứa n ký tự liền nhau, ký tự thứ j là “G”, “T”, hoặc “.” (dấu chấm), cho biết ô (i,j) chứa hạt gạo, hạt thóc, hay là ô trống.
Kết quả
- Dòng 1 ghi số hạt ít nhất phải nhặt ra khỏi bảng.
- m dòng tiếp theo, dòng thứ i ghi n ký tự liền nhau, ký tự thứ j là “G”, “T”, hoặc “.” (dấu chấm), cho biết ô (i,j) còn lại hạt gạo, hạt thóc, hay là ô trống.
Chú ý: Các hàng ô của bảng được đánh số từ 1 tới m theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số từ 1 tới n theo thứ tự từ trái qua phải. Ô nằm ở hàng i, cột j của bảng gọi là ô (i,j).
Ví dụ
Dữ liệu 4 5 GT.GG GGTGT TTGTG GTGT. Kết quả 6 .T.G. .GTGT T.GTG G..T.
- Người up: paulmcvn
- Nguồn bài: VNOI Marathon 2009Round 1Problem Setter: Lê Minh Hoàng