首页 > 试题广场 >

走斜线

[编程题]走斜线
  • 热度指数：470 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有天他来到一张方格地图上，整张地图可以看做一个二维坐标轴。牛牛此刻处于原点（0,0），他想要到点（x,y）去。

牛牛有强迫症，他规定自己必须恰好k步走到点(x,y)，中途可以经过任何点包括（x,y），但是第k步一定要到达（x,y）。

一步有八种走法，直线东（+1,0）南（0,-1）西（-1,0）北（0,+1），斜线东南（+1,-1）东北（+1,+1）西南（-1,-1）西北（-1,+1）。

牛牛会在能k步到达目的地的基础下尽量走斜线，你能计算出牛牛到底走了多少条斜线吗？

输入描述:
第一行一个整数T，代表数据组数。
每组数据给出三个整数x，y，k。


输出描述:
对于每组数据，单独一行输出一个整数。
如果牛牛可以在第k步的时候到达(x,y)，输出牛牛走的斜线数量。
如果牛牛不能到达，输出-1。
示例1

输入

2
2 3 4
7 7 9

输出

3
9
示例2

输入

1
1 2 1

输出

-1

备注:
对于100%的数据，1<=T<=1000，1<=x，y，k<=1000000000000000000。
算法知识视频讲解
添加回答
kyzheng头像 kyzheng 
# Python版本，通过所有算例，供参考
def judge(x, y, k):
    x = abs(x)
    y = abs(y)

    if k < max(x, y):
        return -1
    elif k == max(x, y):
        if (x+y) % 2 == 0:
            return k
        elif (x+y) % 2 == 1:
            return k-1
    elif k > max(x, y):
        if (k - max(x, y)) % 2 == 0:
            if (x + y) % 2 == 0:
                return k
            elif (x + y) % 2 == 1:
                return k - 1
        elif (k - max(x, y)) % 2 == 1:
            if (x + y) % 2 == 0:
                return k - 2
            elif (x + y) % 2 == 1:
                return k - 1

n = int(input())
a = [[] for i in range(n)]

for i in range(n):
    a[i] = input().split()

for i in range(n):
    for j in range(len(a[i])):
        a[i][j] = int(a[i][j])

for i in range(n):
    x = a[i][0]
    y = a[i][1]
    k = a[i][2]

    res = judge(x, y, k)

    print(res)
发表于 2022-03-11 23:08:17 回复(0)
清霜头像 清霜
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            for (int i = 0; i < n; i++) {
                long x = scanner.nextLong();
                long y = scanner.nextLong();
                long k = scanner.nextLong();
                long sum = x + y;
                long a = Math.max(x,y);
                if(a > k){
                    System.out.println(-1);
                    continue;
                }
                if(sum % 2 != 0){
                    System.out.println(k-1);
                }else{
                    long y1 = (k-a)%2;
                    if(y1!=0){
                        System.out.println(k-2);
                    }else{
                        System.out.println(k);
                    }
                }
            }
        }
    }
}
发表于 2020-04-19 19:31:17 回复(0)
黄色变白色头像 黄色变白色
#include<iostream>
#include<cmath>

using namespace std;

void countUnequal(long long int x,long long int y,long long int n) //x为目标点的最大值，y为小值 
{
    if((n-x) < 0) //步数太少，走不到目标点 
    {
        cout << "-1"<<endl;
        //这里一定要加返回值，留下了心酸的泪水 ，检查了好久逻辑问题，最后是这里的锅 
        return; 
    } 
    
    if((x-y)%2 == 0)  //走完(y,y)的正方形后还剩的步数为偶数
    {
        if((n -y)%2) 
        {
            cout << n - 2 << endl;
        } 
        else
        {
            cout << n << endl;
        }
    }
    else if((x-y)%2)//走完(y,y)的正方形后还剩的步数为奇数 
    {
        cout << n -1 << endl;
    }
}


void countMax(long long int x,long long int y,long long int n)
{
   if(x == y) //如果目标点的横轴等于纵轴,且不在原点 
   {
           if(n < y)
        {
            cout << "-1"<<endl;;
        }
        else if((n - y)%2 == 1)  
        {
            cout <<n - 2<<endl;;
        }
        else 
        {
            cout << n<<endl;
        }
   }
   else if(x > y)
      countUnequal(x,y,n);
   else if(x < y)
        countUnequal(y,x,n);      
}


int main()
{
    int t;
    long long int x,y,n;
    cin >> t;
    for(int i = 0;i < t;i++)
    {
        cin >> x>> y >> n;
        countMax(x,y,n); 
    }

    return 0;
}

发表于 2019-07-18 12:09:53 回复(0)
N_I头像 N_I 
#include<iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    while(n){
        long long int x, y, k;
        cin >> x >> y >> k;
        
        long long int max =  x < y?y:x;
        long long int min =  x > y?y:x;
        
        if (k < max){
        	cout << "-1" << endl;
		}else{
            long long int t = min + (max-min)/2*2;
            if((max-min)%2 == 0){
            	if((k - t)%2 == 0){
            		cout << k << endl;
				}else{
					cout << k - 2 << endl;
				}
			}else{
            	cout << k-1 << endl;
			}
        }
        n--;
    }
    return 0; 
}
一直没发通过测试，看了其他人的答案才发现int小了，存不下
发表于 2020-05-20 22:39:28 回复(0)
xxLilyxxZ头像 xxLilyxxZ 
#include <iostream>
using namespace std;
long long max(long long x, long long y){
	return x>y?x:y;
}
void getStep(long long x, long long y, long long k){
	long long minstep,remins;
    long long sum=x+y;
	if(sum%2==0){
		minstep=max(x,y);
		if(k<minstep)
			cout<<-1<<endl;
		else{
			remins=k-minstep;
			if(remins%2==0)
                cout<<k<<endl;     				
			else          
                cout<<k-2<<endl;       
		}
	}else{
		if(x>y)
			minstep=x-1;
		else
			minstep=y-1;
		if(k<minstep+1)
			cout<<-1<<endl;
		else
			cout<<k-1<<endl;
	}
	return;
}
int main(){
	long long t,x,y,k;
	cin>>t;
	while(t-->0){
		cin>>x>>y>>k;
		getStep(x,y,k);
	}
	return 0;
}

发表于 2020-02-20 21:26:48 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 数据库工程师 信息技术岗 贪心 区块链 模拟 测试开发工程师 2019 数学 大数据开发工程师 数据分析师 Java工程师 牛客
来自：2019校招-留学生招...
上传者：小小
难度：
5条回答 4834浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号