Problem description
Przenieśmy się w przyszłość, rok 2030. Jasio uczęszcza na lekcje informatyki do pewnej znanej i lubianej szkoły znanej z najwyższej jakości nauczania. Przygotowuje się właśnie do polimpiady informatycznej (taka unowocześniona wersja archaicznej Olimpiady Informatycznej). Na tych prestiżowych zawodach może być konieczne rozwiązanie zadania utworzenia wielkiego tekstu. Na czerwonym tle. A kartka w Microsoft Word jest domyślnie biała. Co tu zrobić? Ponieważ Jasio nie potrafił zmienić tła całej strony na inny niż biały to stwierdził, że użyje lepszego edytora tekstu: Microsoft Paint. Tak, dobrze czytasz – Microsoft Paint. Przecież też ma funkcjonalność dodawania tekstu do obrazka, co nie? Bardzo sprytny pomysł, którego nauczył się na zajęciach w szkole.
Jasio napisał czarnymi literami na białym tle swój tekst (czcionką Arial, autor zadania wyjątkowo powstrzymał się przed użyciem Comic Sansa):
Następnie postanowił delektować się możliwością wylania kubła czerwonej farby, żeby zmienić tło obrazka na czerwone. Niestety, uzyskany efekt pozostawia wiele do życzenia:
Poza problemem z tym, że kubeł farby niedokładnie koloruje kontury na granicy koloru białego z czarnym, w tekście pozostawione zostały białe dziury. Jasio zaobserwował więc, że czasami, żeby zmienić tło napisanego napisu, trzeba wylać kubeł farby więcej niż raz. Pomożesz mu ustalić ile dokładnie razy? Niedokładności narzędzia przy konturze liter Jasio jest w stanie zaakceptować i możesz się tym nie przejmować.
Napisz program, który wczyta napis, wyznaczy minimalną liczbę użyć narzędzia kubła farby aby zmienić tło napisu i wypisze wynik na standardowe wyjście.
Wskazówka: Jeżeli nie dysponujesz narzędziem
Microsoft Paint, możesz wyszukać w przeglądarce internetowej aplikacji
jspaint, która jest wierną kopią on-line kultowego
programu. Na potrzeby rozwiązania tego zadania powinno być to
wystarczające (w szczególności znajdziesz tam również czcionkę
Arial, gdyby brakowało jej w Twoim systemie).
Wejście
W pierwszym (jedynym) wierszu wejścia znajduje się niepusty ciąg małych i/lub wielkich liter alfabetu angielskiego bez żadnych odstępów – jest to napis, dla którego Jasio chce zmienić tło.
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita – minimalna liczba użyć narzędzia kubła z farbą.
Ograniczenia
Długość napisu nie przekracza 1 000 000 znaków.
Przykład
| Input | Output | |
|
|