| | PROBLEM STATEMENT
Digital circuits are composed of logical elements. When inputs of a logical
element change, its output may change too, to match the new state of the
inputs. Output change, however, does not happen instantaneously: each logical
element in a chain introduces a small time delay into the circuit.
Calculate the delay of a digital circuit composed of multiple logical elements
AND, OR, and NOT. Express the result as an int representing the number of
logical elements in the longest path from the circuit's input to the circuit's
output. The circuit does not have feedbacks, meaning that no output of an
element can influence any of that element's inputs, either directly or through
other elements.
DEFINITION
Class name: TimeDelay
Method name: maxDelay
Parameters: String[]
Return type: int
Method signature: int maxDelay(String[] nodes); Be sure your method is public.
nodes may have between 2 to 50 String objects, inclusive. Each String defines a
"node" in the circuit. A "node" may be an input, an output, or a logical
element of type "AND", "OR", or "NOT". Strings are formatted as follows:
TYPE:Input1,Input2,...
TYPE is a single lowercase character designating the type of the node, as
follows:
'i' - the node is an input,
'x' - the node is an output,
'a' - the node is a logical AND element,
'o' - the node is a logical OR element,
'n' - the node is a logical NOT element.
The input list following the colon ':' character (Input1, Input2,...)
designates inputs of this node. The input list consists of numbers in the range
0 to 48, inclusive, representing zero-based indexes of nodes used as inputs to
the current node. For example, string "a:1,2" represents a logical AND element
with two inputs, connected to the outputs of nodes at index 1 and 2. Elements
of type 'a' and 'o' have 2 to 8 inputs, inclusive. Elements of type 'n' and 'x'
have exactly one input. Elements of type 'i' do not have inputs, therefore
strings that start with 'i' do not contain the ':' character.
TopCoder will ensure that:
* nodes has at least two and no more than fifty elements
* The first character of each String is 'i', 'x', 'a', 'o', or 'n'
* nodes contains at least one but no more than five inputs
* nodes contains at least one output
* Number of inputs per element type is within the limits set above: two to
eight, inclusive, for ANDs and ORs; exactly one for NOTs and Outputs, zero for
Inputs
* Indexes of elements used as inputs to an element are lower than the index of
the current element (this ensures that the circuit has no feedbacks)
NOTES
* Since the time delay is expressed as a count of unit delays, it is
effectively equal to the maximum number of AND, OR, or NOT elements between an
input and an output, over the set of all input-output combinations.
* In cases when multiple inputs and/or outputs exist, maxDelay should consider
delays between all possible pairs of inputs and outputs, and return the maximum
delay.
* Circuits may use output nodes as inputs to other nodes. This is not different
from re-using that output's input, in that it does not alter circuit's timing.
For example,
{"i","n:0","x:1","n:2","x:4"} and
{"i","n:0","x:1","n:1","x:4"} are equivalent.
EXAMPLES
1. nodes = {"i","i","i","n:0","a:1,2,3","x:4"} This circuit contains a logical
AND element with three inputs, two of which are connected directly to inputs,
and one connected to an input through a logical NOT element. See diagram below
(for a more detailed diagram check out
http://www.topcoder.com/contest/circuits.html):
+---+ +---+
i0 --|not|--| |
+---+ | |
i1 ---------|and|-- o0
| |
i2 ---------| |
+---+
Since the longest path from the output to an input goes through both AND and
NOT elements, maxDelay should return 2.
2. nodes = {"i","x:0"} This trivial circuit connects its only input to its only
output, with no logical elements in between. Such a circuit has no delay and
therefore maxDelay should return 0.
3. nodes = {"i","n:0","x:1"} This circuit contains one logical NOT element in
between of its input and its output, therefore maxDelay should return 1.
4. nodes = {"i","i","i","n:0","a:1,2,3","x:4","x:0","x:3"} This circuit is
similar to the one above, except that it adds two more outputs, with delays 0
(output 6) and 1 (output 7). Since the delay of the output 5 is greater than
the delay for the other two outputs, maxDelay should return 2.
5. nodes = {"i","x:0","x:1"} This circuit is similar to one from the second
example. It adds an extra output, so maxDelay should return 0.
|