QOJ.ac

QOJ

実行時間制限: 2.0 s メモリ制限: 256 MB 満点: 100

#12733. Java2016

統計

John 喜欢学习深奥的编程语言。最近他发现了一种概率编程语言 Java2K。Java2K 的内置函数只有一定的概率能按照你的意图执行。

Java2K 编程非常困难,因此 John 设计了一种更简单的训练语言:Java2016。Java2016 的内置运算符是确定性的,但它们的操作数是随机的。Java2016 中的每个值都是 $0$ 到 $255$(含)之间的正整数。

Java2016 支持三种优先级的六种运算符:

$$\langle \text{expression} \rangle ::= \langle \text{expression} \rangle \text{‘min’} \langle \text{sum} \rangle \mid \langle \text{expression} \rangle \text{‘max’} \langle \text{sum} \rangle \mid \langle \text{sum} \rangle$$ $$\langle \text{sum} \rangle ::= \langle \text{sum} \rangle \text{‘+’} \langle \text{term} \rangle \mid \langle \text{sum} \rangle \text{‘-’} \langle \text{term} \rangle \mid \langle \text{term} \rangle$$ $$\langle \text{term} \rangle ::= \langle \text{term} \rangle \text{‘*’} \langle \text{factor} \rangle \mid \langle \text{term} \rangle \text{‘/’} \langle \text{factor} \rangle \mid \langle \text{factor} \rangle$$ $$\langle \text{factor} \rangle ::= \text{‘(’} \langle \text{expression} \rangle \text{‘)’} \mid \text{‘?’} \mid \text{macro}$$

最小值(‘min’)和最大值(‘max’)运算符按常规定义。加法(‘+’)、减法(‘-’)和乘法(‘*’)定义为模 $256$ 运算。除法(‘/’)的结果向零取整。如果除数为零,程序会崩溃。运算符的参数是另一个运算符的结果、均匀分布的随机值(‘?’)或宏替换。

例如,表达式 “?/?/?” 计算结果为零的概率为 $98.2\%$,而程序崩溃的概率为 $0.8\%$。

Java2016 程序由零个或多个宏定义组成,后跟最终的表达式。每个宏定义的形式为:

$$\langle \text{macrodef} \rangle ::= \langle \text{macro} \rangle \text{‘=’} \langle \text{expression} \rangle$$ $$\langle \text{macro} \rangle ::= \text{‘a’} \dots \text{‘z’}$$

宏必须在首次使用前定义。它不能被重新定义。宏在每次使用时都会展开为其定义。例如:

a = ? max ? (a max a) / a

会被展开为 “((? max ?) max (? max ?)) / (? max ?)”。

John 打算在 Java2016 中加入概率常量,因此对于每个可能的常量值,他都需要一个能以至少 $1/2$ 的概率成功计算出该值的程序。程序崩溃计为失败。

输入格式

输入包含一个整数 $c$ — 目标常量 ($0 \le c \le 255$)。

输出格式

输出一个 Java2016 程序,该程序以不低于 $1/2$ 的概率成功计算出常量 $c$。程序的总长度不得超过 $256$ 个字符(不含空格)。

样例

样例输入 1

0

样例输出 1

? / ? / ?

样例输入 2

1

样例输出 2

a = ? max ?
(a max a) / a

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.