Ciągi bez zająknięć
Limit pamięci: 32 MB
Rozważamy ciągi liter.
Powiemy, że ciąg
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
(
)
zachodzi:
.
Interesują nas
-elementowe ciągi bez zająknięć
o minimalnej liczbie liter.
Przykład
Dla
wystarczą dwie litery, powiedzmy
i
.
Mamy dokładnie dwa 3-elementowe ciągi bez zająknięć złożone
z takich liter:
i
.
Dla
potrzebne są już 3 różne litery.
Na przykład
jest trójliterowym ciągiem bez zająknięć.
W ciągu
mamy dwa zająknięcia:
i
.
Zadanie
Napisz program, który:
-
wczyta długość ciągu
,
-
obliczy
-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
,
.
Wyjście
Twój program powinien pisać na standardowe wyjście.
W pierwszym wierszu powinna zostać wypisana
jedna dodatnia liczba całkowita
,
równa minimalnej liczbie różnych liter, które muszą wystąpić
w
-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
małych liter alfabetu angielskiego,
od litery
do
-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
poprawną odpowiedzią jest:
3
abcab
Autor zadania: Krzysztof Sikora.