HDU 5882.Balanced Game(2016 ACM/ICPC Asia Regional Qingdao Online)

280

题目


Description  


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% no matter how the other one plays (if there is a tie, repeat this game until someone wins). Given an integer N, 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), 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



题解



判断出任意一个手势,赢的概率和输的概率是否一样
  • 如果只有两个手势,有关系 A→B ,则出 A 必赢(不输)
  • 如果有三个手势或五个手势,出任意一个手势赢的概率都是 50%

画成图像,可以看作对于每个结点,入度等于出度

如果总结点数为偶数,则对于任意一个结点,除它之外只能有奇数个结点,也即不可能入度等于出度
而如果结点数为奇数,根据贪心可以确保每一个的入度都为出度

也即这道题的任务是判断 n 是奇数还是偶数


代码


/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリ0隶�
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

typedef long long LL;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;


void Do() {
    int n;
    cin >> n;
    if(n & 1)
        cout << "Balanced" << endl;
    else
        cout << "Bad" << endl;
}


int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    int T;
    cin >> T;

    while(T--)
        Do();

    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论