首页 > 试题广场 >

编程题1

[编程题]编程题1

热度指数：658 时间限制：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分，比赛已经全部结束因此最终不能打平。

算法知识视频讲解

泣血残阳

这道题其实是一个线性方程组求解问题。设k场比赛的三只球队的得分分别为x1,x2,x3.设此后n - k场比赛的三只球队得分分别为t1,t2,t3.

那么可以得到以下方程：
|x1 - x2| = d1
|x2 - x3| = d2
x1 + x2 + x3 = k
t1 + t2 + t3 = n - k
x1 + t1 = x2 + t2 = x3 + t3
显然以上共有6个线性无关的方程，可以将6个未知量分别解出，得到
x1 = (k - (2d1 + d2)) / 3
x2 = (k - (d2 - d1)) / 3
x3 = (k + (d1 + 2d2)) / 3
t1 = (n - k + (2d1 + d2)) / 3
t2 = (n - k + (d2 - d1)) / 3
t3 = (n - k - (d1 + 2d2)) / 3
其中d1,d2分别取正负号，总共可能存在4组解。分别验证这四组解中，是否有使得各个未知量均为非负整数的解，若存在，则有可行解。

发表于 2018-02-21 11:25:45 回复(3)

3VVV

思路：这道题不需要解什么线性方程组，对于每一组测试用例，设k次对应的比分为：x+/-d1, x, x+/-d2, ***生4种情况，利用三者之和为k解出x, 这4种只要有一种满足：max(x+/-d1, x, x+/-d2)<=n/3, 且mod(n,3)=0,则yes,否则else.

#include<iostream>
#include<algorithm>
using namespace std;

int main() {
int t;
long int n,k,d1,d2;
cin>>t;
for (int i=0; i<t; ++i) {
cin>>n>>k>>d1>>d2;
bool flag = false;
long int tp; // 不是long int会溢出
if (n%3==0) {
if ((k-d1-d2)%3==0) {
tp = (k-d1-d2)/3;
if (tp+d1<=n/3 && tp+d2<=n/3) {cout<<"yes"<<endl; flag=true; continue;}
}
if((k-d1+d2)%3==0) {
tp = (k-d1+d2)/3;
if (tp>=d2 && tp+d1<=n/3) {cout<<"yes"<<endl; flag=true; continue;}
}
if((k+d1-d2)%3==0) {
tp = (k+d1-d2)/3;
if (tp+d2<=n/3 && tp>=d1) {cout<<"yes"<<endl; flag=true; continue;}
}
if((k+d1+d2)%3==0) {
tp = (k+d1+d2)/3;
if (tp>=d1 && tp>=d2 && tp<=n/3) {cout<<"yes"<<endl; flag=true; continue;}
}
}
if (!flag) {
cout<<"no"<<endl;
}
}
return 0;
}

发表于 2018-09-20 16:45:30 回复(0)

C++

Zaneking

#include<iostream>

#include<cmath>
using namespace std;
int main()
{
long long t;
cin>>t;
while(t--)
{
long long n,k,d1,d2;
cin>>n>>k>>d1>>d2;
if(k-(2*d1+d2)==0 || (k-(2*d1+d2)>0 && (k-(2*d1+d2))%3==0))
{
if(((((n-k)-d2-(d1+d2))%3)==0) && ((((n-k)-d2-(d1+d2)))>=0))
{
cout<<"yes"<<endl;
}
else
{
cout<<"no"<<endl;
}
}
else if(k-(d1+d2)==0 || (k-(d1+d2)>0 && (k-(d1+d2))%3==0))
{
if(((((n-k)-max(d1,d2)-abs(d1-d2))%3)==0) && ((((n-k)-max(d1,d2)-abs(d1-d2)))>=0))
{
cout<<"yes"<<endl;
}
else
{
cout<<"no"<<endl;
}
}
else if(k-(d1+2*d2)==0 || (k-(d1+2*d2)>0 && (k-(d1+2*d2))%3==0))
{
if(((((n-k)-d1-(d1+d2))%3)==0) && ((((n-k)-d1-(d1+d2)))>=0))
{
cout<<"yes"<<endl;
}
else
{
cout<<"no"<<endl;
}
}
else if(k-(2*d1-d2)==0 || (k-(2*d1-d2)>0 && (k-(2*d1-d2))%3==0))
{
if(((((n-k)-(d1+d2))%3)==0) && ((((n-k)-(d1+d2)))>=0))
{
cout<<"yes"<<endl;
}
else
{
cout<<"no"<<endl;
}
}
else
{
cout<<"no"<<endl;
}
}

}

发表于 2022-02-09 20:24:58 回复(0)

原果

