우리는 영문 대문자로 이루어진 문자열을 만들고 싶다. 하지만 문자열의 문자들이 항상 오름차순으로만 증가하는 것이 아니라, 어떤 구간에서는 엄격히 증가하고 어떤 구간에서는 엄격히 감소하도록 만들고 싶다.

문자열의 첫 글자는 반드시 A여야 한다. 그 다음에는 하나 이상의 블록(block)으로 이루어져야 한다. i번째 블록은 정확히 \mathbf{L_i}개의 문자를 포함해야 한다. i가 홀수인 블록에서는, 그 블록의 각 문자는 문자열에서 바로 앞선 문자보다 알파벳 순서로 뒤에 와야 한다. 반대로 i가 짝수인 블록에서는, 그 블록의 각 문자는 문자열에서 바로 앞선 문자보다 알파벳 순서로 앞에 와야 한다. 블록의 첫 글자도 "바로 앞선 문자"가 존재한다는 점에 유의하라(그 문자는 블록 밖에 있을 수도 있다). 이 모든 규칙을 만족하는 문자열을 유효(valid)하다고 한다. 유효한 문자열은 여러 개일 수 있으며, 그중 사전순(알파벳 순)으로 가장 앞서는 문자열을 찾고자 한다.

예를 들어 블록이 2개이고 크기가 \mathbf{L_1}=2, \mathbf{L_2}=3이라면, 문자열은 총 1+\mathbf{L_1}+\mathbf{L_2}=1+2+3=6글자여야 한다(1은 처음의 A를 위한 것이다). XYZYBA, AZYCBA, AYZYBB는 각각 시작 글자 조건, 첫 번째 블록의 정렬 조건, 두 번째 블록의 정렬 조건을 위반하므로 유효하지 않다. AYZYBA는 유효하다. 또한 ABDCBA 역시 유효하며, 게다가 유효한 문자열들 중 사전순으로 가장 앞서는 문자열이다.

각 블록의 크기가 주어질 때, 모든 유효한 문자열 중 사전순으로 가장 앞서는 유효한 문자열을 출력하라. 주어진 제한 내의 모든 입력에 대해, 유효한 문자열이 적어도 하나는 존재함을 보일 수 있다.

#10387 upload 1 done 1 how_to_reg 1

변덕스러운 정렬 timer 10s memory 1024MB

#10387

변덕스러운 정렬 10s 1024MB