首页 > 试题广场 >

编程题1

[编程题]编程题1

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

算法知识视频讲解

gq97

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
bool judge(ll n, ll k, ll d1, ll d2) {
    if(n % 3 != 0) return false;
    ll residue = n-k;
    for(int i = 0; i<2; i++) {
        d1 = -d1;
        for(int j = 0; j<2; j++) {
            d2 = -d2;
            vector<ll> v;
            v.push_back(d1);
            v.push_back(d2);
            v.push_back(0);
            sort(v.begin(), v.end());
            while(v[0] < 0) {
                v[1]+=-v[0], v[2]+=-v[0];
                v[0]+=-v[0];
            }
            if(v[2]+v[2]+v[2] > n) continue;
            ll tem = 2*v[2]-v[0]-v[1];
            if(residue >= tem) {
                if((residue-tem) % 3 == 0) return true;
            }
        }
    }
    return false;
}
int main() {
    //freopen("in.txt", "r", stdin);
    int t;
    cin >> t;
    ll n, k, d1, d2;
    for(int i = 0; i<t; i++) {
        cin >> n >> k >> d1 >> d2;
        judge(n, k, d1, d2) ? cout << "yes\n" : cout << "no\n";
    }
    return 0;
}

编辑于 2019-03-15 22:05:55 回复(0)

FlushHip

今日头条2018校园招聘后端开发工程师(第四批)编程题 - 题解
http://blog.csdn.net/flushhip/article/details/79458502
详细解答，没有之一(自吹一波)

源码：https://github.com/FlushHip/AlgorithmnCode

发表于 2018-03-06 17:43:09 回复(1)

元暗

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for (int i = 0; i < t; i++) {
            long n = scanner.nextLong();
            long k = scanner.nextLong();
            long d1 = scanner.nextLong();
            long d2 = scanner.nextLong();

            if (n % 3 != 0) {
                System.out.println("no");
                continue;
            }
            //如果能完成，每个队伍的最后得分为res
            long res = n / 3;
            //执行完k次可能有4种情况，求出这4种情况是否可能出现
            long[][] dir = new long[][]{{d1, d2}, {d1, -d2}, {-d1, d2}, {-d1, -d2}};
            boolean finished = false;
            for (int j = 0; j < 4; j++) {
                if ((k - dir[j][0] - dir[j][1]) % 3 == 0) {
                    //执行完k次 第2只队伍的得分
                    long second = (k - dir[j][0] - dir[j][1]) / 3;
                    //求出当前k次执行完的情况是否可能出现
                    if (second >= 0 && second + dir[j][0] >= 0 && second + dir[j][1] >= 0) {
                        //当前每个组的分数不能比最终的结果高
                        if (res >= second && res >= dir[j][0] + second && res >= dir[j][1] + second) {
                            finished = true;
                            break;
                        }

                    }
                }
            }
            if (finished) {
                System.out.println("yes");
            } else {
                System.out.println("no");
            }

        }
        scanner.close();


    }

发表于 2019-10-10 22:23:23 回复(1)

offer一生一起走

t = int(input())

for i in range(t):
    (n, k, d1, d2) = [int(i) for i in input().split()]
    # print((n,k,d1,d2))

    if n % 3 != 0 :
        print("no")
        continue
    #只需保证n能被3整除，而且四种情况有一种满足，则一定能够打平
    k1, k2, k3, k4 = k - d1 + d2, k - d1 -d2, k + d1 + d2, k + d1 - d2
    # first > second, second > third
    if k1 >= 0 and k1 % 3 == 0:
        second = k1 / 3
        first = second + d1
        third = second - d2
        if min(first,second,third) >= 0 and max(first,second,third) <= n/3:
            print("yes")
            continue
    # first > second, second < third
    if k2 >= 0 and k2 % 3 == 0:
        second = k2 / 3
        first = second + d1
        third = second + d2
        if min(first,second,third) >= 0 and max(first,second,third) <= n/3:
            print("yes")
            continue

    # first < second, second > third
    if k3 >= 0 and k3 % 3 == 0:
        second = k3 / 3
        first = second - d1
        third = second - d2
        if min(first,second,third) >= 0 and max(first,second,third) <= n/3:
            print("yes")
            continue

    # first < second, second < third
    if k4 >= 0 and k4 % 3 == 0:
        second = k4 / 3
        first = second - d1
        third = second + d2
        if min(first,second,third) >= 0 and max(first,second,third) <= n/3:
            print("yes")
            continue
    
    print("no")

发表于 2023-08-15 19:25:58 回复(0)

wonderson

刚开头一直不懂6 3 3 0为什么是no；
只要a = 0, b = c = 3, 不就是对的吗？
后来突然发现， a + b + c > k.....

