Subtask 1

Làm theo yêu cầu đề bài với độ phức tạp \(O(Q \times N)\).

Subtask 2

Ta định nghĩa ô \(0\) là ô bên trái ô thứ \(1\) và ô \(N+1\) là ô ở bên phải ô \(N\).

Hint: Ta chỉ quan tâm có bao nhiêu con robot còn nằm ở đâu đó trừ ô \(0\) và ô \(N+1\) (các ô mà mấy con robot bị biến mất).

Ta có nhận xét như sau:

• Các con robot không bao giờ nhảy vượt quá con robot cạnh trái hoặc cạnh phải nó. Vì vậy nếu một con robot mà trong \(Q\) lần có bị đứng ở ô \(0\) thì tất cả các con robot đứng bên trái con đó chắc chắn sẽ bị đứng ở ô số \(0\) sau \(Q\) lần đẩy. Tương tự với ô \(N+1\),nếu một con robot mà trong \(Q\) lần có bị đứng ở ô \(N+1\) thì tất cả các con robot đứng bên phải con đó chắc chắn sẽ bị đứng ở ô số \(N+1\) sau \(Q\) lần đẩy.

Giải thích cho câu Các con robot không bao giờ nhảy vượt quá con robot cạnh trái hoặc cạnh phải nó: Giả sử ABCD mỗi ô có một con robot, giả sử nếu tất cả các lệnh là L thì con đứng ở ô D sẽ sang ô C, \(2\) con ở ô C sẽ qua B... (tương tự với lệnh R). Chứ không có khả năng con đứng ở ô D nhảy sang ô B mà bỏ qua ô C.

Từ nhận xét trên ta có thể chặt nhị phân kết quả. Cụ thể là chặt tìm con robot ngoài cùng bên phải mà vị trí kết thúc ở ô \(0\) và chặt tìm con robot ngoài cùng bên trái mà vị trí kết thúc ở ô \(N+1\). Độ phức tạp của cách làm này là \(O(QlogN)\)