시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 25 10 9 42.857%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

2
1
1

예제 출력 1

A

예제 입력 2

3
1
2
3

예제 출력 2

B

출처

University > POSTECH > 2019 PPC D번

  • 빠진 조건을 찾은 사람: jh05013
  • 문제를 만든 사람: ufolion