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

样例输入

1
4 2
2 4 1 1

样例输出

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=0;i<n;i++)
            scanf("%d",&x);
        if(n % (m+1) == 0)
            printf("Starry\n");
        else
        printf("Ocean\n");
    }
    return 0;
}

 

上一篇:1079 延迟的回文数 (20 分)


下一篇:小米弹性调度平台Ocean