Bedao Mini Contest 24 - Robot
Xem dạng PDF
Robot của ~A~ đang đứng tại ô (~x_s, y_s~) trong một bảng hai chiều rộng vô hạn và bạn được ~A~ cho một dãy chỉ dẫn ~S~ gồm ~n~ lệnh L, R, U, D, I để di chuyển robot đến đích (~x_e, y_e~). Ý nghĩa của các lệnh này như sau:
L: Robot từ ô (~x, y~) di chuyển sang ô (~x - 1, y~);
R: Robot từ ô (~x, y~) di chuyển sang ô (~x + 1, y~);
U: Robot từ ô (~x, y~) di chuyển sang ô (~x, y - 1~);
D: Robot từ ô (~x, y~) di chuyển sang ô (~x, y + 1~);
I: Robot đứng yên tại ô (~x, y~).
Tuy nhiên, dãy chỉ dẫn này có một vài sai số, dẫn đến việc robot có thể không tới được đích. Vì vậy, ~A~ cho bạn được quyền thay đổi một đoạn tối đa ~k~ kí tự liên tiếp để đưa robot đi đến ô đích theo đúng kế hoạch. Nói cách khác, bạn được chọn một đoạn (~l, r~) với ~1 \le l \le r \le n, r - l + 1 \le k~ và gán lại một lệnh bất kỳ cho các chỉ dẫn ~S_l, S_{l + 1}, \dots, S_r~.
Yêu cầu: Hãy cho biết bạn có thể đưa robot đến đích sau khi thực hiện thay đổi trên hay không.
Input
Dòng đầu tiên gồm một số nguyên dương ~t~ (~1 \le t \le 10^4~) là số bộ test. Tiếp theo là ~t~ bộ test có cấu trúc như sau:
Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~ (~1 \le k \le n \le 10^5~).
Dòng thứ hai gồm bốn số nguyên ~x_s, y_s, x_e, y_e~ (~-10^9 \le x_s, y_s, x_e, y_e \le 10^9~).
Dòng thứ ba là dãy ~S~ gồm ~n~ ký tự L, R, U, D, I — tương ứng với việc đi sang trái, sang phải, lên trên, xuống dưới hoặc đứng yên.
Đầu vào đảm bảo ~\Sigma n \le 10^5~.
Output
- Với mỗi bộ test, in ra "YES" nếu có thể đưa robot đến đích sau khi thay đổi chỉ dẫn, ngược lại in ra "NO".
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20\%~ | ~k = 1~ |
| 2 | ~20\%~ | ~\Sigma n \le 10^3~ |
| 3 | ~60\%~ | Không có ràng buộc gì thêm |
Sample Input 1
1
3 1
1 1 2 2
RDL
Sample Output 1
YES
Sample Input 2
1
5 2
0 0 5 0
LLLLL
Sample Output 2
NO
Notes
Ở ví dụ đầu tiên, ta thay đổi ~S_3~ thành "I". Với dãy chỉ dẫn "RDI", robot sẽ đi từ (~1, 1~) đến (~2, 2~).
Ở ví dụ thứ hai, ta không có cách nào để đưa robot từ (~0, 0~) đến (~5, 0~) mà chỉ thay đổi tối đa ~2~ chỉ dẫn.
Bình luận
trash problem
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
hinh nhu editorial bi sai a? chi dung dc 70% test
tao thu meo bi chi het
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.