【HDU - 5882】Balanced Game （找规律，思维）

题干：

Rock-paper-scissors is a zero-sum hand game usually played between two people, in which each player simultaneously forms one of three shapes with an outstretched hand. These shapes are "rock", "paper", and "scissors". The game has only three possible outcomes other than a tie: a player who decides to play rock will beat another player who has chosen scissors ("rock crushes scissors") but will lose to one who has played paper ("paper covers rock"); a play of paper will lose to a play of scissors ("scissors cut paper"). If both players choose the same shape, the game is tied and is usually immediately replayed to break the tie. 

Recently, there is a upgraded edition of this game: rock-paper-scissors-Spock-lizard, in which there are totally five shapes. The rule is simple: scissors cuts paper; paper covers rock; rock crushes lizard; lizard poisons Spock; Spock smashes scissors; scissors decapitates lizard; lizard eats paper; paper disproves Spock; Spock vaporizes rock; and as it always has, rock crushes scissors. 

Both rock-paper-scissors and rock-paper-scissors-Spock-lizard are balanced games. Because there does not exist a strategy which is better than another. In other words, if one chooses shapes randomly, the possibility he or she wins is exactly 50%50% no matter how the other one plays (if there is a tie, repeat this game until someone wins). Given an integer NN, representing the count of shapes in a game. You need to find out if there exist a rule to make this game balanced.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow. 
For each test case, there is only one line with an integer N (2≤N≤1000)N (2≤N≤1000), as described above. 

Here is the sample explanation. 

In the first case, donate two shapes as A and B. There are only two kind of rules: A defeats B, or B defeats A. Obviously, in both situation, one shapes is better than another. Consequently, this game is not balanced. 

In the second case, donate two shapes as A, B and C. If A defeats B, B defeats C, and C defeats A, this game is balanced. This is also the same as rock-paper-scissors. 

In the third case, it is easy to set a rule according to that of rock-paper-scissors-Spock-lizard.

Output

For each test cases, output "Balanced" if there exist a rule to make the game balanced, otherwise output "Bad".

Sample Input

3
2
3
5

Sample Output

Bad
Balanced
Balanced

题目大意：

剪刀石头布（这三种操作）会使得每个人都有50%的胜率（如果两人操作相同则重新这一回合）

现在已知有n种操作，问这n种操作能否使得每种操作的胜率为50%。

解题报告：

如果把操作看成点，之间的关系看成边，那么在剩余n-1个顶点中需要有一半指向自己，一半由自己指向，所以n-1需要是偶数，n需要是奇数，由此得到了一个可以输出Balanced的必要条件（也就是如果要是Balance的，那就必须n是奇数）。

现在来证明n是奇数，那么一定能构造出来一个Balance的解，也就是充分条件（wjh大佬tql）。（因为每两个顶点之间只能有一条有向边(因为不可能我比你强的同时你也比我强)所以有可能构造不出来，所以需要证明一定可以构造出来）对于n个操作的，自然不好构造，但是我们可以用数学归纳法类似的思想，由小及大。对于三个操作的，比如石头剪刀布，一定可以构造吧，然后在此基础上加两个顶点，那么这两个顶点和那三个顶点之间没有任何关系（可以随意连边），所以我们：这两个顶点之间连一条边（谁到谁的都行），然后这两个点和剩下的顶点根据情况连边一定可以构造出来。以此往复，就可以构造出来任意奇数个操作的可行解了。重点就是已知三个点是可以构造的，然后依次加两个点也能构造，然后就可以证明了。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;

int main()
{
	int t,n;
	cin>>t;
	while(t--) {
		scanf("%d",&n);
		if(n % 2 == 1) {
			puts("Balanced");
		}
		else puts("Bad");
	}
	return 0 ;
}