Có 9 căn phòng (đánh số từ 1 đến 9) đã được quét vôi với màu trắng, xanh, vàng.Có 9 robot (đánh số từ 1 đến 9 ) phụ trách việc quét vôi các phòng. Mỗi robot chỉ quét vôi một số phòng nhất định. Việc quét vôi được thực hiện nhờ 1 chương trình cài sẵn theo quy tắc:
- Nếu phòng đang có màu trắng thì quét màu xanh
- Nếu phòng đang có màu xanh thì quét mau vàng
- Nếu phòng đang có màu vàng thì quét màu trắng;.
Cần phải gọi lần lượt một số các robot ra quét vôi (mỗi lần 1 robot, một robot có thể gọi nhiều lần và có thể có robot không được gọi. Robot đc gọi sẽ quét vôi tất cả các phòng mà nó phụ trách) để cuối cùng tất cả các phòng đều có màu trắng.Hãy tìm ra phương án như vậy sao cho lượng vôi phải quét là ít nhất. Giả thiết rằng lượng vôi cho mỗi lượt quét đối với các phòng là như nhau.
DỮ LIỆU : đọc từ file văn bản ROBOT.INP gồm các dòng :
- 9 dòng đầu, mỗi dòng mô tả danh sách các phòng đc quét vôi bởi 1 robot theo thứ tự từ robot 1 đến robot 9. Mỗi dòng như vậy gồm các số hiệu phòng viết sát nhau. Chẳng hạn dòng thứ 3 có nội dung 2356 mô tả robot 3 phụ trách việc quét vôi các phòng 2,3,5,6.
- Dòng cuối mô tả màu vôi ban đầu của các phòng. Dòng này gồm 9 kí tự viết sát nhau, ký tự thứ i biểu diễn màu vôi của phòng i với quy ước: kí tự T chỉ màu trắng, ký tự X chỉ màu xanh, ký tự V chỉ màu vàng.
KẾT QUẢ : đưa ra file văn bản ROBOT.OUT gồm 2 dòng dưới dạng:
- Nếu không có phương án thì ghi lại một chữ số 0
- Trái lại , ghi dãy thứ tự các robot đc gọi ( các số hiệu robot viết sát nhau).
VD:
ROBOT.INP ROBOT.OUT
41
1245 11224455699
123
2356
147
13579
369
4578
789
5689
XVXVTTVXX