UESTC 1253 阿里巴巴和n个大盗 博弈、策略

阿里巴巴和n个大盗博弈、策略

Source

第七届ACM趣味程序设计竞赛第二场（正式赛） D

My Solution

首先总人数是n+1人。

由于必须半数以上人同意才能通过方案，所以当剩余两个人时2号必死，因为1号不同意就能独吞。

因此2号必须同意3号的方案，所以3号无论什么方案都会被通过，因此他会选择把所有宝石留给自己。

当总人数三个以上时就有以下的情况：显然4号需要至少3人的同意，可知3号是无论如何不会同意的，因此他只需要拉拢1,2号即可，

也就是给他们1,1的宝石。

5个人时只要3个人同意即可，此时因为5号如果死3号必定不会得到宝石，所以只要给他1个宝石即可。然后再拉拢1,2号中的任意一个，

给他们2个宝石即可。

以此类推，发现当（n+1)是偶数时阿里巴巴只要给1到n号人1,1,0,1,0,1,0....0即可；注意这里以 0 结尾；此时
m-(n+1)/2。★

当(n+1)是奇数时只要给x,x,1,x,1,x,1....0（任意一个x是2，其余x都是0）；此时m-(n+2)/2。 ★

/*给1号或者2号*/即可

因为题目所给数据范围的限制，本题不会出现m不够用的情况，在这里不再讨论。

注意心狠手辣一词。

万恶的这帮强盗也太聪明了吧！

#include 
#include 
#define LOCAL
using namespace std;

int main()
{
    #ifdef LOCAL
    freopen("a.txt","r",stdin);
    #endif // LOCAL
    int n,m;
    scanf("%d%d",&n,&m);
    if(n==1) printf("-1");
    else if(n==2) printf("%d",m);
    else if(n==3) printf("%d",m-2);
    else if(n==4) printf("%d",m-3);
    else {
            if(n%2==1)printf("%d",m-(n+1)/2);
            else printf("%d",m-(n+2)/2);
    }
    return 0;
}

非特殊说明，本站所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

UESTC 1253 阿里巴巴和n个大盗博弈、策略

阿里巴巴和n个大盗博弈、策略

Source

My Solution

相关推荐

HihoCoder – 1511 树的方差无根树的计数、分配式方差、分数取模

Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) B. Bash’s Big Day 数论+贪心

Codeforces Round #386 (Div. 2) D. Green and Black Tea 数论+贪心