"Correct answer" is the most gratifying reply given by the automatic question judgment system. This question belongs to PAT's "correct answer" distribution - as long as the read string meets the following conditions, the system will output "correct answer", otherwise it will output "wrong answer".
The conditions for getting "correct answer" are:
- The string must contain only three characters: P, A and T, and cannot contain other characters;
- Any string shaped like xPATx can get "correct answer", where x is either an empty string or A string composed of only the letter A;
- If aPbTc is correct, aPbATca is also correct, where a, b and c are either empty strings or strings composed of only the letter A.
Now please write an automatic referee program for PAT to determine which strings can get the "correct answer".
Each test input contains 1 test case. The first line gives a positive integer n (≤ 10), which is the number of strings to be detected. Next, each string occupies one line. The length of the string does not exceed 100 and does not contain spaces.
The detection result of each string occupies one line. If the string can obtain "correct answer", output YES, otherwise output NO.
10 PAT PAAT AAPATAA AAPAATAAAA xPATx PT Whatever APAAATAA APT APATTAA
YES YES YES YES NO NO NO NO NO NO
[input] first use int(input()) to receive the value of N, and then use the for loop to complete the input and verification process n times
[inspection] the inspection standard is divided into two sub conditions:
① The string contains three characters P, A and T, and there are no other characters
Starting from the first character element of the string, check whether the quantity (unique) and order (P before t) of P and T are legal; After considering P and T, check whether other characters are non-a. if there are non-A elements, the program can jump out and return false.
Here, we should also consider the requirement that the string length is > 2: there are 1 P and 1 T, and the condition that P is before t is not enough. At least one character a must be stored (the position and quantity of a are not considered temporarily, and can be checked in condition ②).
Then define the function only_one_PT(), the incoming parameter is the string to be verified, and the return value is * * (true / false, position of P, position of T) * *.
def only_one_PT(input_str): char_P,char_T,loc_P,loc_T,t = 0,0,0,0,-1 # char_P,char_T is used to record the number of occurrences of P and t # loc_P,loc_T is used to record the position where P and t appear # t for loop count for i in input_str: t = t + 1 if i == 'P': char_P += 1 loc_P = t continue if i == 'T': if char_P == 0: return(False,0,0) char_T += 1 loc_T = t continue if i != 'A': return(False,0,0) if char_P * char_T == 1 and len(input_str) > 2: return (True,loc_P,loc_T) else: return(False,0,0)
② Number of left A * number of middle A = number of right A, and there is at least one A between P and T
Sort out and summarize the second and third articles of the title stem:
Condition 2: xPATx satisfies the condition when x is an empty string or a string consisting only of the letter A
Explanation: when there is only one A between P and T, the left side of P and the right side of t must be exactly equal
Condition 3: when aPbTc meets the condition, aPbATca also meets the condition. A, B and C are empty strings or strings only composed of letter A
Explanation: according to the first and second conditions, there must be an A between P and T,
And when b is an A: aPATc, at this time, c is equal to a
So aPATc can be seen as aPATa
When b is two A's: from the third condition, aPAATaa also satisfies the condition. At this time, c is equal to two a's
When b is three A's: aPAAATaaa, then c equals three a's
In this way, it can be concluded that:
A1*A2 = A3
A1 represents the number of a on the left of P, A2 represents the number of a in the middle, and A3 represents the number of a on the right of T
def only_one_PT(input_str): char_P,char_T,loc_P,loc_T,t = 0,0,0,0,-1 # char_P,char_T is used to record the number of occurrences of P and t # loc_P,loc_T is used to record the position where P and t appear # t for loop count for i in input_str: t = t + 1 if i == 'P': char_P += 1 loc_P = t continue if i == 'T': if char_P == 0: return(False,0,0) char_T += 1 loc_T = t continue if i != 'A': return(False,0,0) if char_P * char_T == 1 and len(input_str) > 2: return (True,loc_P,loc_T) else: return(False,0,0) n = int(input()) a_res =  # Use the list to save the results of each inspection for i in range(0,n): in_str = input() res = only_one_PT(in_str) if res: if(res * (res - res -1) == len(in_str) - res -1) and (res - res != 1): a_res.append('YES') else: a_res.append('NO') else: a_res.append('NO') for i in a_res: print(i)
Refer to: https://zhuanlan.zhihu.com/p/46465425