/ Vijos / 题库 /

暴力破解不等式

暴力破解不等式

背景

某个数学理论的应用。

描述

AsukaNoKaze一直喜欢使用暴力解法破解不等式。

据传在MO界,有一句非常著名的口诀,被尊称为八字真言,曰:“通分展开整理得证”。

这种解法被国外的MOers形容为"Bloody and Ugly" "Brute force"
可AsukaNoKaze发现 很多时候 当我们对不等式束手无策的时候 暴力解法的确是一种有效的手段。

AsukaNoKaze使用暴力解法对各大竞赛的不等式痛下杀手,屡试不爽。

很多不等式在展开以后形成如下的对称形式

sigma(s1^a1*s2^a2*...*sn^an)>=sigma(s1^b1*s2^b2*...*sn^bn)

(当然 作为齐次不等式 a1+a2+....an=b1+b2+...bn 变量s1,s2,...sn非负)
其中sigma表示对称和(也就是说 一共n!项) 例如
sigma(x^3)=x^3y^0z^0+x^3z^0y^0+y^3x^0z^0+y^3z^0x^0+z^3x^0y^0+z^3y^0x^0=2*(x^3+y^3+z^3)
sigma(x^3y^2z^1)=x^3y^2z^1+x^3z^2y^1+y^3x^2z^1+y^3z^2x^1+z^3x^2y^1+z^3y^2x^1
(三元sigma 一共是6项)
有时候 我们把sigma(s1^a1*s2^a2*...*sn*an)写作 [a1,a2,...an]
例如 著名的均值不等式可以写成 [n,0,0...0]>=[1,1,1...1]
又比如x^2+y^2+z^2>=xy+yz+zx 写成[2,0]>=[1,1]
(a+b-c)(a+c-b)(b+c-a)<=abc 展开后写成 [3,0,0]+[1,1,1]>=2[2,1,0] (虽然本题只要求比较两个[]的大小关系)

现在AsukaNoKaze有一堆不等式 懒散的他不愿意亲自动笔 于是就把这个艰苦的任务交给了你~~

格式

输入格式

第一行为k和n表示式子的个数和变量的个数(2<=k,n<=100)
以下k行 每行n个正整数 表示[a1,a2,....,an]中的诸ai.... 保证每个式子中的ai都是不超过200的非负整数。

保证各个式子齐次(即每一行的sum(ai)都相等)
接下来若干行
每行两个正整数i,j 1<=i,j<=n
表示询问第i个式子与第j个式子的大小关系。

询问次数保证不太多(想想vijos的题目source文件上传大小上限)
最后有两个0表示数据结束

输出格式

按顺序每行输出一个运算请求的结果
如果两个式子相等 输出Equal!
如果恒有某个式子大于等于另一个式子 请输出较大的式子的编号
如果两个式子大小关系不确定(既存在使第一个式子较大的取值也存在使第二个大的式子的取值)请输出Can't tell!
行末有回车!

样例1

样例输入1

3 3
3 0 0
1 2 0
1 1 1
1 1
1 2
2 3
1 3
0 0

样例输出1

Equal!
1
2
1

限制

各个测试点1s

提示

样例中的不等式即
2x^3+2y^3+2z^3>=(y+z)x^2+(z+x)y^2+(x+y)z^2>=6xyz
[3,0,0]>=[2,1,0]>=[1,1,1]

可以请教对国外竞赛动态比较关注的MOer。

来源

AsukaNoKaze 原创
QQ: 413022965
Email/MSN: ArthurTLee@yahoo.com.cn

信息

ID
1271
难度
3
分类
数论 点击显示
标签
递交数
101
已通过
51
通过率
50%
被复制
3
上传者

相关

在下列训练计划中:

RP++分类题库