Mr. Panda and Mr. Sheep are playing a game on a 1 × N game board. Initially, all the cells are empty. Mr. Panda and Mr. Sheep take alternate moves and Mr.Panda moves first.

On each move, a player must fill an 'S' or 'O' into an empty cell. After the move, if there are 3 consecutive cells from left to right form the word "SOS", the player wins the game and the game finished.

If the board gets filled up without SOS appearing consecutively, no one wins the game, the game end with draw.

Now, if both Mr. Panda and Mr. Sheep play optimally, find out the result of the game.

链接🔗

「Gym 101775L」SOS

题解

最短的分出胜利的结构是 S _ _ S _ ,但是如果先手S _ _ _ _ 后手肯定不可能放S 因为只要S _ _ S _,S _ _ _ S ,S _ S _ _ 最后都是都是先手赢。
那么最短的就是 _ _ _ S _ _ _ 因为不管后手破坏哪一边都能在另外一边构造出S _ _ S,那么最短出现结果的就是7,如果是偶数的话,由于Mr.熊猫是先手,他不能获得胜利那么就要破坏别人的,能推脱平局,比如10 --> _ _ _ _ S _ _ _ _ _ 4,5。两边都分不出结果。
当N=15的时候 _ _ _ _ _ _ _ S _ _ _ _ _ _ _ 7,7 ,但是n等于15是奇数,所以从16开始就是Mr.羊获胜,否则就能给Mr.熊猫拖成平局

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 1e5+10;
int a[maxd];
int main()
{
//    freopen("a.in","r",stdin);
//    freopen("k.out","w",stdout);
    int t;scanf("%d",&t);
    //printf("%lld\n",t);
    for(int tt = 1;tt <= t;tt++)
    {
        int n;scanf("%d",&n);
        int flag;
        if(n < 7) flag = 1;
        else if(n %2 == 0 && n < 16)  flag =1;
        else if(n %2 == 0 )flag =0;
        else flag = 2;
        if(flag == 1) printf("Case #%d: Draw\n",tt);
        else if(flag == 2) printf("Case #%d: Panda\n",tt);
        else printf("Case #%d: Sheep\n",tt);
    }
    return 0;
}