QOJ.ac

QOJ

Limite de temps : 1 s Limite de mémoire : 2048 MB Points totaux : 100

#1294. 相等性控制

Statistiques

在编程竞赛圈中,最重要的角色之一是首席平等官(Chief Equality Officer,简称 CEO)。此人的职责是确保每个参赛队伍都有平等的获胜机会。自去年 NWERC 以来,现任 CEO Gregor 一直在深入思考如何让比赛变得更加公平和平等。

他的解决方案是引入一种新的编程语言作为唯一允许提交的语言。这样,就不会有队伍因为没有掌握任何一种允许使用的语言而处于劣势。这种语言被称为 BALLOON,即“构建普通数字长列表”(Building A Long List Of Ordinary Numbers)的缩写。它唯一的数据类型是整数列表。为了保持语言的运行速度,它仅包含四条指令:

  • $[x_1, \dots, x_n]$ 是列表构造器。它按给定的顺序返回括号内的整数。
  • $\text{concat}(\langle \text{Expr}_1 \rangle, \langle \text{Expr}_2 \rangle)$ 返回在求值 $\langle \text{Expr}_1 \rangle$ 后得到的所有整数,紧接着求值 $\langle \text{Expr}_2 \rangle$ 后得到的所有整数,并将它们合并为一个列表。
  • $\text{shuffle}(\langle \text{Expr} \rangle)$ 返回由 $\langle \text{Expr} \rangle$ 求值得到的所有整数,并按照均匀随机排列进行重排,即每个元素排列出现的概率相等。
  • $\text{sorted}(\langle \text{Expr} \rangle)$ 返回由 $\langle \text{Expr} \rangle$ 求值得到的所有整数,并按非递减顺序重排。

举个例子,考虑样例输入 1 中的第一个表达式。两个 shuffle 表达式都以列表 $[1,2]$ 作为输入,并分别以 $0.5$ 的概率返回列表 $[1,2]$ 和 $[2,1]$(两者相互独立)。外部的 concat 算子将这两个返回的列表作为输入,并返回它们的拼接结果。即,它以 $0.25$ 的概率返回列表 $[1,2,1,2]$、$[1,2,2,1]$、$[2,1,1,2]$ 或 $[2,1,2,1]$ 中的一个。

显然,当参赛队伍使用 BALLOON 提交代码时,我们不能再使用逐字节的输出比较,因为其输出是概率性的。评测服务器需要检查提交的程序是否与评委创建的样例解决方案等价。如果对于任何整数列表 $L$,两个程序返回 $L$ 的概率相等,则称这两个程序是等价的。

你的任务是判断给定的两个 BALLOON 程序是否等价。

输入格式

输入包含: 一行包含字符串 $A$,表示第一个程序。 一行包含字符串 $B$,表示第二个程序。

每个程序都是一个语法正确的 BALLOON 程序,长度在 $3$ 到 $10^6$ 个字符之间,且不包含空格或空列表(即字符串 “ ” 或 “[]” 不会出现在输入中)。

程序中的每个整数都大于 $0$ 且小于 $10^9$。

输出格式

如果两个程序等价,输出 “equal”,否则输出 “not equal”。

样例

样例输入 1

concat(shuffle([1,2]),shuffle([1,2]))
shuffle([1,2,1,2])

样例输出 1

not equal

样例输入 2

sorted(concat([3,2,1],[4,5,6]))
[1,2,3,4,5,6]

样例输出 2

equal

样例输入 3

concat(sorted([4,3,2,1]),shuffle([1]))
concat(concat([1,2,3],shuffle([4])),sorted([1]))

样例输出 3

equal

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.