시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 49 | 3 | 3 | 50.000% |
민승이는 정문이에게 미션을 주면서 즐기고 있다. 정문이는 눈에 헤드밴드를 썼기 때문에 앞을 볼 수 없다.
미션은 1부터 N까지 번호가 붙어진 N개의 컵으로 진행된다. 처음에 민승이는 이 N개의 컵 중 한 컵에 공을 넣는다. (당연히 정문이는 어디에 넣은지 알 수 없다) 그 다음부터 정문이는 매 단계마다 'A' 또는 'B' 문자를 부르고 이에 따라 민승이는 공을 꺼내서 다른 컵으로 넣는다. (꺼내서 다시 동일한 컵에 넣을 수도 있다.) 단 민승이가 공을 꺼내서 넣는 컵은 현재 컵의 위치와 정문이가 부른 알파벳에 의해서만 결정된다.
만약에 현재 공이 K번째 컵에 있다면 이 컵은 정문이가 부른 알파벳에 의해서 Ak(정문이가 'A'를 불렀을 경우) 또는 Bk(정문이가 'B'를 불렀을 경우)번째 컵으로 이동하게 된다.
정문이의 미션은 처음에 민승이가 공을 어떤 컵에 넣든지간에 최종적으로 이 공이 컵 1로 들어가게 하는 것이다. 우리는 이런 정문이를 도와 공이 컵 1로 들어가기 위해 정문이가 불러야할 알파벳 문자열을 찾는것이다. 단, 이 문자열은 10,000보다 작아야 한다.
첫 번째 줄에 컵의 개수 N (1 ≤ N ≤ 500)이 주어진다. 그 다음 N개의 줄에는 한 컵에 대한 Ak와 Bk가 공백으로 구분되어 주어진다. (두 번째 줄에 A1과 B1, 다음 줄에 A2와 B2 등이 주어진다는 뜻이다)
정문이가 불러야할 A또는 B로 구성된 문자열을 출력한다. (여러 해가 존재할 경우에는 그 중 하나만 출력되면 되고 항상 답이 존재하는 입력만 주어진다고 하자.) 문자열의 길이는 10,000보다 작거나 같아야 한다.
4 1 2 1 3 3 1 1 4
ABA
10 4 9 5 3 1 8 6 1 3 8 9 1 10 1 6 3 2 3 8 1
BABAABAB