首页 > 试题广场 >

编程题1

[编程题]编程题1

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

算法知识视频讲解

Python

jiarenyf

设三只队伍各赢了x1、x2、x3场，列如下方程（其中a,b = ±1）：

x1 - x2 = a*d1
x2 - x3 = b*d2
x1 + x2 + x3 = k

可得解为：

x1 = (k + 2*a*d1 + 1*b*d2) / 3
x2 = (k - 1*a*d1 + 1*b*d2) / 3
x3 = (k - 1*a*d1 - 2*b*d2) / 3

将a,b遍历，再做如下筛选，即可得到各支队伍赢的场数：
not x.is_integer() or x < 0 or x > k

根据题意，再做简单判断即可得到最终答案，完整代码如下：

def temp(k, d1, d2):
    def helper(a, b):
        x1 = (k + 2*a*d1 + 1*b*d2) / 3
        x2 = (k - 1*a*d1 + 1*b*d2) / 3
        x3 = (k - 1*a*d1 - 2*b*d2) / 3
        return x1, x2, x3
    results = []
    for a in [1, -1]:
        for b in [1, -1]:
            x1, x2, x3 = helper(a, b)
            isOK = True
            for x in [x1, x2, x3]:
                if not x.is_integer() or x < 0 or x > k:
                    isOK = False
            if isOK:
                results.append((x1,x2,x3))
    return results

num = int(raw_input())
for i in xrange(num):
    line = raw_input()
    n, k, d1, d2 = map(float, line.strip().split())
    if n % 3 != 0:
        print 'no'
        continue
    results = temp(k, d1, d2)
    if len(results) == 0:
        print 'no'
        continue
    isOK = False
    for result in results:
        x = max(result)
        if x <= n / 3:
            isOK = True
            break
    if isOK:
        print 'yes'
    else:
        print 'no'

编辑于 2017-12-26 20:52:11 回复(0)

想在家办公的打工鸭爱读书

function main(n, k, d1, d2) {

    var res = calcXYZ(k, d1, d2, 1, 1)
    if (test()) {
        return true
    }
    var res = calcXYZ(k, d1, d2, 1, -1)
    if (test()) {
        return true
    }
    var res = calcXYZ(k, d1, d2, -1, 1)
    if (test()) {
        return true
    }

    var res = calcXYZ(k, d1, d2, -1, -1)
    if (test()) {
        return true
    }
    return false

    function test() {
        if (res === false) return false
        var arr = [res.x, res.y, res.z]
        arr.sort(function(a, b) {
            return a - b
        })
        var min = arr[0]
        var mid = arr[1]
        var max = arr[2]

        var distance = max - min + max - mid
        var remain = n - k
        if ((remain - distance >= 0) && (remain - distance) % 3 === 0) {
            return true
        } else {
            return false
        }
    }
}



function calcXYZ(k, d1, d2, isXMoreThanY, isYMoreThanZ) {
    var x = y + isXMoreThanY * d1
    var y = (k + isYMoreThanZ * d2 - isXMoreThanY * d1) / 3
    var z = y - isYMoreThanZ * d2

    if (!isNotNegativeInteger(x) || !isNotNegativeInteger(x) || !isNotNegativeInteger(x)) {
        return false
    } else {
        return {
            x: x,
            y: y,
            z: z
        }
    }
}
//是否为非负整数 
function isNotNegativeInteger(num) {
    if (typeof(num) !== "number") return false
    if (num < 0) return false
    if (num % 1 !== 0) return false
    return true
}

var num = parseInt(readline())
for (var x = 0; x < num; x++) {
    var arr = readline().split(" ")
    for (var i = 0; i < arr.length; i++) {
        arr[i] = parseInt(arr[i])
    }
    var out = main(arr[0], arr[1], arr[2], arr[3])
    if (out) {
        console.log("yes")
    } else {
        console.log("no")
    }
}

发表于 2018-08-10 15:27:54 回复(0)

unnino

