X Olympiad in Informatics 2002/2003
|
Problem: Sequences without Stammers
|
Author: Krzysztof Sikora
|
We consider sequences of letters. We say a sequence x1x2...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.
In the first line of the standard input there is one positive integer n, 1 <= n <= 10000000.
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.
You may assume 26 letters are enough.
5a correct answer is in the following output:
3 abcab