import java.util.*;
public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int T = sc.nextInt();
            loop: for (int i = 0; i < T; i++) {
                long n = sc.nextLong(), k = sc.nextLong(), d1 = sc.nextLong(), d2 = sc.nextLong();
                long[] add = {1L, -1L};

                if (n % 3 != 0) {
                    System.out.println("no");
                    continue;
                }

                for (int j = 0; j < 2; j++) {
                    for (int t = 0; t < 2; t++) {
                        long a = 0, b = add[j] * d1, c = b + add[t] * d2;
                        long sum = a + b + c;
                        if (sum > k) {
                            continue;
                        }
                        long m = n - k;
                        long max = Math.max(a, Math.max(b, c));
                        long min = max * 3;

                        min -= sum;
                        if (m < min) {
                            continue;
                        }
                        m -= min;

                        if (m % 3 == 0) {
                            System.out.println("yes");
                            continue loop;
                        }
                    }
                }
                System.out.println("no");
            }
            sc.close();
        }
    }

发表于 2022-04-09 15:04:17 回复(0)

Gelivabilities

有点奇葩的贪心算法，只要剩余n-k场能补全，各种看能不能对3取模就行了，我是对测试用例各种试出来的。精简后10行代码搞定

import sys
while True:
    s=sys.stdin.readline().strip()
    if len(s)==0:break
    for i in range(int(s)):
        [n,k,d1,d2]=[int(x) for x in input().split()]
        max_left_1,max_left_2,min_left=2*d1+d2,2*d2+d1,d1+d2
        if n-k<=min_left:print('yes' if min_left==0 else 'no')
        elif not (k-2*d2+d1)%3==0 and not (k-max_left_1)%3==0 and not (k-max_left_2)%3==0: print('no')
        else: print('yes' if n%3==0 else 'no')

编辑于 2019-08-04 12:58:44 回复(0)

世茅

# python3.5

def main(n, k, d1, d2):
    if n%3 == 0 and d1 <= n/3 and d2 <= n/3:
        if d1 >= d2:
            if (n-k-(d1+d1+d2))%3 == 0 and (n-k-(d1+d1+d2)) >= 0:
                print("yes")
            elif (n-k-(d1+d1-d2))%3 == 0 and (n-k-(d1+d1-d2)) >= 0:
                print("yes")
            elif (n-k-(d1+d2))%3 == 0 and (n-k-(d1+d2)) >= 0:
                print("yes")
            else:
                print("no")
            
        elif d1 <= d2:
            if (n-k-(d2+d2-d1))%3 == 0 and (n-k-(d2+d2-d1)) >= 0:
                print("yes")
            elif (n-k-(d2+d2+d1))%3 == 0 and (n-k-(d2+d2+d1)) >= 0:
                print("yes")
            elif (n-k-(d1+d2))%3 == 0 and (n-k-(d1+d2)) >= 0:
                print("yes")
            else:
                pirnt("no")
                
    else:
        print("no")
         
if __name__ == "__main__":
    t = int(input())
    for i in range(t):
        data = list(map(int, input().split()))
        main(data[0], data[1], data[2], data[3])

编辑于 2019-04-13 08:20:04 回复(0)

维恰尔。

python2 ac:

def solution(n, k, d1, d2):     r1, r2, r3, r4 = k - 2 * d1 - d2, k - 2 * d1 + d2, k + 2 * d1 - d2, k + 2 * d1 + d2     if r1 >= 0 and r1 % 3 == 0:         remain = n - k - d1 - 2 * d2         if remain >=0 and remain % 3 == 0:             return 'yes'     if r2 >= 0 and r2 % 3 == 0:         remain = n - k - d1 - d2         if remain >=0 and remain % 3 == 0:             return 'yes'     if r3 >= 0 and r3 % 3 == 0:         remain = n - k - 2 * d1 + d2         if remain >=0 and remain % 3 == 0:             return 'yes'     if r4 >= 0 and r4 % 3 == 0:         remain = n - k - 2 * d1 - d2         if remain >=0 and remain % 3 == 0:             return 'yes'     return 'no'

t = input()
for i in range(0, t):     nums = raw_input()     n, k, d1, d2 = [int(x) for x in nums.split(' ') if x != '']     print solution(n, k, d1, d2)

发表于 2018-04-14 17:33:05 回复(0)

提交观点

问题信息

贪心 C++工程师 2018 字节跳动数学 Java工程师

上传者：小小

难度：

8条回答 49收藏 2207浏览

通过挑战的用户

Kaiisann

2023-01-06 10:07:04
牛客71385...

2022-11-24 21:43:04
ling2

2022-11-01 14:56:42
牛客72027...

2022-10-08 19:23:17
小丸子呢

2022-10-03 21:01:05

编程题1

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题