Artinals
Time Limit: 1 Second Memory Limit: 32768 KB
Nick has recently learned about a special kind of sets called artinian sets or simply artinals. These sets have the advantage of possessing a finite representation, so they can be processed by a computer. However, their formal definition is a bit complicated. Here it is:
- The only artinal of height <= 0 is the empty set.
- Artinals of height <= n are exactly the finite sets composed of artinals of height <= n - 1. Here n >= 1 is an arbitrary natural number.
- Finally, A is an artinal if A is an artinal of height <= n for at least one integer n.
- The set of all artinals is denoted by U.
It is immediate from the definition that an artinal of height <= n is also an artinal of height <= n + 1. Thus for any artinal A we can define its height h(A) as the minimal integer n such that A is an artinal of height <= n. An artinal of height n is also called an n-artinal.
There were two other definitions which took a lot of time to understand. They are the definition of canonical order on U (denoted by <) and the definition of canonical form of an artinal:
- The canonical form of an artinal A of height <= n is a representation A = { A1, A2, ..., As} where Ai are artinals of height <= n - 1 and A1 < A2 < ... < As.
- If A = {A1, A2, ..., As} and B = {B1, B2, ..., Bt} are two artinals of
height <= n
written in the canonical form, then we put A < B iff there exists an integer k, 1 <= k <= min(s+1, t), such that Aj = Bj for all integer j such that 1 <= j < k and either k = s + 1 or Ak < Bk.
Now we can define for any artinal A its canonical representation. It is a string repr(A) composed of characters '{', '}' and ',' defined in the following way: repr(emptyset) = "{}", and if A is an artinal with canonical form A = {A1, A2, ..., As}, then repr(A) = "{" + repr(A1) + "," + ... + "," + repr(As) + "}".
The canonical representation is often rather lengthy. In order to shorten it, the following definition is introduced. For any integer n >= 0 an artinal n_ (called finite ordinal) is defined by induction on n: 0_ := emptyset and n+1_ :={n_} U n_ for all n >= 0. Then we can define the reduced canonical representation of an artinal in the following way: We take the canonical representation of this artinal and substitute n for any occurrence of the ordinal n_ that is not contained in an occurrence of m_ for some m > n.
Then some operations on artinals are defined. These operations (from highest priority to lowest) are:
- Unary intersection *: for a non-empty artinal A = {A1, A2, ..., As} put
* A := A1 * A2 * ... * As. - Unary union U: for any artinal A = {A1, A2, ..., As} put + A := A1 + A2 + ... + As; + emptyset := emptyset.
- Binary intersection *: A * B := {x : x in A & x in B}.
- Binary union +: A + B := {x : x in A V x in B}.
- Binary difference -: A - B := {x in A : x not in B}.
- Binary symmetrical difference ^: A ^ B := (A - B) + (B - A).
Besides, some relations between artinals are defined:
- Equality = and inequality !=.
- Inclusion < and >: A < B <=> B > A <=> (x in A => x in B).
- Element relations in and include: B in A (equivalent to A include B) means that B is an element of A.
- Canonical order relations <, >, <=, >= described above (as usual, A <= B <=> ((A < B) V (A = B)), A > B <=> B < A and A >= B <=> B <= A).
Now Nick wants you to write a program that would make some computations with artinals. This program will consist of several operators, each on a separate line. There are four kinds of operators:
- Assignment operator
":= " - sets variable to the value of expression . - Evaluate operator "!"
- evaluates and prints the result in reduced canonical representation on a separate line of output. - Check condition operator "?"
- checks the condition and outputs either "FALSE" or "TRUE" on a separate line of output. - Comment operator "#"
- the entire line is copied to the output.
The following definitions are used:
The binary operators (in the order they were listed in the definition of
Besides, before the execution of the program the variables with names that are decimal representations (without leading zeros) of non-negative integers n <= 2^9 are set to the finite ordinals n_. All other variables are initialized with emptyset. All identifiers are case-sensitive.
Input
The input consists of not more than one hundred lines each containing a single operator. No line is longer than 254 characters.
Output
Produce one line of output for each "?", "!" and "#" operator as described above. It is guaranteed that there will be no "run-time errors"' (e.g. unary ^ will never be applied to an empty set).
This problem contains multiple test cases!
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between
output blocks.
Sample Input
1
!2 + 2
!2*2
!3-4
# More examples!
00 := 5+3
! 3-5
! 00
! (5-3)*(5+3)
? 3>9
A := {2,3,9}
B := {1,7}
! A^ B
! +239
? 2->00
? 2<<00
? A>>B
! {{{},{{}},{}},B,{A},{B},{A,B}}+B
Sample Output
2
2
0
# More examples!
0
5
{3,4}
FALSE
{1,2,3,7,9}
238
TRUE
TRUE
FALSE
{1,2,7,{1,7},{{1,7}},{{1,7},{2,3,9}},{{2,3,9}}}
Submit
Source: Northeastern Europe 2003, Northern Subregion