The Game Of Parity

发表于

The Game Of Parity

There are n cities in Westeros. The i-th city is inhabited by ai people. Daenerys and Stannis play the following game: in one single move, a player chooses a certain town and burns it to the ground. Thus all its residents, sadly, die. Stannis starts the game. The game ends when Westeros has exactly k cities left.

The prophecy says that if the total number of surviving residents is even, then Daenerys wins: Stannis gets beheaded, and Daenerys rises on the Iron Throne. If the total number of surviving residents is odd, Stannis wins and everything goes in the completely opposite way.

Lord Petyr Baelish wants to know which candidates to the throne he should support, and therefore he wonders, which one of them has a winning strategy. Answer to this question of Lord Baelish and maybe you will become the next Lord of Harrenholl.

Input

The first line contains two positive space-separated integers, n and k (1 ≤ k ≤ n ≤ 2·105) — the initial number of cities in Westeros and the number of cities at which the game ends.

The second line contains n space-separated positive integers a**i (1 ≤ a**i ≤ 106), which represent the population of each city in Westeros.

Output

Print string “Daenerys” (without the quotes), if Daenerys wins and “Stannis” (without the quotes), if Stannis wins.

Examples

Input

1
2
3 1
1 2 1

Output

1
Stannis

Input

1
2
3 1
2 2 1

Output

1
Daenerys

Input

1
2
6 3
5 20 12 7 14 101

Output

1
Stannis

题解：

  1. 如果k==n，直接得出结果。

  2. 如果后手能把奇数城毁完，那么后手必胜（因为剩下的，不管怎么毁，总和都为偶数）。

  3. 如果后手不能把奇数城毁完

    3.1如果倒数第二步操作的人不能把偶数城毁完，那么最后一步操作的人必胜，因为在最后一步时，既有奇数，也有偶数，可以随意控制输赢。

    3.2如果倒数第二步操作的人能把偶数城毁完，那么剩下的就只有奇数城，所以最后只需看剩下的奇数城有几座，即k。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
int n, k, a[2];
int main()
{
    cin>>n>>k;
    a[0] = a[1] = 0;
    for(int i = 1; i<=n; i++)
    {
        int x;
        cin>>x;
        a[x%2]++;//输入的人数只需要他的奇偶性，所以用0，1来区分奇偶数
    }
    int winner;
    int step = n-k;
    if(step==0)//n和k一样时，只需要判断奇数城市的个数
        winner = a[1]%2;
    else if(step/2>=a[1])//后手把奇数城全摧毁
        winner=0;
    else
    {
        if(step/2<a[0]) winner = step%2;//判断后手的最后一步是否可以把偶数全摧毁
        else winner = k%2;
    }
    if(winner)
    cout<<"Stannis"<<endl;
    else
        cout<<"Daenerys"<<endl;
}