SIO Anonymous
wydruk ps pdf

Płytki drukowane (ply)

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,

    Pojedyncza część

  • kilku mniejszych układów szeregowo-równoległych połączonych szeregowo,

    Połączenie szeregowe

  • dwóch części rozgałęziających łączących równolegle kilka mniejszych układów szeregowo-równoległych.

    Połączenie równoległe

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ą n (2 <= n <= 10000) oddzielone pojedynczym odstępem, to opisywany układ składa się z n 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ą n (2 <= n <= 10000) oddzielone pojedynczym odstępem, to opisywany układ składa się z n 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 10000000, a głębokość rekurencji w opisie nie przekracza 500.

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

poprawnym wynikiem jest:

8

Przykładowy układ
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.


Nazwa pliku źródłowego: ply.XXX, gdzie XXX to c dla C, cpp dla C++, pas dla Pascala.
SIO, 2019-05-23 17:10:12