Polish version    English version  
  History of OI -> X OI 2002/2003


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Rules
For contestants
Helpful resources
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
X Olympiad in Informatics 2002/2003

Problem: Printed-Circuit Boards
Author: Marcin Kubica

The firm of Bytel starts to produce series-parallel electronic circuits. Each such a circuit consists of electronic units, connections between them, and two power connections. A series-parallel circuit may consist of:

  • a single unit

    Single unit

  • several smaller series-parallel circuits connected in series

    Series
connection

  • two branching units connecting in parallel several smaller series-parallel circuits.

    Parallel connection

The circuits are assembled on two-sided printed-circuit boards. The problem is to determine which connections should run on the top and which on the bottom side of the board. For technical reasons as many connections as possible should run on the bottom side but to each unit at least one must come from the top side of the board.

Task

Write a program which:
  • reads the description of a series-parallel circuit,
  • computes the minimal number of connections that must run on the top side of the board,
  • writes the result.

Input

From the standard input one should read the description of a series-parallel circuit. The description is in a recursive form:
  • if the first line of the description contains a capital letter S and a positive integer n (2 <= n <= 10000) separated from each other by a single space, then the circuit being described consists of n smaller circuits connected in series; they are described in the successive lines,
  • if the first line of the description contains a capital letter R and a positive integer n (2 <= n <= 10000) separated from each other by a single space, then the circuit being described consists of n smaller circuits connected in parallel (by means of two branching units); they are described in the successive lines,
  • a line containing only one capital letter X describes a circuit consisting of a single unit only.
  • The total number of letters X occurring in the description of a circuit does not exceed 10000000, and the recursive depth of the description does not exceed 500.

    Output

    Your program should write to the standard output. In the first line there should be one integer equal to the minimal number of connections that must run on the top side of the board.

    Example

    For the following input data:
    R 3
    S 2
    X
    R 2
    S 2
    X
    X
    S 2
    X
    X
    S 3
    X
    X
    X
    R 2
    X
    X
    
    the correct answer is in the following output:
    8
    

    Example of a printed circuit
    Scheme of the series-parallel circuit for the data from the example. Solid lines indicate the connections running on the top side of the board.



    Print friendly version