ZYB's Game(博弈)

ZYB's Game

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 190    Accepted Submission(s): 162

Problem Description

ZYB played a game named NumberBomb with his classmates in hiking:a host keeps a number in [1,N] in mind,then 
players guess a number in turns,the player who exactly guesses X loses,or the host will tell all the players that
the number now is bigger or smaller than X.After that,the range players can guess will decrease.The range is [1,N] at first,each player should guess in the legal range.

Now if only two players are play the game,and both of two players know the X,if two persons all use the best strategy,and the first player guesses first.You are asked to find the number of X that the second player
will win when X is in [1,N].

 

Input

In the first line there is the number of testcases T.

For each teatcase:

the first line there is one number N.

1≤T≤100000,1≤N≤10000000

 

Output

For each testcase,print the ans.

 

Sample Input

1 3

 

Sample Output

1

 题意：一个游戏，让你在一定范围内猜数X，起始范围是【1，N】随着猜，裁判会告诉你大了还是小了，范围会逐渐减小；

假设猜之前两个人都知道了这个数X，谁猜到，谁就输了，给你一个N让求有多少个X会让后者赢；

方法：要想让第二个人赢，第二个人走的最优方法是第一个人每走一个点，第二个人要走关于x对称的点，所以只有N是奇数的时候，第二个人才会赢，而赢的点就是（1+N）/2；

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
int main(){
	int x,T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&x);
	if(x&1)puts("1");
	else puts("0");	
	}
		return 0;
}