【HDU1538】A Puzzle for Pirates（经典的海盗问题）

【题目】

Description

A bunch of pirates have gotten their hands on a hoard of gold pieces and wish to divide the loot. They are democratic pirates in their own way, and it is their custom to make such divisions in the following manner: The fiercest pirate makes a proposal about the division, and everybody votes on it, including the proposer. If 50 percent or more are in favor, the proposal passes and is implemented forthwith. Otherwise the proposer is thrown overboard, and the procedure is repeated with the next fiercest pirate. 
All the pirates enjoy throwing one of their fellows overboard, but if given a choice they prefer cold, hard cash, the more the better. They dislike being thrown overboard themselves. All pirates are rational and know that the other pirates are also rational. Moreover, no two pirates are equally fierce, so there is a precise pecking order ― and it is known to them all. The gold pieces are indivisible, and arrangements to share pieces are not permitted, because no pirate trusts his fellows to stick to such an arrangement. It's every man for himself. Another thing about pirates is that they are realistic. They believe 'a bird in the hand is worth two in the bush' which means they prefer something that is certain than take a risk to get more, where they might lose everything. 

For convenience, number the pirates in order of meekness, so that the least fierce is number 1, the next least fierce number 2 and so on. The fiercest pirate thus gets the biggest number, and proposals proceed in the order from the biggest to the least. 

The secret to analyzing all such games of strategy is to work backward from the end. The place to start is the point at which the game gets down to just two pirates, P1 and P2. Then add in pirate P3, P4, ... , one by one. The illustration shows the results when 3, 4 or 5 pirates try to divide 100 pieces of gold. 



Your task is to predict how many gold pieces a given pirate will get.

Input

The input consists of a line specifying the number of testcases, followed by one line per case with 3 integer numbers n, m, p. n (1 ≤ n ≤ 10^4) is the number of pirates. m (1 ≤ m ≤ 10^7) is the number of gold pieces. p (1 ≤ p ≤ n) indicates a pirate where p = n indicates the fiercest one. 

Output

The output for each case consists of a single integer which is the minimal number of gold pieces pirate p can get. For example, if pirate p can get 0 or 1 gold pieces, output '0'. If pirate p will be thrown overboard, output 'Thrown'. 

Sample Input

3 3 100 2 4 100 2 5 100 5

Sample Output

0 1 98

【题意】

这是一个经典问题，有n个海盗，分m块金子，其中他们会按一定的顺序提出自己的分配方案，如果50%以上的人赞成，则方案通过，开始分金子，如果不通过，则把提出方案的扔到海里，下一个人继续。

【分析】

自己先从小到大玩一遍这个游戏，就能找到一些规律。

　　分够贿赂和不够贿赂两种情况。抓特点：一个人如果将要死，他会支持前面的人保证自己不死。如果能得到更多的钱，他会更加支持。如果得到同样的钱，他乐于把前面的人扔下水。对于

够钱贿赂的情况，他会给与自己同奇偶的人。这样票数也够，他也会支持你。（具体为什么思考一下就知道了）。对于不够钱贿赂，要考虑到人不希望死这个情况，找到规律，决策者总是

2*m+2^k(k为任意整数)，可是他具体贿赂谁是不确定的，所以除了一些在前面的必死的人，其他人的ans都为0。

　　具体看大神blog：http://blog.csdn.net/acm_cxlove/article/details/7853916

 

代码如下：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 1010

void ffind(int x,int y,int z)
{
    if(x<=2*y+1)
    {
        if(z==x) printf("%d\n",y-(x-1)/2);
        else if((x-z)%2==0) printf("1\n");
        else printf("0\n");
    }
    else
    {
        int mx;
        for(int i=0;(2*y)+(1<<i)<=x;i++) mx=2*y+(1<<i);
        if(z>mx) printf("Thrown\n");
        else printf("0\n");
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,p;
        scanf("%d%d%d",&n,&m,&p);
        ffind(n,m,p);
    }
    return 0;
}

 

2016-04-25 13:21:52