#P16988. [NWERC 2018] Equality Control

[NWERC 2018] Equality Control

背景

译自 NWERC 2018 E 题。

题目描述

在程序设计竞赛圈中,最重要的职位之一是 Chief Equality Officer(CEO,首席平等官)。这个人负责确保每支队伍都有平等的获胜机会。自从去年的 NWERC 以来,现任 CEO Gregor 一直在认真思考如何让比赛更加公平和平等。

他的答案是引入一种新的编程语言,并且将其作为唯一允许提交的语言。这样,就不会有队伍因为没有掌握某种允许语言而处于劣势。这门语言叫做 BALLOON,是 Building A Long List Of Ordinary Numbers 的缩写。它唯一的数据类型是整数列表。为了保持语言快速,它只有四条指令:

  • [x1,...,xn] 是列表构造器。它按给定顺序返回括号内的整数。
  • concat(<Expr1>,<Expr2>) 返回先计算表达式 <Expr1> 得到的所有整数,再接上计算表达式 <Expr2> 得到的所有整数所组成的列表。
  • shuffle(<Expr>) 返回计算 <Expr> 得到的所有整数,并按照一个均匀随机排列重新排列,即每一种排列出现的概率相同。
  • sorted(<Expr>) 返回计算 <Expr> 得到的所有整数,并重新排列为非降序。

例如,考虑样例输入 11 的第一个表达式。两个 shuffle 表达式都以列表 [1,2] 为输入,并各自以 0.50.5 的概率返回 [1,2][2,1](两者相互独立)。外层 concat 操作把这两个返回列表作为输入,并返回它们的拼接结果。也就是说,它会以各 0.250.25 的概率返回 [1,2,1,2][1,2,2,1][2,1,1,2][2,1,2,1] 之一。

显然,当队伍使用 BALLOON 提交解答时,不能再使用逐字节输出比较,因为它的输出是概率性的。评测服务器必须检查提交程序是否与评委创建的标准程序等价。若对于任意整数列表 LL,两个程序返回 LL 的概率都相等,则称这两个程序等价。

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

输入格式

输入包括:

  • 一行一个字符串 AA,表示第一个程序。
  • 一行一个字符串 BB,表示第二个程序。

每个程序都是语法合法的 BALLOON 程序,长度在 3310610^6 个字符之间,不包含空格,也不包含空列表(即输入中不会出现字符串 [])。

每个程序中的每个整数都大于 00 且小于 10910^9

输出格式

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

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

提示

【数据规模与约定】

具体限制见输入格式。