Towers of coins

• DP를 이용해서 푸는 가장 기본적인 게임이론 문제
• DP로 구할때의 시간복잡도는 O(n*m) (n:포지션의 갯수, m:행동의 갯수) 가 되는데, 포지션은 1,000,000 개, 가능한 행동은 3가지이므로 충분히 시간내에 구할수 있다.
• DP식이 최대 이전 10개 항에 의존하므로, dp테이블은 2^10 크기 이내의 사이클이 존재하게 된다. 사이클을 찾아서 그것을 이용해서 계산하게 되면 시간복잡도를 더 줄일수도 있겠지만 구현 난이도가 너무 높아지므로 생략.
  • 이렇게 풀어야 하는 문제가 9662 이다.

"""Solution code for "BOJ 3358. Towers of coins".

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

Tags: [Game theory]
"""


def main():
    # pylint: disable=unused-variable
    K, L, m = [int(x) for x in input().split()]
    N = [int(x) for x in input().split()]

    max_n = max(N)
    is_win_pos = [False] * (max_n + L + 1)
    for i in range(max_n + 1):
        if not is_win_pos[i]:
            is_win_pos[i + 1] = is_win_pos[i + K] = is_win_pos[i + L] = True

    print(''.join('A' if is_win_pos[x] else 'B' for x in N))


if __name__ == '__main__':
    main()