2015
09-17

MU Puzzle

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?

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 <= 106.

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 <= 106.

2
MI
MU

Yes
No

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int main()
{
int testcase;
cin>>testcase;
while(testcase--)
{
string p="MI";
int counti=1,countu=0,counti2=0,countu2=0,cm=0,pos=0;
string tar;
cin>>tar;
for(int i=0;i<tar.length();i++)
{

if(tar[i]=='M')
{
cm++;
}

if(tar[i]=='I')
{
counti2++;
}

if(tar[i]=='U')
{
countu2++;
}

}

if( cm==1 && tar[0]=='M'&& (((countu2*3+counti2)%2==0 && (countu2*3+counti2)%3!=0)||(countu2*3+counti2)==1))
{
pos=1;
}
else
{
pos=0;
}

if(pos==0)
{
cout<<"No"<<endl;
}
else if(pos==1)
cout<<"Yes"<<endl;

}

return 0;
}