SIO Anonymous
wydruk ps pdf

Ciągi bez zająknieć (cia)

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.

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

Nazwa pliku źródłowego: cia.XXX, gdzie XXX to c dla C, cpp dla C++, pas dla Pascala.
SIO, 2019-08-19 20:30:00