#P2366. Sacrament of the sum
Sacrament of the sum
题目描述
——我的兄长,修道院院长明天想了解长期研究的结果。他不多不少就想看到求和机器!甚至,他希望我们的机器——仅仅一台机器——尽可能深刻地展示它对求和圣礼的理解。他希望我们的机器找到两个数,使它们的和等于神圣数字。
——嘘——嘘——嘘!这简直是近乎亵渎神明的疯狂想法!机器怎么能计算出这个神圣数字呢?我们已经为此努力了二十七年,但我们也只教会了它判断输入的两个数的和是大于还是小于。一个凡人能找到两个数,使它们的和等于吗?
——但即使我们的机器做不到,我们也得借助它来完成这件事。否则我们将会……这么说吧,会遇到大麻烦,如果把被煮沸的油也能这么说的话。不过,我有个主意。你还记得吗,上周我们往机器里输入了两个数和,机器回答说它们的和小于。我不知道怎么去验证这个结果,但我们除了相信我们的研究成果之外别无选择。现在我们输入一个比大的数,然后再次启动机器。我们就这样一遍又一遍地做,直到找到一个数,这个数加上能得到。我们唯一要做的就是准备一个递增的数字列表。
——我不相信这个办法……我们从一个显然大于神圣数字的和开始,然后减小其中一个加数。这样我们更有可能避免被煮……遇到大麻烦。
没有达成一致意见,修士们各自回到了自己的房间。到了第二天,他们每个人都准备了一份数字列表,在他看来,这份列表能拯救他们……这两份列表能一起拯救他们吗?
你的程序应该判断,是否有可能从两个整数列表中选择出两个数,使得它们的和等于。
输入
你会依次得到这两个列表。每个列表的格式如下:在列表的第一行写着第个列表的数字数量。接下来是第个数字列表,每个数字占一行(共行)。满足以下条件:,列表中的每个元素都在到的范围内。第一个列表是递增的,第二个列表是递减的。
输出
如果有可能从这两个整数列表中选择出两个数,使得它们的和等于,你应该向标准输出写入“YES”。否则,你应该写入“NO”。
4
-175
19
19
10424
3
8951
-424
-788
YES
提示
这个问题的输入数据量很大,使用scanf() 而不是cin来读取数据,以避免超出时间限制。
来源
乌拉尔国立大学内部竞赛,2000年10月,初级组