MU Puzzle
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 134 Accepted Submission(s): 71
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?
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'.
Following n lines, each line contains a nonempty string which consists only of letters 'M', 'I' and 'U'.
Total length of all strings <= 106.
Output
n lines, each line is 'Yes' or 'No'.
Sample Input
2
MI
MU
MI
MU
Sample Output
Yes
No
No
Source
Recommend
zhuyuanchen520
全场最水的题目。
一开始时MI。
其实可以全部转化成I的个数。
一个U相当于3个I，减少两个U，相当于减少6个I。
第一个操作相当于可以把I的个数翻倍。
所以1个I，2个I，4个I，8,16,32，。。。。这些2^n个I都是可以实现的。
而且可以减掉6个I，8-6=2,16-6=10,10-6=4，等等都可以。
10个I可以，20个I也可以。
这样数I的个数，比赛时候暴力预处理下所以可以的情况，就像晒素数一样。
其实可以发现规律的，除了一个I之外，奇数个I和个数被6整除的都不行，可以根据整除性分析下。
贴上代码，里面有一个init函数式预处理的，虽然没有用上
/*
* Author: kuangbin
* Created Time: 2013/8/8 11:54:08
* File Name: 1008.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
using namespace std;
char str[];
const int MAXN = ;
bool dp[MAXN];
bool vis[MAXN];
void init()
{
memset(dp,false,sizeof(dp));
memset(vis,false,sizeof(vis));
dp[] = true;
queue<int>q;
q.push();
vis[] = true;
while(!q.empty())
{
int tmp = q.front();
dp[tmp] = true;
q.pop();
if(tmp == ){dp[] = true;vis[] = true;continue;}
if(tmp >= && !vis[tmp-])
{
q.push(tmp-);
vis[tmp-] = true;
}
tmp *= ;
while(tmp < MAXN)
{
if(vis[tmp])break;
dp[tmp] = true;
if(tmp >= && !vis[tmp-])
{
q.push(tmp-);
vis[tmp-] = true;
}
tmp *= ;
}
}
} int main()
{
int T;
init();
scanf("%d",&T);
while(T--)
{
bool flag = true;
scanf("%s",str);
int len = strlen(str);
if(str[]!='M')
{
printf("No\n");
continue;
}
int cnt = ;
for(int i = ;i < len;i++)
{
if(str[i]=='M')
{
flag = false;
break;
}
if(str[i] =='I')cnt++;
else cnt+= ;
}
if(!flag)
{
printf("No\n");
continue;
}
if(cnt == )
{
printf("Yes\n");
continue;
}
if(cnt% == || cnt% == )printf("No\n");
else printf("Yes\n");
}
return ;
}