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: Artinals
Description 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*.
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*= {*A*_{1},*A*_{2}, …,*A*} where_{s}*A*are artinals of height ≤_{i}*n*− 1 and*A*_{1}<*A*_{2}< … <*A*._{s} - If
*A*= {*A*_{1},*A*_{2}, …,*A*} and_{s}*B*= {*B*_{1},*B*_{2}, …,*B*} are two artinals of height ≤_{t}*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*A*=_{j}*B*for all integer_{j}*j*such that 1 ≤*j*<*k*and either*k*=*s*+ 1 or*A*<_{k}*B*._{k}
A its canonical representation. It is a string repr(A) composed of characters ‘{’, ‘}’ and ‘,’ defined in the following way: repr(∅) = “{}”, and if A is an artinal with canonical form A = {A_{1}, A_{2}, …, A}, then repr(A) = “{” + repr(_{s}A_{1}) + “,” + … + “,” + repr(A) + “}”. The canonical representation is often rather lengthy. In order to shorten it, the following definition is introduced. For any integer _{s}n ≥ 0 an artinal (called nfinite ordinal) is defined by induction on n: 0 := ∅ and := {n + 1} ∪ n for all nn ≥ 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 that is not contained in an occurrence of nm 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*= {*A*_{1},*A*_{2}, …,*A*} put ∩_{s}*A*:=*A*_{1}∩*A*_{2}∩ … ∩*A*._{s} - Unary union ∪: for any artinal
*A*= {*A*_{1},*A*_{2}, …,*A*} put ∪_{s}*A*:=*A*_{1}∪*A*_{2}∪ … ∪*A*; ∪∅ := ∅._{s} - Binary intersection ∩:
*A*∩*B*:= {*x*:*x*∈*A*∧*x*∈*B*}. - Binary union ∪:
*A*∪*B*:= {*x*:*x*∈*A*∨ x ∈*B*}. - Binary difference −:
*A*−*B*:= {*x*∈*A*:*x*∉*B*}. - Binary symmetrical difference ⊕:
*A*⊕*B*:= (*A*−*B*) ∪ (*B*−*A*).
- Equality = and inequality ≠.
- Inclusion ⊂ and ⊃: (
*A*⊂*B*) ⇔ (*B*⊃*A*) ⇔ (*x*∈*A*⇒*x*∈*B*). - Element relations ∈ and ∋:
*B*∈*A*(equivalent to*A*∋*B*) means that*B*is an element of*A*. - Canonical order relations <, >, ≤, ≥ described above (as usual,
*A*≤*B*⇔ ((*A*<*B*) ∨ (*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 five kinds of operators: - Assignment operator <
*ident*> “:=” <*expr*> — sets variable <*ident*> to the value of expression <*expr*>. - Evaluate operator “!”<
*expr*> — evaluates <*expr*> and prints the result in reduced canonical representation on a separate line of output. - Check condition operator “?”<
*expr*><*relation*><*expr*> — checks the condition and outputs either “FALSE” or “TRUE” on a separate line of output. - Comment operator “#”<
*any_characters*> — the entire line is copied to the output. - Empty operator — an empty line (i.e. line consisting only of blank characters) — does nothing.
The following definitions are used: n ≤ 2^{9} are set to the finite ordinals . All other variables are initialized with ∅. All identifiers are case-sensitive.nInput The input file 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). Sample Input !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}}} Source Northeastern Europe 2003, Northern Subregion |

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

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

Any problem, Please Contact Administrator