num = int(input())
list = [] def f(_list,k):
    _max = max(_list)
    others = [] for e in _list: if e[1] != _max[1]:
            others.append(e[0])
    sum = _max[0] - others[0]
    sum += _max[0] - others[1]
    x = k - sum if x >= 0 and int(x) % 3 == 0: return True  else: return False for i in range(num):
    list.append([int(e) for e in input().split(' ')]) for row in list:
    n = row[0]
    _k = row[0] - row[1]
    k = row[1]
    d_1 = row[2]
    d_2 = row[3]
    is_ok = False  for flag in range(4):  if flag == 0:
            g_2 = (k+d_2-d_1)/3 
       if g_2 % 1 != 0 : continue    g_1 = g_2 + d_1
            g_3 = g_2 - d_2 if g_1 >= 0 and g_2 >= 0 and g_2 >= 0:
                is_ok = f([[g_1,0],[g_2,1],[g_3,2]],_k)  if is_ok == True:break 
       else: is_ok = False  if flag == 1:
            g_2 = (k+d_2+d_1)/3    if g_2 % 1 != 0 : continue 
       g_1 = g_2 - d_1
            g_3 = g_2 - d_2 if g_1 >= 0 and g_2 >= 0 and g_2 >= 0:
                is_ok = f([[g_1,0],[g_2,1],[g_3,2]],_k)  if is_ok == True:break  else: is_ok = False  if flag == 2:
            g_2 = (k-d_2-d_1)/3    if g_2 % 1 != 0 : continue 
      g_1 = d_1 + g_2
            g_3 = d_2 + g_2 if g_1 >= 0 and g_2 >= 0 and g_2 >= 0:
                is_ok = f([[g_1,0],[g_2,1],[g_3,2]],_k)  if is_ok == True:break  else: is_ok = False  if flag == 3:
            g_2 = (k-d_2+d_1)/3 
       if g_2 % 1 != 0 : continue    g_1 = g_2 - d_1
            g_3 = g_2 + d_2 if g_1 >= 0 and g_2 >= 0 and g_2 >= 0:
                is_ok = f([[g_1,0],[g_2,1],[g_3,2]],_k)  if is_ok == True:break  else: is_ok = False   if is_ok == True:  print('yes')  else:  print('no')

发表于 2018-08-12 22:59:27 回复(0)

牛客1659416

首先对给定的n,k,d1,d2，只有当n能被3整除时最终才可能分数打平，然后(x1，x2，x3)的取值只可能是出自(x2-d1，x2-d2，x2)、(x2，x2+d1，x2+d2)，(x2-d1，x2，x2+d2)和(x2-d2，x2，x2+d1)这四个，验证这四个值即可得到(x1，x2，x3)的值，然后计算c=max(x1，x2，x3)-min(x1，x2，x3)+max(x1，x2，x3)-submin(x1，x2，x3)，这里submin表示第二小的，c即为让最小的两个分数和最大的分数持平需要的最少场数。

只有当n-k-c>=0且n-k-c能被3整除时最终才可能分数打平。


	#include <iostream>



	usingnamespacestd;



	intmain()



	{



	    int t;



	    while( cin>>t )



	    {



	        long long n,k,d1,d2;



	        for(int q=0; q<t; q++)



	        {



	            cin >> n >> k >> d1 >> d2;



	            int yes=0;



	            int sign=0;



	            int c=0;



	            if(n%3==0)



	            {



	                if((k+d1+d2)%3==0 && (k+d1+d2)/3<=k && (k+d1+d2)/3-d1>=0 && (k+d1+d2)/3-d2>=0 )



	                {



	                    c=d1+d2;



	                    sign=1;



	                }



	                else if((k-d1-d2)%3==0 && k-d1-d2>=0 && (k-d1-d2)/3+d1<=k && (k-d1-d2)/3+d2<=k )



	                {



	                    if(d2>=d1)



	                        c=d2+d2-d1;



	                    else



	                        c=d1+d1-d2;



	                    sign=1;



	                }



	                else if((k+d1-d2)%3==0 && k+d1-d2>=0 && (k+d1-d2)/3<=k && (k+d1-d2)/3-d1>=0 && (k+d1-d2)/3+d2<=k )



	                {



	                    c=d2+d1+d2;



	                    sign=1;



	                }



	                else if((k-d1+d2)%3==0 && k-d1+d2>=0 && (k-d1+d2)/3<=k && (k-d1+d2)/3-d2>=0 && (k-d1+d2)/3+d1<=k)



	                {



	                    c=d1+d2+d1;



	                    sign=1;



	                }



	            }



	            if(sign==1 && n-k-c>=0)



	            {



	                if((n-k-c)%3==0)



	                    yes=1;



	            }



	            if(yes==1)



	                cout << "yes"<< endl;



	            else



	                cout << "no"<< endl;



	        }



	    }



	    return 0;



	}