Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
458. Equation
Олимпиадные задачи на английском языке| 19/09/2007 | Занятие 2 (E) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
A few years ago Nick learned set theory, and liked it so much that sets became the subject of his bachelor's
thesis. Nick's thesis describes a new kind of mathematical equations – set equations. Set equations are
composed of set variables, which represent various subsets of a universal set `Ω`. The following four
operations are defined for set variables:
- Intersection `∩`: `A\ ∩\ B\ :=\ {x\ :\ x\ ∈\ A\ ∧\ x\ ∈\ B}`.
- Union `∪`: `A\ ∪\ B\ :=\ {x\ :\ x\ ∈\ A\ ∨\ x\ ∈\ B}`.
- Difference –: `A-B\ :=\ {x\ :\ x\ ∈\ A\ ∧\ x\ ∉\ B}`.
- Symmetrical difference `Δ`: `A\ Δ\ B\ :=\ (A-B)\ ∪\ (B-A)`.
The operations are listed in the order of their precedence, i.e. intersection has the highest precedence,
union has lower precedence than intersection, difference has lower precedence than union, and symmetrical
difference has the lowest precedence. Parentheses can be used to change operations precedence as usual.
The thesis includes a chapter dedicated to automated solving of some specific classes of set equations.
Nick has already elaborated a notation for storing equations in text files. Here is some quotation from
the thesis:
The following notation is used for describing set equations:
<space or tab> `→` space | tabulation symbol
<ws> `→` <space or tab> *
<char> `→` 'A' | 'B' | … | 'Z' | 'a' | 'b' | … | 'z'
<var> `→` <char> <char> *
<expr> `→` <var>
| <expr> <ws> <operator> <ws> <expr>
| '(' <ws> <expr> <ws> ')'
<operator> `→` '+' | '*' | '-' | '^'
<equation> `→` <expr> <ws> '=' <ws> <expr>
Operators `∩`, `∪`, – and `Δ` are encoded with tokens '+', '*', '-' and '^' respectively. The '='
token denotes the operator of set equality.
It is possible to assign values to some variable using the following notation:
<digit> `→` '0' | '1' | … | '9'
<element> `→` <digit> *
<variable value> `→` <var> <ws> '=' <ws> <values>
<values> `→` <element>
| <element> <space or tab> <ws> <values>
Unfortunately Nick is not very skilled in programming so he asks you to help and write a program module
for automated solving of one specific simple class of equations – the equations where each variable, except
`Ω`, occurs exactly one time.
Input
Input file is written in Nick's notation.
The first line of the input file contains an equation to solve. Total length of the equation does not exceed
1 000 characters. There is exactly one occurence of each variable, except "Omega", in the equation.
The following lines contain definitions of variable values. Variable name lengths do not exceed ten
characters each. There is always a variable called "Omega" that represents the universal set. Both the
number of elements in the universal set and the value of each element does not exceed 500.
The total length of all variable definitions does not exceed 100 000 characters.
Output
First line of the output file must contain "Solution" if there exists at least one solution of the given
equation and "No Solution" otherwise.
If the solution exists the following lines must contain such values of all undefined variables so that equation
is satisfied. The variables may be listed in arbitrary order.
Sample Input 1
Omega - OneOrThree = Two Omega = 1 2 3 Two = 2
Sample Output 1
Solution OneOrThree = 1 3
Sample Input 2
Omega * result * result = Empty Omega = 1 2 3 4 5 Empty =
Sample Output 2
Solution result=
Sample Input 3
(one+two) ^(TWO+three) = result one =1 TWO =1 3 4 5 two =2 three=3 Omega=1 2 3 4 5 result = 2 3 4 5
Sample Output 3
Solution
Sample Input 4
Omega ^Omega = Omega Omega=123 234 345 456
Sample Output 4
No Solution
