Polish version    English version  
  Historia OI -> V OI 1997/1998 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Terminarz
Statystyki
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
V Olimpiada Informatyczna 1995/96

Zadanie: ABS
Autor: Krzysztof Diks
AB-Słowa

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.

  • Każde dwa puste ab-słowa (tzn. nie zawierające żadnych liter) są podobne
  • Dwa niepuste, ładnie zbudowane ab-słowa X=[x1,...,xn] i Y=[y1,..,yn] są podobne, jeżeli są tej samej długości (n=m) i jest spełniony jeden z następujacych warunków:
    1. x1=y1, xn=yn oraz X[2..n-1] o Y[2..n-1] są ładnie zbudowanymi, podobnymi ab-słowami
    2. istnieje i, 1<=i<=n, takie, że słowa X]1..i], X[i+1..n] są ładnie zbudowanymi ab-słowami i
      1. Y[1..i], Y[i+1..n] są ładnie zbudowanymi ab-słowami o X[1..i] jest podobne do Y[1..i] oraz X[i+1..n] jest podobne do Y[i+1..n], lub
      2. Y[1..n-i], Y[n-i+1..n] są ładnie zbudowanymi ab-słowami i X[1..i] jest podobne do Y[n-i+1..n] oraz X[i+1..n] jest podobne do Y[1..n-i].

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

  • wczyta z pliku tekstowego ABS.IN elementy zbioru S;
  • policzy stopień zróżnicowania S;
  • zapisze wynik w pliku tekstowym ABS.OUT

Wejście

W pliku tekstowym ABS.IN są zapisane:

  • w pierwszym wierszu liczba n elementów zbioru S, 1<=n<=1000;
  • w kolejnych n wierszach elementy zbioru S tj. ładnie zbudowane ab-słowa, po jednym w każdym wierszu; pierwsza litera każdego ab-słowa jest pierwszym symbolem w wierszu i między kolejnymi literami w słowie nie ma żadnych innych znaków; każde ab-słowo ma długość co najmniej 1, a co najwyżej 200

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.





Wersja do druku