1430 奇偶游戏
题目来源: CodeForces
基准时间限制:1 秒 空间限制:131072 KB 分值: 160 难度:6级算法题 收藏 关注
有n个城市,第i个城市有ai个人。Daenerys和Stannis是两个恶魔。他们在玩一个游戏,他们轮流去破坏城市。每一轮破坏一个城市并杀光里面所有的人。直到剩下k个城市为止。
如果最后剩下的总人数是偶数那么Daenerys获得胜利,否则Stannis获得胜利。
现在给定一个局面,要求你来判断一下谁会赢,Stannis先出手。
Input
单组测试数据。
第一行包含两个整数n,k (1 ≤ k ≤ n ≤ 2*10^5)表示刚开始的城市数目和最后剩下的城市数目。
第二行有n个整数a1,a2,a3,…,an。 (1 ≤ ai ≤ 10^6),表示每个城市里面的人数。
Output
对于每一组数据输出胜者。
Input示例
3 1
1 2 1
3 1
2 2 1
Output示例
Stannis
Daenerys
/*
博弈.
具体讨论第k+1个是谁取的.
n==k的时候特判一下.
否则算出每个人的可操作次数.
然后讨论就好.
*/
#include<iostream>
#include<cstdio>
#define MAXN 10001
using namespace std;
int n,k,num1,num0,k0,k1;
int main()
{
int x;
while(~scanf("%d%d",&n,&k))
{
num1=num0=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
if(x&1) num1++;
else num0++;
}
if(n==k)
{
if(num1&1) printf("Stannis\n");
else printf("Daenerys\n");
continue;
}
k1=(n-k+1)/2;
k0=n-k-k1;
if(num1<=k0) printf("Daenerys\n");
else if(num0<=k0&&(num1-num0)&1&&k0!=k1)
{
printf("Daenerys\n");
}
else if(num0<=k0&&(num1-num0)%2==0&&k1==k0)
{
printf("Daenerys\n");
}
else if(num0>k0&&num1>k0&&k1==k0)
{
printf("Daenerys\n");
}
else {
printf("Stannis\n");
}
}
return 0;
}