X Olimpiada Informatyczna 2002/2003

Wszystkie zadania I etapu

Rozważamy ciągi liter. Powiemy, że ciąg x₁x₂...x_n 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: x_i = x_j, x_i+1 = x_j+1, ..., x_j-1 = x_2j-i-1.

Interesują nas n-elementowe ciągi bez zająknięć o minimalnej liczbie liter.

Przykład

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.

Zadanie

Napisz program, który:

• wczyta długość ciągu n,
• obliczy n-elementowy ciąg bez zająknięć o minimalnej liczbie różnych liter,
• wypisze wynik.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna dodatnia liczba całkowita n, 1 <= n <= 10000000.

Wyjście

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.

Przykład

Dla danych wejściowych:

5

poprawnym wynikiem jest:

3
abcab