만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

고유 부분 문자열

시간 제한1초메모리 제한256 MB

요약
길이가 4096 이하인 소문자 문자열을 만들어 서로 다른 부분 문자열이 정확히 K개가 되도록 하는 문제입니다.
난이도

보통10점 중 6점

유형
문자열, 그리디, 구현
정답자
아직 제출이 없습니다

문제

소문자 알파벳으로 이루어진 길이 NN의 문자열 S1S2…SNS_1S_2 \ldots S_N을 만드시오. 단, 1≤N≤2121 \le N \le 2^{12}이다. 이 문자열은 서로 다른 부분 문자열을 정확히 KK개 가져야 한다.

부분 문자열은 어떤 1≤L≤R≤N1 \le L \le R \le N에 대해 SLSL+1…SR−1SRS_L S_{L+1} \ldots S_{R-1} S_R 형태의 연속된 글자열이다. 글자의 순서가 같으면 같은 부분 문자열로 본다.

입력

첫 줄에 정수 KK가 주어진다 (1≤K≤2221 \le K \le 2^{22}). NN은 주어지지 않는다. 만드는 문자열의 길이 NN은 1≤N≤2121 \le N \le 2^{12}을 만족하면 된다.

출력

1≤N≤2121 \le N \le 2^{12}을 만족하는 소문자 문자열 한 개를 한 줄에 출력한다. 이 문자열은 서로 다른 부분 문자열을 정확히 KK개 가져야 한다. 조건을 만족하는 문자열이 여러 개면 어느 것이든 허용된다. 주어진 제약 안에서는 그런 문자열이 항상 존재함이 증명되어 있다.

힌트

첫 번째 예제에서 banana의 서로 다른 부분 문자열은 a, an, ana, anan, anana, b, ba, ban, bana, banan, banana, n, na, nan, nana로 15개이다. 부분 문자열이 15개인 다른 문자열로 aaaaaaaaaaaaaaa도 있으며, 이것 역시 첫 번째 예제의 올바른 출력이다.

예제2

  1. 예제 1

    입력
    15
    
    예상 출력
    banana
    
  2. 예제 2

    입력
    351
    
    예상 출력
    abcdefghijklmnopqrstuvwxyz