시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB34161446.667%

문제

We consider sequences of letters. We say a sequence x1,x2,…,xn contains a stammer, if we can find in it two occurrences of the same subsequence, one directly following the other, i.e. if for some i and j (1 ≤ i < j ≤ (n+i+1)/2) we have xi=xj, xi+1=xj+1,…,xj-1=x2j-i-1.

We are interested in n-element sequences having no stammers, built of the minimal number of different letters.

For n=3 it is enough to use two letters, say a and b. We have exactly two 3-element sequences without stammers build of those letters: aba and bab. For n=5 we need three different letters. For example abcab is a three-letter sequence without stammers. In the sequence babab we have two stammers: ba and ab.

Write a program which:

  • reads the length of the sequence n,
  • computes an n-element sequence with no stammers built of the minimal number of different letters,
  • writes the result.

입력

In the first line of the standard input there is one positive integer n, 1 ≤ n ≤ 10,000,000.

출력

Your program should write to the standard output. In the first line there should be one positive integer k equal to the minimal number of different letters that must appear in an n-element sequence having no stammers.

In the second line one should write the computed sequence without stammers as a word that comprises n lower case letters of English alphabet and is built only of the letters from a up to the k-th letter of the alphabet. If there are many such sequences, your program should write one of them.

예제 입력 1

5

예제 출력 1

3
abcab

출처

Olympiad > Polish Olympiad in Informatics > POI 2002/2003 > Stage 1 1번

  • 데이터를 추가한 사람: cozyyg