#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>得到的所有整数,并重新排列为非降序。
例如,考虑样例输入 的第一个表达式。两个 shuffle 表达式都以列表 [1,2] 为输入,并各自以 的概率返回 [1,2] 或 [2,1](两者相互独立)。外层 concat 操作把这两个返回列表作为输入,并返回它们的拼接结果。也就是说,它会以各 的概率返回 [1,2,1,2]、[1,2,2,1]、[2,1,1,2] 和 [2,1,2,1] 之一。
显然,当队伍使用 BALLOON 提交解答时,不能再使用逐字节输出比较,因为它的输出是概率性的。评测服务器必须检查提交程序是否与评委创建的标准程序等价。若对于任意整数列表 ,两个程序返回 的概率都相等,则称这两个程序等价。
你的任务是判断给定的两个 BALLOON 程序是否等价。
输入格式
输入包括:
- 一行一个字符串 ,表示第一个程序。
- 一行一个字符串 ,表示第二个程序。
每个程序都是语法合法的 BALLOON 程序,长度在 到 个字符之间,不包含空格,也不包含空列表(即输入中不会出现字符串 或 [])。
每个程序中的每个整数都大于 且小于 。
输出格式
如果两个程序等价,输出 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
提示
【数据规模与约定】
具体限制见输入格式。