#P4644. Max and Min
Max and Min
题目描述
有两只特别珂爱的小猫,一个叫做 Min,另一个叫做 Max。今天,Min 和 Max 来玩一个游戏。
游戏开始时,有两个整数。每只猫都有许多组可以用来玩游戏的数对。小猫 Max 有 对非负整数 ,同理,小猫 Min 也有 对非负整数 。
当轮到小猫 Max 走的时候,它可以选择任何一对 并将 加上 , 加上 ;当轮到 Min 的时候,它可以选择任何可用的对 并把 减去 ,把 减去 。
Max 和 Min 可以在不同的移动过程中多次使用每一对。Max 先开始游戏。
如果在某个时刻 两个数字同时为负整数,那么 Min 就获胜了!否则,为 Max 获胜。
这两只珂爱的小猫想让你告诉它们,到底谁会赢?假设两只小猫都足够聪明,都会以最优方法来走。
输入格式
输入的第一行包含两个整数,分别为 和 。对应着 Max 和 Min 可用的数字对的数目。
第二行包含两个整数 这两个数代表小猫玩的数字的初始值。
接下来的 行包含数对 ,代表小猫 Max 可用的对。
最后的 行包含数对 ,代表小猫 Min 可用的对。
,,。
输出格式
如果小猫 Max 赢了,则输出 Max
,如果 Min 赢了,则输出 Min
。
2 2
42 43
2 3
3 2
3 10
10 3
Min
Min 可以通过移动 对 Max 移动 做出响应,并通过移动 来响应 Max 的移动 的方案。因此,对于每一对最大值和最小值的移动,数字 和 的值都将严格减小,因此,Min 迟早会赢。
1 1
1 1
3 4
1 1
Max
每对最大值和最小值移动后,数字 和 只会增加,因此它们都不会变为负值。