Fruit Game

• 우선 C가 한쪽 끝에 있는 경우를 생각해보자. 반대쪽 끝에 있는 과일이 A라면 애플맨의 패배, B라면 바나나맨의 패배.
• 비슷하게 양쪽 끝에 모두 A가 있으면 애플맨의 패배, 모두 B가 있으면 바나나맨의 패배.
• 그럼 이제 생각할 것은, 한쪽 끝에는 A가 있고 다른쪽 끝에는 B가 있는 경우뿐이다. WLOG, 왼쪽 끝에 A가 있고, 오른쪽 끝에 B가 있다고 하자.
• 왼쪽을 먼저 다 먹으면 애플맨이 이기고, 오른쪽을 먼저 다 먹으면 바나나맨이 이긴다. 따라서 애플맨은 왼쪽을 우선적으로 먹으려고 하고, 바나나맨은 오른쪽을 우선적으로 먹으려고 할것이다.
• 그럼 어느쪽이 진짜로 먼저 없어질것인지를, 양쪽의 과일 갯수와 배치를 세어서 계산하려고 했는데 간단하게 나올줄 알았는데 간단하게 식이 안세워졌다. 잠시 고민했는데, 어차피 두명이 취할 전략은 정해져있으므로 그냥 시뮬레이션을 돌리면 된다는 결론을 냈다. 애플맨은 왼쪽이 A면 그걸 먹고, 왼쪽에는 B가 있고 오른쪽에만 A가 있으면 할수 없이 오른쪽을 먹고, 양쪽다 B면 스킵한다. 바나나맨은 반대로 행동. 이대로 시뮬레이션을 돌려서 어느쪽이 먼저 없어지는지를 확인하면 된다. 시간복잡도는 O(n)

"""Solution code for "BOJ 19406. Fruit Game".

- Problem link: https://www.acmicpc.net/problem/19406
- Solution link: http://www.teferi.net/ps/problems/boj/19406

Tags: [game theory]
"""

import sys


def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        fruits = sys.stdin.readline().rstrip()
        if 'A' not in (fruits[0], fruits[-1]):
            print('Apfelmann')
            continue
        elif 'B' not in (fruits[0], fruits[-1]):
            print('Bananenfrau')
            continue

        left, right = fruits.split('C')
        left, right = list(left), list(reversed(right))
        fruits_a, fruits_b = (left, right) if left[0] == 'A' else (right, left)
        while True:
            if fruits_a[-1] == 'A':
                fruits_a.pop()
                if not fruits_a:
                    print('Apfelmann')
                    break
            elif fruits_b[-1] == 'A':
                fruits_b.pop()

            if fruits_b[-1] == 'B':
                fruits_b.pop()
                if not fruits_b:
                    print('Bananenfrau')
                    break
            elif fruits_a[-1] == 'B':
                fruits_a.pop()


if __name__ == '__main__':
    main()