Sơn hàng rào
Đề bài
Mô tả
Một hàng rào gồm tấm ván xếp theo thứ tự từ đến . Tấm ván thứ đang có màu , và bạn muốn nó có màu .
Bạn đã thuê thợ sơn. Thợ thứ đến vào thời điểm (nghĩa là các thợ làm việc lần lượt theo thứ tự ) và sẽ sơn lại đúng một tấm ván bằng màu . Với mỗi thợ bạn được chọn tấm ván mà thợ đó sơn, nhưng không được từ chối thợ nào: mỗi thợ bắt buộc phải sơn đúng một tấm ván. Nhiều thợ có thể cùng sơn một tấm ván, khi đó màu cuối cùng của tấm ván là màu của thợ đến sau cùng trong số đó.
Hãy xác định xem có thể thu được hàng rào với màu mong muốn hay không. Nếu có, hãy chỉ ra tấm ván mà mỗi thợ phải sơn.
Dữ liệu vào
- Dòng đầu tiên chứa một số nguyên là số bộ dữ liệu.
- Mỗi bộ dữ liệu gồm bốn dòng:
- Dòng thứ nhất chứa hai số nguyên và : số tấm ván và số thợ sơn.
- Dòng thứ hai chứa số nguyên : màu ban đầu của các tấm ván.
- Dòng thứ ba chứa số nguyên : màu mong muốn của các tấm ván.
- Dòng thứ tư chứa số nguyên : màu sơn mà các thợ mang theo.
Dữ liệu ra
Với mỗi bộ dữ liệu:
- In ra NO nếu không thể thu được cách tô màu .
- Ngược lại, in ra YES trên một dòng, rồi in ra số nguyên trên dòng tiếp theo, trong đó là chỉ số tấm ván mà thợ thứ phải sơn.
Nếu có nhiều đáp án, in ra một đáp án bất kỳ. Chữ hoa hay chữ thường của YES / NO đều được chấp nhận.
Ràng buộc
- Tổng trên tất cả các bộ dữ liệu không vượt quá , và tổng cũng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 1 1 1 1 3 4 1 1 1 2 1 1 3 3 3 2 3 4 1 1 1 2 1 1 2 3 3 3 |
YES 1 YES 1 1 1 1 NO |
Bộ 1: tấm ván duy nhất đã đúng màu, thợ duy nhất sơn lại nó bằng chính màu đó nên không làm hỏng gì. Bộ 2: ba thợ đầu mang màu vô dụng, nhưng họ cùng sơn lên tấm ván vì thợ cuối sẽ phủ màu lên đó. Bộ 3: cùng tập màu nhưng thợ cuối mang màu , mà không có trong ; tấm ván anh ta sơn sẽ giữ màu đến cuối nên chắc chắn sai. |
| 2 10 5 7 3 2 1 7 9 4 2 7 9 9 9 2 1 4 9 4 2 3 9 9 9 7 4 3 6 4 3 4 2 4 1 2 2 3 1 3 1 1 2 2 3 4 |
YES 1 2 5 5 9 NO |
Bộ 1: bốn tấm ván đang sai màu và được đúng bốn thợ sửa; thợ mang màu không cần đến nên sơn tạm lên tấm ván , sau đó thợ phủ màu lên. Nhiều đáp án khác cũng hợp lệ. Bộ 2: không đủ thợ mang màu cần thiết nên không thể đạt được . |
Bình luận