cho.sh

ABC

A, B, C로 이루어진 길이 N 문자열 중 S[i] < S[j]인 쌍이 정확히 K개인 것 가운데 사전순으로 가장 작은 문자열을 구한다.

보통4그리디조합론구현면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

정수 NN과 KK가 주어질 때, 다음 두 조건을 모두 만족하는 문자열 SS를 찾는 프로그램을 작성하시오.

  • SS의 길이는 NN이고, SS는 A, B, C로만 이루어져 있다.
  • 0≤i<j<N0 \le i < j < N이면서 S[i] < S[j]인 순서쌍 (i,j)(i, j)가 정확히 KK개이다.

문자의 대소는 알파벳 순서를 따른다. 즉 A < B < C이다.

입력

첫째 줄에 NN과 KK가 공백을 사이에 두고 주어진다. (3≤N≤303 \le N \le 30, 0≤K≤N(N−1)/20 \le K \le N(N-1)/2)

출력

조건을 만족하는 문자열 SS 가운데 사전순으로 가장 앞서는 것을 첫째 줄에 출력한다. 조건을 만족하는 SS가 하나도 없으면 -1을 출력한다.