시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)94373542.683%

문제

$N$개의 A와 $N$개의 B로 이루어진 문자열 $T$에서 A가 놓인 위치를 $a_1,a_2,\cdots ,a_N$, B가 놓인 위치를 $b_1,b_2,\cdots ,b_N$이라고 하자. 문자열 $T$의 점수 $f(T)$는 같은 문자끼리의 거리의 총합으로 정의되며, $f(T) =\sum_{i=1}^{N}\sum_{j=1}^{N}(|a_i-a_j|+|b_i-b_j|)$으로 계산한다.

A, B, X로 구성된 길이가 $2N$인 문자열 $S$가 주어진다. $S$에는 A와 B가 각각 최대 $N$개 포함되어 있다. 여러분은 X를 A 또는 B로 적절히 바꿔서, A와 B의 개수가 각각 정확히 $N$이 되도록 만들어야 한다.

점수를 최소화하는 문자열과 최대화하는 문자열을 구하라.

입력

첫째 줄에 $N$이 주어진다.

둘째 줄에 $S$가 주어진다.

출력

$N$개의 A와 $N$개의 B로 이루어진 문자열 2개를 한 줄에 하나씩 출력한다.

첫째 줄에 점수를 최소화하는 문자열, 둘째 줄에 점수를 최대화하는 문자열을 출력한다. 이러한 문자열이 여러 개 존재할 경우, 그중 아무거나 출력한다.

제한

  • 주어지는 모든 수는 정수이다.
  • $1\le N\le 3\, 000$
  • $S$는 A, B, X로 이루어진 길이가 $2N$인 문자열로, A와 B는 각각 최대 $N$번 등장한다.

서브태스크

번호배점제한
123

$N \leq 200$

211

$S$에서 X가 최대 10번 등장한다.

328

$S$에서 X가 최대 20번 등장한다.

438

추가 제약 조건 없음.

예제 입력 1

1
BA

예제 출력 1

BA
BA

예제 입력 2

4
AXBXBAXX

예제 출력 2

ABBBBAAA
ABBABABA

출처

Contest > LG Collegiate Programming Contest > LGCPC 2025 본선 B번

채점 및 기타 정보

  • 예제는 채점하지 않는다.