{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"The designers of digital integrated circuits (IC) are very concerned about the correctness of their designs because, unlike software, ICs cannot be easily tested. Real tests are not possible until the design has been finalized and the IC has been produced. \r\u003cbr\u003eTo simulate the behavior of a digital IC and to more or less guarantee that the final chip will work, all of today\u0027s digital ICs are based on a synchronous design. \r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/182ccaeaf284c645fd145ac536a30d20?v\u003d1715162058\"\u003e\r\u003cbr\u003eFigure: The critical path (dashed line) takes 43ns to settle\r\u003cbr\u003e\u003c/center\u003e\r\u003cbr\u003eIn a synchronous design, an external clock signal triggers the IC to go from a well defined and stable state to the next one. On the active edge of the clock, all input and output signals and all internal nodes are stable in either the high or low state. Between two consecutive edges of the clock, the signals and nodes are allowed to change and may take any intermediate state. The behavior of a synchronous network is predictable and will not fail due to hazards or glitches introduced by irregularities of the real circuit. \r\u003cbr\u003eTo analyze whether an IC has a synchronous design, we distinguish between synchronous and asynchronous nodes. Flip flops are synchronous nodes. On the active edge of the clock, the output of the flip flop changes to the state of the input and holds that state throughout the next clock cycle. Synchronous nodes are connected to the clock signal. \r\u003cbr\u003eSimple gates like ANDs or ORs are asynchronous nodes. Their output changes - with a short delay - whenever one of their inputs changes. During that transition phase, the output can even go into some undefined or intermediate state. \r\u003cbr\u003eFor simplicity, we assume that all inputs of the circuits are directly connected to the output of a synchronous node outside the circuit and that all outputs of the circuit are directly connected to the input of a synchronous node outside the circuit. \r\u003cbr\u003eFor an IC to have a synchronous design, mainly two requirements must be met: \r\u003cbr\u003e\u003cul\u003e\r\u003cbr\u003e\u003cli\u003e\tThe signal delay introduced between two synchronous nodes must be smaller or equal than the clock period so there is enough time for nodes to become stable. In figure 1, the round-ended boxes are asynchronous nodes whereas the square boxes are synchronous nodes. The delay introduced on the dashed path is 43ns and exceeds the given clock period of 30ns. \r\u003cbr\u003e\u003c/li\u003e\u003cli\u003e\tThere may be n o cycles composed exclusively of asynchronous nodes. In the real circuit such cycles could oscillate. In figure 2, the dashed path constitutes a cycle of asynchronous nodes. \r\u003cbr\u003e\u003c/li\u003e\u003c/ul\u003e\r\u003cbr\u003eFigure 3 shows a circuit with a synchronous design. It does not contain cycles composed of asynchronous nodes and the longest path between two synchronous nodes is shorter than the clock period of 30ns. \r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/577bd17a3b86fb0f407daab499866883?v\u003d1715162058\"\u003e \r\u003cbr\u003eFigure: The design contains a cycle (dashed line)\r\u003cbr\u003e\u003c/center\u003e\r\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/f74b374b5842abd9c0b1317f7c8e564c?v\u003d1715162058\"\u003e\r\u003cbr\u003eFigure: A synchronous design\r\u003cbr\u003e\u003c/center\u003e\r\u003cbr\u003eYour are to write a program that decides for a given IC whether it has a synchronous design or not. You are given a network of synchronous and asynchronous nodes, a delay for each node, some inputs and outputs and the clock period. \r\u003cbr\u003eYou may safely assume that \r\u003cbr\u003e\u003cul\u003e\r\u003cbr\u003e\u003cli\u003e\tthe delays introduced between any input and any output of the same node are equal, i.e. equal to the delay given for that node, \r\u003cbr\u003e\u003c/li\u003e\u003cli\u003e\tsynchronous nodes have no delay at all, \r\u003cbr\u003e\u003c/li\u003e\u003cli\u003e\tall connections between two nodes connect an output to an input. \r\u003cbr\u003e\u003c/li\u003e\u003c/ul\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input file contains several circuits. The first line gives the number of circuits in the file. \r\u003cbr\u003eFor each circuit in the file, the first line contains the clock period for the circuit, given as an integer number in nanoseconds. The next line gives the number of nodes. The following lines each contain a node, described by a letter and a integer number. The letter is \u0027i\u0027 for an input, \u0027o\u0027 for an output, \u0027a\u0027 for an asynchronous node and \u0027s\u0027 for a synchronous node. The number gives the delay introduced by the node as an integer number in nanoseconds (only meaningful for an asynchronous node). Nodes are implicitly numbered, starting at zero. \r\u003cbr\u003eAfter the nodes, the number of connections for the circuit follows. Each following line contains a pair of integer numbers denoting a connection between the output and the input of two nodes. The connection links an output of the node given by the first number and an input of the node given by the second number. \r\u003cbr\u003eThe clock signal is not given in the input file. We assume that all synchronous nodes are properly connected to the clock signal. \r\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each circuit in the input file, your output file should contain a line with one of the following messages: \r\u003cbr\u003e\u003cul\u003e\r\u003cbr\u003e\u003cli\u003e\t\"Synchronous design. Maximum delay: \u0026lt; ss \u0026gt;.\" if the circuit has a synchronous design. \r\u003cbr\u003e\u003c/li\u003e\u003cli\u003e\t\u0026lt; ss \u0026gt; should be replaced by the longest delay found on any path between two synchronous nodes.\r\u003cbr\u003e\u003c/li\u003e\u003cli\u003e\t\"Circuit contains cycle.\" if the circuit contains a cycle composed exclusively of asynchronous nodes. \r\u003cbr\u003e\u003c/li\u003e\u003cli\u003e\t\"Clock period exceeded.\" if there is a path between two synchronous nodes that is longer than the given clock period and there are no cycles composed of asynchronous nodes. \r\u003cbr\u003e\u003c/li\u003e\u003c/ul\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n30\r\n10\r\ni 0\r\ni 0\r\ni 0\r\ni 0\r\no 0\r\no 0\r\na 9\r\na 11\r\na 8\r\ns 0\r\n9\r\n0 8\r\n1 7\r\n2 6\r\n2 6\r\n6 7\r\n7 8\r\n8 4\r\n7 9\r\n9 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eSynchronous design. Maximum delay: 28.\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}