2005 ASIA PROGRAMMING CONTEST – MANILA

October 29, 2005

 

 

Problem D

 

 Any Relation?

 

Input File: d.in

Limit: 2 seconds

 

A relation on a set A is a relation from A to A. A relation R on a set A is:

 

i. reflexive if (a, a) Î R for every element a Î A

ii. symmetric if (b, a) Î R whenever (a, b) Î R, for all a, b Î A

iii. antisymmetric only if a = b when (a, b) Î R and (b, a) Î R, for all a, b Î A

iv. transitive if whenever (a, b) Î R and (b, c) Î R, then (a, c) Î R, for all a, b, c Î A

 

Relations can be combined in any way two sets can be combined such as union (R1 È R2), intersection (R1 Ç R2), and difference (R1 - R2). If R1 is a relation from set A to set B, and R2 is a relation from set B to set C, the composite (R2 ° R1) of relation R1 and R2 is the relation consisting of ordered pairs (a, c) where a Î A, c Î C, and for which there exists an element b Î B such that (a, b) Î R1 and (b, c) Î R2. The power R2 of relation R is equivalent to R ° R.

 

Write a program that determines whether given relations or combinations of relations on given sets, satisfy or do not satisfy the properties defined.

 

 

Input

 

The input file starts with 1 to 10 lines of set definitions, and followed by 1 to 30 lines (each being a test case) of relations or combined relations on any of the given sets. Set names and relation names consist of exactly 2 characters (1 alphabet character followed by 1 digit).

 

Each set contains 2 to 30 unique elements separated by commas and spaces. Each element is a string consisting of 1 to 5 alphabet or digit characters. Each relation contains unique elements separated by commas and spaces. Each element is an ordered pair enclosed in parenthesis.

 

Union operator is represented as +, intersection operator is represented as *, and difference operator is represented as -. The composition operator is represented as # and power of 2 is represented as ^2. Assume that at most one operation may be used per test case.

 

Assume also that there are no empty relations being tested and that all set definitions and test cases are in the same format as the examples and are valid.

 

 

Output

 

For each of the test cases, output R, S, A, T respectively for reflexive, symmetric, antisymmetric, and transitive, if it satisfies the respective property.

 

 

Sample Input                                                                                                     Sample Output

 

S1 = { a, b, c, d, e, f, g }

S3 = { 10, 20, 30 }

S2 = { Cat, Dog, Sheep }

K2 = { a, b, c, d }

Case 1: X3 on K2 = { (a,a), (a,b), (b,a), (b,b), (c,d), (d,a), (d,d) }

Case 2: X2 on K2 = { (a,a), (a,b), (a,d), (b,a), (b,b), (c,c), (d,a), (d,d) }

Case 3: X4 on K2 = { (b,a), (c,a), (c,b), (d,a), (d,b), (d,c) }

Case 4: X1 on K2 = { (a,a), (a,b), (a,c), (a,d), (b,b), (b,c), (b,d), (c,c), (c,d), (d,d)}

Case 5: R1 on S1 = { (a, b), (a, c), (c, a) }

Case 6: R2 on S3 = { (10, 10), (20, 20), (30, 30) }

Case 7: R4 on S1 = { (a, c), (b, a) }

Case 8: R1 + R4

Case 9: R4 * R1

Case 10: R5 on S3 = { (10, 20) }

Case 11: R1 – R4

Case 12: R2 + R5

Case 13: R1 # R4

Case 14: R1^2

 

 

 

 

Case 1:

Case 2: R S

Case 3: A T

Case 4: R A T

Case 5:

Case 6: R S A T

Case 7: A

Case 8: S

Case 9: A T

Case 10: A T

Case 11: A

Case 12: R A T

Case 13: A T

Case 14: A T