Płytki drukowane
Limit pamięci: 32 MB
Firma Bajtel rozpoczyna produkcję elektronicznych układów
szeregowo-równoległych.
Każdy taki układ składa się z części elektronicznych, połączeń
między nimi oraz dwóch połączeń doprowadzających prąd.
Układ szeregowo-równoległy może składać się z:
-
pojedynczej części,
-
kilku mniejszych układów szeregowo-równoległych połączonych
szeregowo,
-
dwóch części rozgałęziających łączących równolegle kilka
mniejszych układów szeregowo-równoległych.
Układy są montowane na dwustronnych płytkach drukowanych.
Problem polega na ustaleniu, które połączenia powinny znaleźć się
na górnej, a które na dolnej stronie płytki.
Ze względów technicznych, jak najwięcej połączeń powinno znaleźć
się na dolnej stronie płytki, jednak do każdej części musi
dochodzić przynajmniej jedno połączenie znajdujące się na górnej
stronie płytki.
Zadanie
Napisz program, który:
-
wczyta opis układu szeregowo-równoległego,
-
obliczy minimalną liczbę połączeń, jakie muszą znajdować się na
górnej stronie płytki,
-
wypisze wynik.
Wejście
Ze standardowego wejścia należy wczytać opis układu
szeregowo-równoległego.
Opis ten ma postać rekurencyjną:
-
jeśli pierwszy wiersz opisu zawiera wielką literę S
oraz dodatnią liczbę całkowitą ()
oddzielone pojedynczym odstępem, to opisywany układ składa się
z mniejszych układów połączonych szeregowo,
opisanych w kolejnych wierszach,
-
jeśli pierwszy wiersz opisu zawiera wielką literę R oraz
dodatnią liczbę całkowitą ()
oddzielone pojedynczym odstępem, to opisywany układ składa się
z mniejszych układów połączonych równolegle (za pomocą
dwóch części rozgałęziających), opisanych w kolejnych wierszach,
-
wiersz zawierający jedynie wielką literę X oznacza
układ złożony tylko z pojedynczej części.
Łączna liczba liter
X pojawiających się w opisie układu
nie przekracza
, a głębokość rekurencji w opisie nie
przekracza
.
Wyjście
Twój program powinien pisać na standardowe wyjście.
W pierwszym wierszu powinna zostać wypisana
jedna liczba całkowita, równa minimalnej
liczbie połączeń, jakie muszą znaleźć się na górnej stronie
płytki.
Przykład
Dla danych wejściowych:
R 3
S 2
X
R 2
S 2
X
X
S 2
X
X
S 3
X
X
X
R 2
X
X
poprawną odpowiedzią jest:
8
Schemat układu szeregowo-równoległego dla danych z przykładu.
Ciągłą linią zaznaczono połączenia znajdujące się na
górnej stronie płytki.
Autor zadania: Marcin Kubica.