Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ETI07E2 - Kreskowany rysunek

Przy ręcznym wykonywaniu dwuwymiarowego rysunku technicznego jedną z najbardziej żmudnych i niewdzięcznych prac było precyzyjne kreskowanie rysunku. Choć w ostatnich latach narzędzia komputerowe wspomagające projektowanie pozwoliły na zautomatyzowanie tego typu czynności, z kreskowaniem wiążą się nowe problemy. Wiele przenośnych formatów danych pozwala wyłącznie na zapis obrazu w postaci odcinków linii prostych, przez co reprezentacja zakreskowanego wielokąta zajmuje bardzo dużo pamięci.

Dla podanego wielokąta należy wyznaczyć, ile przynajmniej odcinków trzeba narysować, by uzyskać jego poprawne kreskowanie. Dla uproszczenia przyjmujemy, że w obwodzie wielokąta wszystkie boki są równoległe do osi (kierunki: N-S i W-E), a wszystkie wierzchołki wielokąta leżą na punktach siatki jednostkowej. Rozważane kreskowanie polega na narysowaniu domkniętego odcinka głównej przekątnej (kierunek: NW-SE) dla każdego kwadratu siatki jednostkowej, który leży w całości w obrębie wielokąta.

Wejście

W pierwszym wierszu podana jest liczba naturalna n określająca długość obwodu wielokąta (4<=n<=106). W kolejnym wierszu znajduje się n znaków {'N','S','W','E'}, opisujących ciąg kolejnych przesunięć jednostkowych pozwalających na obejście całego obwodu wielokąta, startując od ustalonego punktu obwodu.

Wyjście

Należy wypisać pojedynczą liczbę całkowitą, określającą minimalną liczbę odcinków potrzebnych do wykonania kreskowania wielokąta zgodnie z założeniami zadania.

Przykłady

Zestaw przykładowy 1

Wejście:
8
EENNWWSS


Wyjście:
3


Zestaw przykładowy 2

Wejście:
38
NNEENNEESSSSEENEESSSEESSWWWWWWWWNNNNWW


Wyjście:
15

Ilustracja przykładu 2
Ilustracja przykładu 2

Dodane przez:adrian
Data dodania:2006-11-11
Limit czasu wykonania programu:0.167s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.