V Olimpiada Informatyczna 1995/96
|
Zadanie: ABS
|
Autor: Krzysztof Diks
|
Zawody I stopnia |
Plik źródłowy: | ABS.??? (np. pas, c, cpp) |
Plik wykonywalny: | ABS.exe |
Plik wejściowy: | ABS.in |
Plik wyjściowy: | ABS.out |
Każdy niepusty ciąg, którego elementami są małe litery a i b, a także ciąg pusty nazywamy ab-słowem. Jeżeli X=[x1,..,xn] jest ab-słowem, a i, j takimi dowolnymi liczbami całkowitymi, że 1<=i<=j<=n, to przez X[i..j] będziemy oznaczali podsłowo X składające się z kolejnych liter xi,..,xj. Powiemy, że ab-słowo X=[x1,..xn] jest ładnie zbudowane, jeżeli zawiera tyle samo liter a co b i dla każdego i=1,..,n podsłowo x[1..i] zawiera co najmniej tyle samo liter a co liter b.
Podamy teraz indukcyjną definicję podobieństwa ładnie zbudowanych ab-słów.
Stopniem zróżnicowania niepustego zbioru S ładnie zbudowanych ab-słów nazywamy największą liczbę ab-słów, które można wybrać z S tak, żeby żadne dwa wybrane słowa nie były do siebie podobne.
Zadanie
Napisz program, który
Wejście
W pliku tekstowym ABS.IN są zapisane:
Wyjście
W pierwszym i jedynym wierszu pliku tekstowego ABS.OUT należy zapisać jedną liczbę całkowitą - stopień zróżnicowania S.
Przykład
Dla pliku wejściowego ABS.IN o zawartości:
3 aabaabbbab abababaabb abaaabbabb
poprawnym rozwiązaniem jest ABS.OUT o zawartości:
2
Twój program powinien szukać pliku ABS.IN w katalogu bieżącym i tworzyć plik ABS.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę ABS.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku ABS.EXE.