#P2366. Sacrament of the sum

    ID: 1367 传统题 1000ms 256MiB 尝试: 17 已通过: 3 难度: 9 上传者: 标签>其他二分查找双指针扫描Ural State University Internal Contest October'2000 Junior Session

Sacrament of the sum

题目描述

——我的兄长,修道院院长明天想了解长期研究的结果。他不多不少就想看到求和机器!甚至,他希望我们的机器——仅仅一台机器——尽可能深刻地展示它对求和圣礼的理解。他希望我们的机器找到两个数,使它们的和等于神圣数字1000010000

——嘘——嘘——嘘!这简直是近乎亵渎神明的疯狂想法!机器怎么能计算出这个神圣数字呢?我们已经为此努力了二十七年,但我们也只教会了它判断输入的两个数的和是大于还是小于1000010000。一个凡人能找到两个数,使它们的和等于1000010000吗?

——但即使我们的机器做不到,我们也得借助它来完成这件事。否则我们将会……这么说吧,会遇到大麻烦,如果把被煮沸的油也能这么说的话。不过,我有个主意。你还记得吗,上周我们往机器里输入了两个数7-71313,机器回答说它们的和小于1000010000。我不知道怎么去验证这个结果,但我们除了相信我们的研究成果之外别无选择。现在我们输入一个比7-7大的数,然后再次启动机器。我们就这样一遍又一遍地做,直到找到一个数,这个数加上1313能得到1000010000。我们唯一要做的就是准备一个递增的数字列表。

——我不相信这个办法……我们从一个显然大于神圣数字的和开始,然后减小其中一个加数。这样我们更有可能避免被煮……遇到大麻烦。

没有达成一致意见,修士们各自回到了自己的房间。到了第二天,他们每个人都准备了一份数字列表,在他看来,这份列表能拯救他们……这两份列表能一起拯救他们吗?

你的程序应该判断,是否有可能从两个整数列表中选择出两个数,使得它们的和等于1000010000

输入

你会依次得到这两个列表。每个列表的格式如下:在列表的第一行写着第ii个列表的数字数量NiN_i。接下来是第ii个数字列表,每个数字占一行(共NiN_i行)。满足以下条件:1Ni500001 \leq N_i \leq 50000,列表中的每个元素都在32768-327683276732767的范围内。第一个列表是递增的,第二个列表是递减的。

输出

如果有可能从这两个整数列表中选择出两个数,使得它们的和等于1000010000,你应该向标准输出写入“YES”。否则,你应该写入“NO”。

4
-175
19
19
10424
3
8951
-424
-788
YES

提示

这个问题的输入数据量很大,使用scanf() 而不是cin来读取数据,以避免超出时间限制。

来源

乌拉尔国立大学内部竞赛,2000年10月,初级组