Responsive image

问题 A: 海盗分金

问题 A: 海盗分金

时间限制: 1 Sec  内存限制: 128 MB
提交: 18  解决: 7
[提交][状态][讨论版][命题人:]

题目描述

一群海盗已经把手放在一堆金币上,并希望划分战利品。他们是以他们自己的方式进行划分,他们习惯于按照以下方式进行这样的分金币:最凶猛的海盗提出关于分金币的建议,并且每个人都对它进行投票,包括提议者。如果有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'。

样例输入

3
3 100 2
4 100 2
5 100 5

样例输出

0
1
98
[提交][状态]
ACM算法攻关部