Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: John's Canonical Difference Bound Matrices
Description When John studied the timed automaton, he met the problem about how to trigger the machine. With the problem deeply studied, he found that it can be ascribed to the clock constraints of the timed automaton. The timed automation in question is described below: The clock variables, or simply clocks, are variables whose values are integers. Of course, time passes at the same rate for all clocks, and any clock can be reset to zero. John uses - All inequalities of the form
*t*`#` *c*or*c*`#` *t*are clock constraints, where*t*is a clock,`#` is either < or ≤, and*c*is an integer. - If
*A*_{1}and*A*_{2}are clock constraints, then*A*_{1}∧*A*_{2}is a clock constraint.
John notes that a clock constraint can define several regions in some multidimensional space. He wants to know such regions, so he defines the clock zones recursively as follows. For simplicity, he let C_{0}| × |C_{0}|. Each D has the form (_{ij}d, _{ij}`#` ), where d ∈ _{ij}Z ∪ {`$` }, `#` ∈ {<, ≤}. The value of D can be evaluated in the following form:_{ij}For every inequality x _{j}`#` d in clock zone _{ij}A, let D = (_{ij}d, _{ij}`#` ), where x and _{i}x are two clocks. If the bound of _{j}x_{i} − x for _{j}x_{i} and x is unknown, let _{j}D = (_{ij}`$` , <).For example, DBM of the clock zone given by
The representation of a clock zone by a DBM is not unique. In this example, there are some implied constraints that are not reflected in the DBM. Since Now John wants to do the similar adjusting operations of difference bounds for all clocks x until further application of this tighten operation does not change the matrix. John obtains the following new canonical difference bound matrix:_{j}
Note that some clock zone may contain contrary conditions and has not canonical difference bound matrix. But John can not obtain a canonical difference bound matrix for a complex clock zone. He asks for your help. Input The first line of the input file is a single integer Each test case consists of several lines. Four integers x < _{j}d or x − _{i}x ≤ _{j}d (0 ≤ i, j ≤ m, −10000 < d < 10000). If r = 0, then this line represents an inequality in the form of x − _{i}x < _{j}d, otherwise it represents an inequality in the form of x − _{i}x ≤ _{j}d. The maximal index m of clocks indicates that the indexes of the clocks are 0, 1, …, m, (1 ≤ m ≤ 100). Note that you have to get the value of m by yourself.A symbol Output For each test case, first output “ For each test case, output the description of the canonical difference bound matrix. If it doesn’t have a canonical difference bound matrix, print “ d, _{ij}`#` ), where `#` is either `<` or `<=` . If the bound of x − _{i}x for _{j}x and _{i}x is unknown, print _{j}`($,<)` at the position (i, j). Two consecutive elements on each row should be separated by a single space.Sample Input 1 1 2 2 0 0 2 0 0 2 0 2 1 0 1 -1 1 # Sample Output Case 1: (0,<=) (-1,<=) (0,<) (4,<) (0,<=) (2,<) (2,<=) (1,<=) (0,<=) Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator