uva 620 Cellular Structure

A chain of connected cells of two types A and B composes a cellular structure of some microorganisms of species APUDOTDLS.

If no mutation had happened during growth of an organism, its cellular chain would take one of the following forms:

$\bullet$ simple stage O = A $\bullet$ fully-grown stage O = OAB $\bullet$ mutagenic stage O = BOA

Sample notation O = OA means that if we added to chain of a healthy organism a cell A from the right hand side, we would end up also with a chain of a healthy organism. It would grow by one cell A.

A laboratory researches a cluster of these organisms. Your task is to write a program which could find out a current stage of growth and health of an organism, given its cellular chain sequence.

Input
A integer n being a number of cellular chains to test, and then n consecutive lines containing chains of tested organisms.

Output
For each tested chain give (in separate lines) proper answers:

SIMPLE for simple stage FULLY-GROWN for fully-grown stage MUTAGENIC for mutagenic stage MUTANT any other (in case of mutated organisms)

If an organism were in two stages of growth at the same time the first option from the list above should be given as an answer.

Sample Input

4
A
AAB
BAAB
BAABA

Sample Output

SIMPLE
FULLY-GROWN
MUTANT
MUTAGENIC

题目大意：有三种分裂方式：

1）在空的情况下，生成A—>SIMPLE；

2）在不空的情况下，在两边生成B 和 A–>MUTAGENIC;

3）在不空的情况下，在右边生成AB–>FULLY-GROWN;

当三种情况都不满足输出 MUTANT。

题目要求求出最后一种分裂方式。

解题思路：先判断字符串的长度：为1时，输出SIMPLE；为偶数时，输出MUTANT；为奇数时，从后往前遍历，若当前字母为B判断FULLY-GROWN方法，为A时判断MUTAGENIC方法，判断不满足跳出循环输出MUTANT。从后往前遍历到的第一种方法就是酒后一种分裂方式。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#define N 10005
using namespace std;
typedef long long ll;
char s[N];
int main() {
    int T;
    scanf("%d", &T);    
    while (T--) {
        scanf("%s", s);
        int len = strlen(s);
        if (len == 1) {
            printf("SIMPLE\n");
            continue;
        }
        else if (len % 2 == 0) {
            printf("MUTANT\n");
            continue;
        }
        int flag = 1;
        int first = 0, last = len - 1;
        while (first != last) {
            if (s[last] == ‘B‘) {
                if (s[last - 1] != ‘A‘) {
                    flag = 0;
                    break;
                }
                else {
                    if (flag == 1) flag = 2;
                    last -= 2;
                }
            } else if (s[last] == ‘A‘) {
                if (s[first] != ‘B‘) {
                    flag = 0;
                    break;
                }
                else {
                    if (flag == 1) flag = 3;
                    last--;
                    first++;
                }
            }
        }
        if (flag == 1 || flag == 0) printf("MUTANT\n");
        else if (flag == 2) printf("FULLY-GROWN\n");
        else if (flag == 3) printf("MUTAGENIC\n");
    }
    return 0;
}