A: Absolutely Simple---巴什博弈

A: Absolutely Simple

时间限制: 1 s 内存限制: 128 MB

题目描述

Ocean暑假去海边玩，海边有许多好看的贝壳。并且Ocean捡了好多回来。

回来之后，Starry也感觉这些贝壳好漂亮，也想要。这些贝壳虽然都很漂亮，但是每一个贝壳都有自己的美丽度，于是Ocean把这些贝壳按照美丽度从小到大排列了起来，接下来就是和Starry分贝壳了。因为这些贝壳是如此的好看，以至于Ocean和Starry都想拿到最后一个贝壳。所以为了更好的分配，Ocean和Starry决定，按照顺序轮流取贝壳，并且每次可以取m

个以内的贝壳，Ocean先取，也就是说，Ocean先开始取贝壳，并且可以选择取走1,2,3,,,或者是m

个。现在，聪明的你可以判断出来谁可以取走最后一个贝壳吗？,Ocean与Starry都十分的聪明，每次都会采取最优策略。

输入

一个整数T代表有T

组数据(1≤T≤102)

接下来2T

行，

第2∗i−1

行每行两个数字n和 m,n代表总共有n个贝壳，m代表每次最多可以一次性取走m个贝壳(1≤n≤105,1≤m≤106)

第2∗i

行，每行有n个整数x代表每个贝壳的美丽度，数据保证最美丽的贝壳有且只有一个。(1≤x≤106)

输出

输出T

行

对于每组测试数据，若Ocean拿到最后一个贝壳输出Ocean，否则输出Starry

样例输入

样例输出

Ocean

提示

大量的输入建议用scanf

在样例中排序后是1 1 2 4

Ocean第一次取走一个，然后Starry无论取走1个还是2个，Ocean最后都可拿走剩下的所有的所以Ocean一定可以取走最后一个

巴什博弈
eg:
有n个石头，Alice和Bob轮流取石头，每次取的石头不能超过m个，Alice开始取，最后取完的赢，两个人都是以最优的方案取，求最终赢的是谁？

假设n = 12，m = 11。
先手能取1,2,3…10,11这11种情况，剩下石头的有11,10,9…3,2,1 很明显先手不管取哪种情况都比输。

所以先手必输
结论: n % (m+1) == 0 时，先手必输，否则必赢。

#include<iostream>

#include<string.h>

#include<math.h>

#define mx 0x3f3f3f3f

#define ll long long

#define mod 1000000007

using namespace std;

int main()

{

    int t,m,n,x;

    scanf("%d",&t);

    while(t--)

    {

        cin>>n>>m;

        for(int i=;i<n;i++)

            scanf("%d",&x);

        if(n % (m+) == )

            printf("Starry\n");

        else

        printf("Ocean\n");

    }

    return ;

}