海盗分金

news/2024/10/25 18:24:57/

海盗分金

时间限制: 1 Sec 内存限制: 128 MB
提交: 4 解决: 4
[ 提交][ 状态][ 讨论版]

题目描述

一群海盗已经把手放在一堆金币上，并希望划分战利品。他们是以他们自己的方式进行划分，他们习惯于按照以下方式进行这样的分金币：最凶猛的海盗提出关于分金币的建议，并且每个人都对它进行投票，包括提议者。如果有50％及以上的海盗赞成，该提案即通过并立即实施。否则，提议者被扔到海里，并且由下一个最凶猛的海盗进行提议。所有的海盗都想把他们的一位同伴（既提议者）扔到船外，但同时他们会通过对自己最有好处的提议，而且好处越大越好。同时他们不喜欢自己被抛在海里。所有海盗都是理性的，并且知道其他海盗也是理性的。而且，没有两个海盗同样凶恶，所以有一个精确的分金币顺序 - 它是所有人都知道的。金币是不可分割的，不允许分享的，因为没有海盗信任他的同伴。关于海盗的另一件事是他们是现实的。他们认为'十鸟在林不如一鸟在手'，这意味着他们更喜欢明确获得的，而不是冒险获得更多，因为他们可能会失去一切。为了方便起见，按照温顺的顺序对海盗进行编号，最不凶恶的是1号，下一个是2号，等等。因此，最凶猛的海盗最先提出分配方案，及提案按照号码从最大到最小的顺序进行。你的任务是预测给定的海盗会得到多少金币。

现在有100枚金币

当有3个海盗时

他们所分配的金币数量如下

ID：1 2 3

1 0 99

当有4个海盗时

他们所分配的金币数量如下

ID：1 2 3 4

0 1 0 99

当有5个海盗时

他们所分配的金币数量如下

ID：1 2 3 4 5

1 0 1 0 98

输入

一个T表示测试用例个数

然后有T行，每行3个整数n，m，p。n（1≤n≤10^ 4）是海盗的数量。m（1≤m≤10^ 7）是金币的数量。p（1≤p≤n）表示你要预测的海盗所在的序号，其中p = n表示最凶猛的海盗。

输出

每种情况下的输出由一个整数组成，这是海盗可以获得的最小金币数量。例如，如果海盗可以获得0或1个金币，输出'0'。如果海盗p被抛出，输出'Thrown'。

样例输入

样例输出

0
1
98

解题思路：https://blog.csdn.net/y990041769/article/details/22858781（参考这位大牛的）

源代码：

#include <cstdio>  
int fac[15]= {2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};  
int main()  
{  int T;  scanf("%d",&T);  while(T--)  {  int n,m,k,ans=-1,flot;  scanf("%d%d%d",&n,&m,&k);  if(2*m+1>=n)  {  if(n==k)  {  ans=m-((n-1)/2);  }  else if(n%2==k%2)  ans=1;  else  ans=0;  }  else  {  n-=2*m;  flot=0;  for(int i=0; i<14; i++)  if(n==fac[i])  {  ans=0;  flot=1;  break;  }  if(flot==0)  {  for(int i=1; i<14; i++)  {  if(n<fac[i])  {  if(k>2*m+fac[i-1] && k<2*m+fac[i])  ans=-1;  else  ans=0;  break;  }  }  }  }  if(ans==-1)  printf("Thrown\n");  else  printf("%d\n",ans);  }  return 0;  
}