首页 > 试题广场 >

编程题1

[编程题]编程题1
  • 热度指数:250 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
有三只球队,每只球队编号分别为球队1,球队2,球队3,这三只球队一共需要进行 n 场比赛。现在已经踢完了k场比赛,每场比赛不能打平,踢赢一场比赛得一分,输了不得分不减分。已知球队1和球队2的比分相差d1分,球队2和球队3的比分相差d2分,每场比赛可以任意选择两只队伍进行。求如果打完最后的 (n-k) 场比赛,有没有可能三只球队的分数打平。



输入描述:
第一行包含一个数字 t (1 <= t <= 10)
接下来的t行每行包括四个数字 n, k, d1, d2(1 <= n <= 10^12; 0 <= k <= n, 0 <= d1, d2 <= k)


输出描述:
每行的比分数据,最终三只球队若能够打平,则输出“yes”,否则输出“no”
示例1

输入

2
3 3 0 0
3 3 3 3

输出

yes
no

说明

case1: 球队1和球队2 差0分,球队2 和球队3也差0分,所以可能的赛得分是三只球队各得1分
case2: 球队1和球队2差3分,球队2和球队3差3分,所以可能的得分是 球队1得0分,球队2得3分, 球队3 得0分,比赛已经全部结束因此最终不能打平。
直接列出方程组,解方程判断解的合法性
"""解方程组
a+b+c=k
b-a=-d1或d1
b-c=-d2或d2
"""

def judge(n, k, d1, d2):
    # 由于不能打平,因此n场比赛发出n分(每场发出一分给赢的队伍)
    if n % 3 != 0:
        # 如果n不能被3整除,三个队伍肯定不可能平分
        return False
    for factor1 in [-1, 1]:
        for factor2 in [-1, 1]:
            # 解方程得到三支球队的得分
            a = (k - 2*d1*factor1 + d2*factor2) // 3;
            b = (k + d1*factor1 + d2*factor2) // 3;
            c = (k + d1*factor1 - 2*d2*factor2) // 3;
            # 跳过不合法的解
            if (a + b + c != k or a < 0 or b < 0 or c < 0) or (a > n // 3 or b > n // 3 or c > n // 3):
                continue
            return True
    return False

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        n, k, d1, d2 = map(int, input().split())
        if judge(n, k, d1, d2):
            print("yes")
        else:
            print("no")


编辑于 2021-01-27 17:42:11 回复(0)