let t=parseInt(readline());
for(let i=0;i<t;i++){

let result='no';

let [n,k,d1,d2]=readline().split(' ').map(x=>parseInt(x));//解构赋值的方式获得n,k,d1,d2

//1,2,3号球队的得分关系有4种情况，1>2>3,1>2<3,1<2>3,1<2<3,分别求3种情况下至少还要多少球才能打平

let c0=d1+d1+d2;//至少需要多少球才能打平

let e0=d1+d2+d2;//至少需要多少球才能打成现在的情况

let c1=d2>d1?d2+d2-d1:d1+d1-d2;

let e1=d1+d2;

let c2=d1+d2;

let e2=d2>d1?d2+d2-d1:d1+d1-d2;

let c3=d1+d2+d2;

let e3=d1+d1+d2;

let scoreNeed=[c0,c1,c2,c3];

let kAtLeast=[e0,e1,e2,e3];

let possibleCases=[];//4种情况中可能出现的情况

for(let j=0;j<4;j++){

if(k>=kAtLeast[j]&&(k-kAtLeast[j])%3===0){

possibleCases.push(j);

}

}

for(let h of possibleCases){

if(n-k>=scoreNeed[h]&&(n-k-scoreNeed[h])%3===0){

result='yes';

break;

}

}

console.log(result);

}

编辑于 2019-03-10 21:44:28 回复(0)

jmfang

#include<stack>
#include<vector>
#include<algorithm>
#include<iostream>
#include<stdio.h>
using namespace std;

/*
x1 - x2 = a*d1
x2 - x3 = b*d2
x1 + x2 + x3 = k
solve
x1 = (k + 2*a*d1 + d*d2)/3
x2 = (k + b*d2 - a*d1)/3
x3 = (k - 2b*d2 - a*d1)/3
*/
vector<int> sort123(int a, int b, int c) {
    vector<int> res;
    res.push_back(a);
    res.push_back(b);
    res.push_back(c);
    sort(res.begin(), res.end());
    return res;
}
bool valid(int a, int b, int c, int k) {
    if(a >= 0 && b >= 0 && c >= 0 && a <= k && b <= k && c <= k) {
        if(a + b + c == k) {
            if((a - (int)a == 0) && (b - (int)b == 0 && c - (int)c == 0)) {
                return true;
            }
        }
    }
    return false;
}
int main() {
    float x1, x2, x3;
    int a, b;
    int as[2] = {1, -1};
    int bs[2] = {1, -1};
    int t, n, k, d1, d2;
    bool flag = false;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d%d%d", &n, &k, &d1,&d2);
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 2; j++) {
                a = as[i];
                b = bs[j];
                x1 = (k + 2*a*d1 + b*d2)*1.0/3;
                x2 = (k + b*d2 - a*d1)*1.0/3;
                x3 = (k - 2*b*d2 - a*d1)*1.0/3;

                if(valid(x1, x2, x3, k)) {
                    //cout << "t:" << t << " " << x1 << " " << x2 << " " << x3 << endl;
                    if(n == k) {
                        if( x1 == x2 && x2 == x3) flag = true;
                        else flag = false;
                    } else {
                        //对 x1 x2 x3排序，分别求出第二第三与第一的差距
                        int r = (n - k) % 3;
                        vector<int> v = sort123(x1, x2, x3);
                        int r1 = v[2] - v[1];
                        int r2 = v[2] - v[0];
                        if(n-k >= r1+r2) {
                            int r3 = n-k - r1 - r2;
                            if(r3 % 3 == 0) flag = true;
                            else flag = false;
                        } else {
                            flag = false;
                        }
                    }
                }

            }
        }
        if(flag) cout << "yes" << endl;
        else cout << "no" <<endl;
    }
}

下面的测试case 不能通过，求高人指点

124272371505 14857869176 3504489017 5415377887
444050665588 203397123071 47794909135 42499609248
335265500614 163750570012 61911921323 15109080991
450754198180 104339494534 94127327352 1058880080
542466530501 404970527310 258843105264 215354440674
77835122322 43362966016 15047129062 4559565552
*/

发表于 2018-03-21 22:13:27 回复(0)