17237번 - Conquering A Castle

문제

A와 B 두 사람이 성 함락시키기 게임을 하고 있다. 이 게임은 턴제 게임으로 A와 B가 번갈아서 한 턴씩 진행한다. 게임은 A의 턴으로 시작된다. 규칙은 다음과 같다.

A는 군사를 가지고 성을 함락시키는 것을 목표로 하며, B는 대포를 사용해 성을 지키는 것을 목표로 한다. A에게는 n명의 군사가 있는데, 각 군사 i 는 (1 ≤ i ≤ n) 성으로부터 d_i m 떨어져 있다. 성으로 들어가는 길은 두 개가 있으며, A는 자신의 턴에 각 군사를 두 길 중 한 곳에 배치하거나 배치하지 않을 수 있다. 길에 배치되어 있는 병사는 다른 길에 배치하거나 회수할 수도 있다. 이때 군사를 두 길 중 어디에 배치할지는 A가 자유롭게 결정할 수 있으나, 성으로부터의 거리 d_i는 바꿀 수 없다. 적어도 하나의 군사는 길에 배치되어야 한다.

B는 자신의 턴에 두 개의 길 중 한 곳에 대포를 쏠 수 있다. B가 대포를 쏘면, 그 길에 있는 군사는 거리에 무관하게 모두 죽는다. B가 대포를 쏘고 살아남은 A의 군사들은 모두 1m 씩 성으로 전진한다. 만약 한 명의 군사라도 성에 도달한다면, 게임은 A의 승리로 끝나며, B가 대포를 사용해 A의 모든 군사를 죽인다면 게임은 B의 승리로 끝난다.

A와 B 모두 최적의 선택을 한다고 가정할 때, 주어진 초기 병사들의 위치 d_i 를가지고 누가 게임에서 승리할지 판단하라.

입력

첫 줄에는 군사들의 수 n 이 주어진다. (1 ≤ n ≤ 1,000)

두 번째 줄부터 n + 1 번째 줄에는 매 줄마다 정수 d_i, 즉 i 번째 군사가 성으로부터 떨어진 거리가 미터 단위로 주어진다.(1 ≤ d_i ≤ 20)

출력

A와 B 모두 최적의 선택을 한다고 가정할 때, A가 게임에서 승리한다면 “A”를, B가 승리한다면 “B”를 출력하라.

제한

힌트