P7040 [NWRRC 2016] Java2016

John likes to learn esoteric programming languages. Recently he discovered the probabilistic $\textit{programming language}$ Java2K. Built-in functions of Java2K have only a certain probability to do whatever you $\textit{intend them}$ to do. The Java2K programming is very hard, so John designed a much simpler language for training: Java2016. $\textit{Built-in}$ operators of Java2016 are deterministic, while their operands are random. Each value in $\textit{Java2016 is}$ a positive integer in the range $0 \cdots 255$ , inclusive. Java2016 supports six operators of three precedencies: $$\begin{aligned}{\langle \mathrm{expression}\rangle}&\quad::=\quad{\langle \mathrm{expression}\rangle}\operatorname{`\texttt{min}\text'}{\langle \mathrm{sum}\rangle}\mid{\langle \mathrm{expression}\rangle}\operatorname{`\texttt{max}\text'}{\langle \mathrm{sum}\rangle}\mid {\langle \mathrm{sum}\rangle}\\{\langle \mathrm{sum}\rangle}&\quad::=\quad{\langle \mathrm{sum}\rangle}\operatorname{`\texttt{+}\text'}{\langle \mathrm{term}\rangle}\mid{\langle \mathrm{sum}\rangle}\operatorname{`\texttt{-}\text'}{\langle \mathrm{term}\rangle}\mid{\langle \mathrm{term}\rangle}\\{\langle \mathrm{term}\rangle}&\quad::=\quad{\langle \mathrm{term}\rangle}\operatorname{`\texttt{*}\text'}{\langle \mathrm{factor}\rangle}\mid {\langle \mathrm{term}\rangle}\operatorname{`\texttt{/}\text'}{\langle \mathrm{factor}\rangle}\mid {\langle \mathrm{factor}\rangle}\\{\langle \mathrm{factor}\rangle}&\quad::=\quad\operatorname{`\texttt{(}\text'}{\langle \mathrm{expression}\rangle}\operatorname{`\texttt{)}\text'}\mid `\texttt{?}\text'\mid {\langle \mathrm{macro}\rangle}\end{aligned}$$ Minimum $(\textit{`min'})$ and maximum $((\textit{`max'}))$ operators are defined as usual. Addition $(\text{`+'}),$ subtraction $(\text{`--'}) and$ multiplication $(\text{`}\times\text{'})$ are defined modulo $256$ . The result of the division $(\text{`}/\text{'})$ is rounded towards zero. $\textit{If}$ the divider is zero, the program crashes. The argument of the operator is a result of another $\textit{operator, evenly}$ distributed random value $(\text{`}?\text{'})$, or macro substitution. For instance, the probability that $\text{`?/?/?'}$ is evaluated to zero is $98.2\%$, while the probability of $the crash$ is $0.8\%$. The Java2016 program consists of zero or more macro definitions, followed by the resulting expression. $ Each$ macro definition has a form of $$\begin{aligned}{\langle \mathrm{macrodef}\rangle}&\quad::=\quad{\langle \mathrm{macro}\rangle}\operatorname{`\texttt{=}\text'}{\langle \mathrm{expression}\rangle}\\{\langle \mathrm{macro}\rangle}&\quad::=\quad\operatorname{`\texttt{a}\text'}\ldots\operatorname{`\texttt{z}\text'}\end{aligned}$$ The macro should be defined before the first use. It may not be redefined. The macro is expanded to $its definitio_n$ on each use. For instance, ```plain a = ? max ? (a max $a) / a ``` is expanded to `((? max ?) max (? max ?)) / (? max ?)`. John is going to add probabilistic constants to Java2016, so for each possible constant value he needs $a progra_m$ that successfully evaluates to this value with at least one-half probability. Crashes are $\textit{counted toward}$ failures.

无

无

Time limit: 2 s, Memory limit: 512 MB.