2013
12-12

# A Puzzle for Pirates

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.

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.

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’.

3
3 100 2
4 100 2
5 100 5

0
1
98
HintHint
The situation gets complicated when a few gold pieces were divided among many pirates. 

by—cxlove

http://acm.hdu.edu.cn/showproblem.php?pid=1538

### 金币数量的不确定性:由上面的推理可知, 当n=2m+2时, 上一轮推理没有分到金币的人的金币数量首次具有不确定性, 并且在n>2m+2时, 这种不确定性一定会延续下去, 轮到因为n号决策者之前的一个人决策时, 那个人肯定分不到金币了, 所以在上一轮推理中没有分到金币的人的个数一定大于m.

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
#define C    240
#define TIME 10
#define inf 1<<25
#define LL long long
using namespace std;
//保存2的幂
int fac[15]={2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
void slove(int n,int m,int p){
//金币够贿赂的情况
if(n<=2*m){
//不是决策者，而且奇偶性相同，都能被贿赂
if(n!=p&&(n%2==p%2))
printf("1\n");
//剩下的都是决策者拥有
else if(n==p)
printf("%d\n",m-(n-1)/2);
else
//其余人分不到金币，他们的决策不影响全局
printf("0\n");
return ;
}
//这时候的不同在于决策者不能拿金币
else if(n==2*m+1){
if(p<2*m&&p&1)
printf("1\n");
else
printf("0\n");
return ;
}
int t=n-2*m,i;
//这是刚好保命的情况，对于决策者来说，肯定没有金币
//对于其它人来说，要么肯定没有金币，要么可能没有金币，不确定性
for( i=0;i<14;i++){
if(t==fac[i]){
printf("0\n");
return;
}
}
for( i=1;i<14;i++)
if(t<fac[i]){
//决策者必死
if(p>2*m+fac[i-1]&&p<2*m+fac[i])
printf("Thrown\n");
else
printf("0\n");
return ;
}
}
int main(){
int t,n,m,p;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&p);
slove(n,m,p);
}
return 0;
}

1. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

2. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c

3. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示