Time Limit: Java: 10000 ms / Others: 10000 ms
Memory Limit: Java: 32768 KB / Others: 32768 KB
In contemporary VLSI chip industry, the software tools used by electrical engineers
perform many optimizations. Your task is to implement one specific optimization
of some chip design. Your tool is given an acyclic net of NAND gates (NAND gate
computes the negated conjunction of its inputs, i.e. the output value of the
gate is 0 if and only if its both input values are 1). The net is a part of
already synthesized component and cannot be changed. All the inputs of the net
are connected to one signal x. The objective is to disconnect x from some inputs
and to assign constant signals 0 and/or 1 to those inputs in such a way that
the function implemented by the design remains unchanged.
We say that an assignment of x's and/or 0's and/or 1's to the inputs of the net is optimal if the number of inputs connected to x is the smallest possible but the net still computes the same function as if all the inputs were connected to x.
Look at the following design.
We can change it to the design with only one variable input, for example:
(Observe that there are other ways of connecting the inputs to just one x and to some number of 0's and 1's that implement the same function).
Write a program which for each data set:
reads the description of the net,
computes an optimal assignment of x's and/or 0's and/or 1's to the inputs of the net,
writes the result.