시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB57211948.718%

문제

민겸이는 연금술을 배우는 견습 연금술사이다. 졸업 시험을 앞둔 민겸이는 $N$개의 a와 $M$개의 b를 전부 이용하여 가장 가치가 높은 문자열을 만들고 싶다. 문자열의 가치는 다음과 같이 측정한다.

  1. 어떤 문자열에 대해서 $k = 1, 2, 3, \cdots$에 대해 2를 반복한다.
  2. 해당 문자열에서 거리가 $k$인 동일한 종류의 문자 쌍이 존재할 경우 가치가 $k$만큼 증가한다. 이때, 거리가 $k$인 문자 쌍이 여러 개여도 가치는 $k$만큼만 증가한다.
  3. $i$번째 문자와 $j$번째 문자 사이의 거리는 $|i-j|$이다. 예를 들어, 문자열 abba에서 두 a 사이의 거리는 $3$이고, 두 b 사이의 거리는 $1$이다.

가치가 $8$인 문자열 aabba를 예로 들어 보자.

  1. $k = 1$일 때 $(1, 2)$, $(3, 4)$ 등의 문자 쌍이 있으므로 가치가 $1$ 증가한다.
  2. $k = 2$일 때는 거리가 $2$인 문자 쌍이 없으므로 가치를 증가시킬 수 없다.
  3. $k = 3$일 때 $(2, 5)$ 등의 문자 쌍이 있으므로 가치가 $3$ 증가한다.
  4. $k = 4$일 때 $(1, 5)$ 등의 문자 쌍이 있으므로 가치가 $4$ 증가한다.
  5. $k \ge 5$일 때는 거리가 $k$인 문자 쌍이 없으므로 가치를 증가시킬 수 없다.
  6. 총 가치는 $1 + 3 + 4 = 8$이다.

$N$개의 a와 $M$개의 b를 전부 이용하여 만들 수 있는 문자열의 최대 가치를 구하고, 해당 가치를 가지는 문자열을 하나 출력하는 프로그램을 작성하여라.

입력

입력의 첫 번째 줄에 a의 개수 $N$과 b의 개수 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 10\,000;$ $1 \le M \le 10\,000)$

출력

첫 번째 줄에 주어진 알파벳 소문자들로 만들 수 있는 최대 가치를 출력한다.

두 번째 줄에 해당 가치를 가지는 문자열을 출력한다. 답이 여러 개라면, 하나만 출력한다.

예제 입력 1

3 2

예제 출력 1

8
aabba

예제 입력 2

3 3

예제 출력 2

12
baaabb

예제 입력 3

2 4

예제 출력 3

15
bbabab

출처

University > 경인지역 6개대학 연합 > shake! 2022 F번