PAT Basic 1003

1. 解题分析

初看题目时本以为看懂了，再看输入输出样例发现一头雾水。回到题干分析判定条件，才明白什么样的输入是符合要求的。然后你会发现这其实就是一个找规律的问题。那么，如何判定“答案正确”呢？分析如下, 表1.1中每一行显示了从已知正确字符串(根据条件1和2)推导出其它正确字符串(根据条件3)的过程。通过观察字符串a、b、c，我们可以发现一个规律len(c)=len(a)*len(b)。到此，问题似乎已经被解决了，但结果可能会背道而驰。所以，请仔细查看推导过程。我们不难发现字符串b的长度恒大于0，也就是说，b为空串的情况是要排除掉的。至此，就可以通过给定的全部测试用例了。

表1.1 推导

条件1, 2	条件3	条件3	条件3	条件3
PAT(a=””,b=”A”,c=””)	PAAT(a=””,b=”AA”,c=””)	PAAAT(a=””,b=”AAA”,c=””)	PAAAAT(a=””,b=”AAAA”,c=””)	…
APATA(a=”A”,b=”A”,c=”A”)	APAATAA(a=”A”,b=”AA”,c=”AA”)	APAAATAAA(a=”A”,b=”AAA”,c=”AAA”)	APAAAATAAAA(a=”A”,b=”AAAA”,c=”AAAA”)	…
AAPATAA(a=”AA”,b=”A”,c=”AA”)	AAPAATAAAA(a=”AA”,b=”AA”,c=”AAAA”)	AAPAAATAAAAAA(a=”AA”,b=”AAA”,c=”AAAAAA”)	AAPAAAATAAAAAAAA(a=”AA”,b=”AAAA”,c=”AAAAAAAA”)	…
…	…	…	…	…

2. 题目原型

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。

得到“答案正确”的条件是：

字符串中必须仅有P、 A、 T这三种字符，不可以包含其它字符；
任意形如xPATx的字符串都可以获得“答案正确”，其中x或者是空字符串，或者是仅由字母A组成的字符串；
如果aPbTc是正确的，那么aPbATca也是正确的，其中a、b、c均或者是空字符串，或者是仅由字母A组成的字符串。

现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式：
每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。

输出格式：
每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。

输入样例：

8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA

输出样例：

YES
YES
YES
YES
NO
NO
NO
NO

3. python code

if __name__ == '__main__':
    n = int(input())
    while n > 0:
        s = input()
        idx_p = s.find('P')
        idx_t = s.find('T')
        a = s[:idx_p]
        b = s[idx_p+1:idx_t]
        c = s[idx_t+1:]
        len_b = len(b)
        if c == a*len_b and a == 'A'*len(a) and len_b > 0 and b == 'A'*len_b:
            print('YES')
        else:
            print('NO')
        n -= 1