题目描述
很久很久以前,中原地区分成了 N 个国家,编号为 1∼N,任意两个国家都可互达。每个国家有一个攻击值 Ai 和防御值 Bi 。定义一个人从 i 国去 j 国的危险值为:假如 Ai>Bj ,则危险值为 Ai2−Bj2,否则危险值为 0 。现在,Nan 从国家 1 出发,经过每一个国家有且仅有一次,最后回到国家 1 ,要求找出一种方案,使得其中危险值的最大值最小。
输入格式
第一行正整数 N ,表示有 N 个国家;
第二行正整数 A1,A2,x,y,z,有等式 Ai=(x×Ai−1+y×Ai−2+z)mod32767;
第三行正整数 B1,B2,x,y,z,有等式 Bi=(x×Bi−1+y×Bi−2+z)mod32767。
输出格式
输出一个数,表示危险值的最大值最小是多少。
5
2 4 1231 4432 123
123 45 3245 555 6676
9171832
数据规模与约定
对于 100% 的数据, 1≤N≤106
样例说明
A 数组为 2,4,13911,5151,3031 。
B 数据为 123,45,24364,26060,21765。
其中一种最优方案为 1−2−4−3−5−1,危险值分别为 0,0,0,0,9171832。