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 6.
Output
n lines, each line is 'Yes' or 'No'.
Sample Input
2 MI MU
Sample Output
Yes No
Source
代码写得好丑，都要丑哭了T T
U->3I, cnt/2 % 3 == 1 || cnt/2%3 == 2即可。
//2017-08-03#include#include #include #include 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\n"); continue; } if(fg == 0){ printf("No\n"); 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\n"); else printf("No\n"); } return 0;}