Upin and Ipin
View as PDF
Upin and Ipin are two twin brothers. They are very close and often play together when they are not studying. Today, they are playing a game to see who has a better memory. They create a string ~s~ consisting only of the characters U and I. They need to choose a substring~^*~ ~t~ of ~s~, such that ~t~ contains at least one character U and at least one character I, and proceed to play the game on string ~t~.
According to their strengths, Upin has an advantage in remembering the characters U and Ipin has an advantage in remembering the characters I. If we denote ~cnt_\texttt{U}~ and ~cnt_\texttt{I}~ as the number of characters U and I in the substring ~t~, then the result of the game will be determined as follows:
if ~cnt_\texttt{U} \geq 2 \cdot cnt_\texttt{I}~, Upin will win,
if ~cnt_\texttt{I} \geq 2 \cdot cnt_\texttt{U}~, Ipin will win,
if neither wins, the result of the game is a draw.
Upin and Ipin have entrusted their friend Tpin with the task of being the referee. Tpin needs to choose the substring ~t~. To make the game decisive, Tpin must ensure that the result of the game is not a draw.
Help Tpin find a substring ~t~ of the given string ~s~ that satisfies this condition, or indicate that every way of choosing the substring ~t~ results in a draw. If there are multiple ways to choose the substring ~t~, find any valid way.
————————————————————————
~^*~ A string ~t~ is called a substring of ~s~ if ~t~ can be formed by deleting (zero or more) characters from the beginning of ~s~, and deleting (zero or more) characters from the end of ~s~.
Input
The first line contains an integer ~q~ (~1 \leq q \leq 10\,000~) — the number of games. The data for each game is described as follows.
The first and only line of each game contains a string ~s~ (~|s| \le 10^5~) consisting only of the characters I and U – describing the string chosen by Upin and Ipin for the ~i~-th game.
The data guarantees that the total length of all strings ~s~ in all games does not exceed ~10^5~.
Output
For each game round, print NO if all substrings ~t~ result in a draw.
Otherwise, print YES and two integers ~l, r~ ~(1 \leq l \leq r \leq |S|)~ describing how to choose ~t = s_l s_{l + 1} s_{l + 2} \ldots s_r~.
If there are multiple ways to choose, print any valid choice.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
Scoring
The total score for this problem is ~500~.
Sample Input 1
4
UUUIIIUIIUI
UU
IUUIIUUI
IU
Sample Output 1
Yes 3 11
No
Yes 2 7
No
Notes
In the first game, Tpin chooses the substring ~t~ = "UIIIUIIUI" with ~cnt_\texttt{I} = 6~ and ~cnt_\texttt{U} = 3~. Ipin will win because the condition ~cnt_\texttt{I} \geq 2 \cdot cnt_\texttt{U}~ is satisfied.
In the second game, Tpin cannot find a valid substring ~t~.
In the third game, Tpin chooses the substring ~t~ = "UUIIUU" with ~cnt_\texttt{I} = 2~ and ~cnt_\texttt{U} = 4~. Upin will win because the condition ~cnt_\texttt{U} \geq 2 \cdot cnt_\texttt{I}~ is satisfied.
In the fourth game, Tpin cannot find a valid substring ~t~.
Comments
1+1=2
Ai dùng prefix bài này upvote comment này !!
Upin và Ipin?