X Olimpiada Informatyczna 2002/2003
|
Zadanie: cia
|
Autor: Krzysztof Sikora
|
Zawody I stopnia |
Plik źródłowy: | cia.xxx (xxx=pas,c,cpp) |
Rozważamy ciągi liter. Powiemy, że ciąg x1x2...xn zawiera zająknięcie, jeśli napotykamy w nim dwa, następujące bezpośrednio po sobie, wystąpienia takiego samego podciągu. Tzn. jeśli dla pewnych i i j (1 <= i < j <= (n+i+1)/2) zachodzi: xi = xj, xi+1 = xj+1, ..., xj-1 = x2j-i-1.
Interesują nas n-elementowe ciągi bez zająknięć o minimalnej liczbie liter.
Dla n=3 wystarczą dwie litery, powiedzmy a i b. Mamy dokładnie dwa 3-elementowe ciągi bez zająknięć złożone z takich liter: aba i bab. Dla n = 5 potrzebne są już 3 różne litery. Na przykład abcab jest trójliterowym ciągiem bez zająknięć. W ciągu babab mamy dwa zająknięcia: ba i ab.
Napisz program, który:
W pierwszym wierszu standardowego wejścia zapisana jest jedna dodatnia liczba całkowita n, 1 <= n <= 10000000.
Twój program powinien pisać na standardowe wyjście. W pierwszym wierszu powinna zostać wypisana jedna dodatnia liczba całkowita k, równa minimalnej liczbie różnych liter, które muszą wystąpić w n-elementowym ciągu nie zawierającym zająknięć.
W drugim wierszu należy wypisać obliczony ciąg bez zająknięć, jako słowo złożone z n małych liter alfabetu angielskiego, od litery a do k-tej litery alfabetu. Jeżeli istnieje wiele takich ciągów, Twój program powinien wypisać jeden z nich.
Możesz przyjąć, że 26 liter wystarczy.
Dla danych wejściowych:
5
poprawnym wynikiem jest:
3 abcab