Upin and Ipin
Xem dạng PDF
Upin và Ipin là hai anh em sinh đôi. Hai cậu rất thân thiết và thường chơi cùng nhau trong những lúc không phải học bài. Hôm nay, họ cùng nhau chơi một trò chơi để thi xem ai có khả năng ghi nhớ tốt hơn. Hai bạn tạo ra một xâu kí tự ~s~ chỉ bao gồm các kí tự U và I. Hai bạn cần chọn ra một xâu con~^*~ ~t~ của ~s~, sao cho ~t~ có chứa ít nhất một kí tự U và ít nhất một kí tự I, và tiến hành chơi trò chơi trên xâu ~t~.
Theo sở trường của mình, Upin có thế mạnh ghi nhớ các kí tự U và Ipin có thể mạnh ghi nhớ các kí tự I. Nếu như gọi ~cnt_\texttt{U}~ và ~cnt_\texttt{I}~ lần lượt là số lượng kí tự U và I trong xâu con ~t~, vậy thì kết của của lượt chơi sẽ được quyết định như sau:
nếu ~cnt_\texttt{U} \geq 2 \cdot cnt_\texttt{I}~, Upin sẽ dành chiến thắng,
nếu ~cnt_\texttt{I} \geq 2 \cdot cnt_\texttt{U}~, Ipin sẽ dành chiến thắng,
nếu như không ai chiến thắng, kết quả của lượt chơi là hòa.
Upin và Ipin giao nhiệm vụ trọng tài cho người bạn tốt của mình là Tpin. Tpin cần phải chọn ra xâu con ~t~. Để cuộc chơi có tính quyết định, Tpin cần phải đảm bảo rằng kết của của cuộc chơi không hòa.
Hãy giúp Tpin tìm ra xâu con ~t~ của xâu ~s~ cho trước thỏa mãn, hoặc chỉ ra rằng mọi cách chọn xâu ~t~ đểu cho ra kết quả hòa. Nếu có nhiều cách chọn xâu ~t~, hãy tìm ra cách chọn bất kì.
————————————————————————
~^*~ Xâu ~t~ được gọi là xâu con của ~s~ nếu như ~t~ có thể được tạo thành bằng cách xóa đi (không hoặc nhiều) ký tự ở đầu ~s~, và xóa đi (không hoặc nhiều) ký tự ở cuối ~s~.
Input
Dòng đầu tiên chứa một số nguyên ~q~ (~1 \leq q \leq 10\,000~) — số lượt chơi. Mô tả dữ liệu của mỗi lượt chơi như sau.
Dòng đầu tiên và duy nhất của mỗi lượt chơi chứa một xâu ~s~ (~|s| \le 10^5~) chỉ gồm các kí tự I và U – mô tả xâu được Upin và Ipin lựa chọn cho lượt chơi thứ ~i~.
Dữ liệu đảm bảo tổng độ dài của các xâu ~s~ trong tất cả các lượt chơi không vượt quá ~10^5~.
Output
Đối với mỗi vòng chơi, in ra NO nếu tất cả các chuỗi con ~t~ dẫn đến hòa.
Nếu không, in ra YES và hai số nguyên ~l, r~ ~(1 \leq l \leq r \leq |S|)~ mô tả cách chọn ~t = s_l s_{l + 1} s_{l + 2} \ldots s_r~.
Nếu có nhiều cách chọn, in ra bất kì cách chọn hợp lệ nào.
Bạn có thể xuất câu trả lời ở bất kỳ kiểu chữ nào (chữ hoa hoặc chữ thường). Ví dụ, các chuỗi "yEs", "yes", "Yes", và "YES" sẽ được công nhận là đúng.
Scoring
Tổng điểm cho bài này là ~500~.
Sample Input 1
4
UUUIIIUIIUI
UU
IUUIIUUI
IU
Sample Output 1
Yes 3 11
No
Yes 2 7
No
Notes
Trong lượt chơi đầu tiên, Tpin chọn xâu con ~t~ = "UIIIUIIUI" có ~cnt_\texttt{I} = 6~ và ~cnt_\texttt{U} = 3~. Ipin sẽ dành chiến thắng do điều kiện ~cnt_\texttt{I} \geq 2 \cdot cnt_\texttt{U}~ thỏa mãn.
Trong lượt chơi thứ hai, Tpin không thể tìm được xâu con ~t~ thỏa mãn.
Trong lượt chơi thứ ba, Tpin chọn xâu con ~t~ = "UUIIUU" có ~cnt_\texttt{I} = 2~ và ~cnt_\texttt{U} = 4~. Upin sẽ dành chiến thắng do điều kiện ~cnt_\texttt{U} \geq 2 \cdot cnt_\texttt{I}~ thỏa mãn.
Trong lượt chơi thứ tư, Tpin không thể tìm được xâu con ~t~ thỏa mãn.
Bình luận
1+1=2
Ai dùng prefix bài này upvote comment này !!
Upin và Ipin?