MU Puzzle

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1296 Accepted Submission(s): 539


Problem Description Suppose there are the symbols M, I, and U which can be combined to produce strings of symbols called words. We start with one word MI, and transform it to get a new word. In each step, we can use one of the following transformation rules:
1. Double any string after the M (that is, change Mx, to Mxx). For example: MIU to MIUIU.
2. Replace any III with a U. For example: MUIIIU to MUUU.
3. Remove any UU. For example: MUUU to MU.
Using these three rules is it possible to change MI into a given string in a finite number of steps?

Input First line, number of strings, n.
Following n lines, each line contains a nonempty string which consists only of letters 'M', 'I' and 'U'.

Total length of all strings <= 10⁶.
Output n lines, each line is 'Yes' or 'No'.
Sample Input

2
MI
MU

Sample Output

Yes
No

Source 2013 Multi-University Training Contest 6
Recommend zhuyuanchen520 | We have carefully selected several similar problems for you: 4822 4821 4820 4819 4818
規律題，把u全部化成i，然後多寫下，就能發現規律

 

 

#include
#include
using namespace std;
char str[1000010];
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		cin>>str;
		int l=strlen(str),xi=0,xu=0,k=0;
		if(str[0]!='M')
		{
			cout<