HDU4662(SummerTrainingDay03-B)

MU Puzzle

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

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

 

代码写得好丑，都要丑哭了T T

U->3I, cnt/2 % 3 == 1 || cnt/2%3 == 2即可。

//2017-08-03
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;
char str[N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", str);
        int cnt = 0;
        bool fg = 1;
        if (str[0] == 'M')
        {
            for (int j = 1; j < strlen(str); j++)
            {
                if (str[j] == 'I')
                    cnt++;
                else if (str[j] == 'U')
                    cnt += 3;
                else if(str[j] == 'M')fg = 0;
            }
        }else{
            printf("No
");
            continue;
        }
        if(fg == 0){
            printf("No
");
            continue;
        }
        if (cnt <= 4)
        {
            if (cnt == 3 || cnt == 0)
                fg = 0;
            else
                fg = 1;
        }
        else
        {
            if (cnt % 2 == 1)
                fg = 0;
            else
            {
                cnt /= 2;
                if (cnt % 3 == 1 || cnt % 3 == 2)
                    fg = 1;
                else
                    fg = 0;
            }
        }
        if (fg)
            printf("Yes
");
        else
            printf("No
");
    }

    return 0;
}