Friends and Enemies HDU - 5874（思維）

Friends and Enemies HDU - 5874

On an isolated island, lived some dwarves. A king (not a dwarf) ruled the island and the seas nearby, there are abundant cobblestones of varying colors on the island. Every two dwarves on the island are either friends or enemies. One day, the king demanded that each dwarf on the island (not including the king himself, of course) wear a stone necklace according to the following rules:

  For any two dwarves, if they are friends, at least one of the stones from each of their necklaces are of the same color; and if they are enemies, any two stones from each of their necklaces should be of different colors. Note that a necklace can be empty.

  Now, given the population and the number of colors of stones on the island, you are going to judge if it's possible for each dwarf to prepare himself a necklace. 
           

Input

Multiple test cases, process till end of the input.

For each test case, the one and only line contains 2 positive integers M,N (M,N<231)
representing the total number of dwarves (not including the king) and the number of colors of stones on the island.
           

Output

For each test case, The one and only line of output should contain a character indicating if it is possible to finish the king’s assignment. Output

T" (without quotes) if possible,

F” (without quotes) otherwise.

Sample Input

20 100
           

Sample Output

T
           

題意：

說一個島上有m個人，n種石頭，兩個人見面要麼是朋友要麼是敵人，是朋友的要求是兩個矮人的身上的項鍊上至少有一個石頭的顔色相同，是敵人的要求就是兩個矮人的身上沒有石頭顔色相同。問給出m，n的值，能否滿足使得兩個人見面要麼是敵人要麼是朋友的條件。

思路：

1、其實題意隐晦成這個樣子：就是讓你将m個人分成兩個部落，使得部落之内都是朋友，部落之間是敵人。

2、那麼最壞的條件就是将m個人分成兩個部落，每個部落m/2個人。那麼滿足兩兩之間見面都有關系，那麼需要 m2⋅m2條邊，也就是需要m24 m 2 ⋅ m 2 條 邊 ， 也 就 是 需 要 m 2 4 種石頭。

按照上述判斷一下即可。

code:

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n,m;
    while(~scanf("%lld%lld",&m,&n)){
        if(m * m /  > n) printf("F\n");
        else printf("T\n");
    }
    return ;
}