Bedao Mini Contest 24 - Robot
View as 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.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
hinh nhu editorial bi sai a? chi dung dc 70% test
tao thu meo bi chi het
This comment is hidden due to too much negative feedback. Show it anyway.