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.