Codeforce 1040A Diagonal Walking v.2 (思维) No.14

Diagonal Walking v.2

传送
Mikhail walks on a Cartesian plane. He starts at the point
(0,0), and in one move he can go to any of eight adjacent points. For example, if Mikhail is currently at the point (0,0), he can go to any of the following points in one move:(1,0);(1,1);(0,1);(−1,1);(−1,0);(−1,−1);(0,−1);(1,−1)

If Mikhail goes from the point (x1,y1) to the point (x2,y2) in one move, and x1≠x2 and y1≠y2, then such a move is called a diagonal move.

Mikhail has q queries. For the i-th query Mikhail’s target is to go to the point (ni,mi) from the point (0,0) in exactly ki moves. Among all possible movements he want to choose one with the maximum number of diagonal moves. Your task is to find the maximum number of diagonal moves or find that it is impossible to go from the point
(0,0） to the point (ni,mi) in ki moves.

Note that Mikhail can visit any point any number of times (even the destination point!).

Input

The first line of the input contains one integer q (1≤q≤10^4) — the number of queries.

Then q lines follow. The i-th of these q lines contains three integers ni, mi and ki (1≤ni,mi,ki≤1018) — x-coordinate of the destination point of the query, y
-coordinate of the destination point of the query and the number of moves in the query, correspondingly.

Output

Print q integers. The i-th integer should be equal to -1 if Mikhail cannot go from the point (0,0) to the point (ni,mi) in exactly ki moves described above. Otherwise the i-th integer should be equal to the the maximum number of diagonal moves among all possible movements.

Example

input

3
4 3 7
10 1 9

output

1
6
-1

Note

One of the possible answers to the first test case: (0,0)→(1,0)→(1,1)→(2,2).

One of the possible answers to the second test case: (0,0)→(0,1)→(1,2)→(0,3)→(1,4)→(2,3)→(3,2)→(4,3).

In the third test case Mikhail cannot reach the point
(10,1) in 9 moves.

---

题目大意:

你可以移动到周围8个点，斜着跳算超级跳。
你必须在准确k步走到规定的(n,m),请问最多能跳几次超级跳？
ps：每个点可以用无数次

题解：

经过我多次瞎试，发现转圈大法，先尽力斜着到终点，横着走就用波浪代替，然后剩余步数在终点附近转圈。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,x,y,k,ans,res;
int q;
int main(){
	cin>>q;
	while(q--){
		cin>>n>>m>>k;
		ans=0;res=k;
		if(n<m){
			swap(n,m);
		} 
		long long t=n-m;
		ans+=m;res-=m;
		x+=m,y+=m;
		if(t==0){
			if(res<0){
				cout<<-1<<endl;
				continue;
			}
			else if(res==0){
				cout<<ans<<endl;
				continue;
			}
			else if(res==1){
				cout<<ans-1<<endl;
				continue;
			}
			else if(res%2==0){
				cout<<ans+res<<endl;
				continue;
			}
			else if(res%2==1){
				ans+=res-2;
				cout<<ans<<endl;
				continue;
			}
		}
		else if(t%2==1){
			if(res<=0){
				cout<<-1<<endl;
				continue;
			}
			ans+=t-1;res-=t-1;
			if(res<=0){
				cout<<-1<<endl;
				continue;
			}
			else if(res==1){
				cout<<ans<<endl;
				continue;
			}
			else if(res>0){
				ans+=res-1;
				cout<<ans<<endl;
				continue;
			}
		} 
		else if(t%2==0){
			if(res<=0){
				cout<<-1<<endl;	
				continue;
			}
			ans+=t;res-=t;
			if(res<0){
				cout<<-1<<endl;
				continue;
			}
			else if(res==0){
				cout<<ans<<endl;
				continue;
			}
			else if(res==1){
				cout<<ans-1<<endl;
				continue;
			}
			else if(res%2==0){
				cout<<ans+res<<endl;
				continue;
			}
			else if(res%2==1){
				ans+=res-2;
				cout<<ans<<endl;
				continue;
			}			
		}
	}
	return 0;
}