Polish version    English version  
  History of OI -> V OI 1997/1998 -> Problems


 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
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Schedule
Stats
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
Niebieskie ksi.eczki
V Olimpiada Informatyczna 1997/1998

Task: UKL
Author: Marcin Kubica
Assemler circuits

III stage contest  

Bytetel Company decided to improve computers they produce. They want to replace assembler programs with special systems called assembler circuits. Assembler programs consist solely of assignments. Each assignment is determined by four elements:

  • two registers from which data are taken,
  • elementary operation that should be performed on the data,
  • register to which the result should be written.

We assume that there are at most 26 registers. They are represented by small letters of English alphabet. There are at most 4 elementary operations and they are represented by capital letters A, B, C, D.
An assembler circuit has:

  • inputs assigned to registers; initial value of appropriate register is passed to the input;
  • outputs, also assigned to registers; their final values are passed to these registers.

There are gates inside a circuit. Each gate has two inputs and one output. The gate performs an elementary operation on data delivered on its inputs and passes the result to its output. Inputs of gates and outputs of the whole circuit are connected to outputs of other gates or inputs of the circuit. Outputs of gates and inputs of the circuit can be connected to many inputs of other gates or outputs of the circuit. Connections among gates cannot form cycles.

An assembler circuit is equivalent to an assembler program if for any initial state of registers the final state of registers produced by the program and the circuit are the same.

Task

Write a program that:

  • reads a description of an assembler program from the text file UKL.IN;
  • computes the minimal number of gates in an assembler circuit equivalent to the given program;
  • writes the result to the text file UKL.OUT.

Input

In the first line of the input file UKL.IN there is one integer n (1 <= n < 1000), which is the number of instructions in the program.

In the following n lines there are descriptions of consecutive instructions in the program. Each description is a four-letter word beginning with an elementary operation symbol: A,B,C or D. The second and the third letter (which are small letters of English alphabet) are names of registers, in which data are placed. The fourth letter is a name of a register, in which the result should be placed.

Output

In the first and only line of the output file UKL.OUT there should be written one integer, which is the minimal number of gates in an assembler circuit equivalent to the given program.

Example

For the text file UKL.IN:

8
Afbc
Bfbd
Cddd
Bcbc
Afcc
Afbf
Cfbb
Dfdb

the correct answer is the output file UKL.OUT:

6

A circuit equivalent to the given program is shown in the figure.

Figure



Print friendly version