轮流取石头游戏

两个足够聪明的人玩轮流取石头的游戏，谁取到最后一个石头谁就赢了，他们一次只能取1个、3个、7个或8个石头，写一程序判断n个石头时先取的人是输还是赢。

输入格式:

一个整数n，其值不超过10000000。

输出格式:

如果先取的人赢，请以单独一行输出1，否则输出0。

输入样例:

这里是3组输入。

1

10

300

输出样例:

上面3组数据对应的输出分别如下：

1

1

0

#include <stdio.h>
#include <iostream>
using namespace std;
int dp[10000001],n;//dp存的对于先手来说的赢输情况
int main()
{
    
/*每次只能取1,3,7,8个*/
    dp[1]=1;//1,3,7,8这些情况下，先手第一次就取完全部，剩下0个，就直接先手胜
    dp[3]=1;
    dp[5]=1;//5是先手取3 后手1 先手1 最后剩0 ，先手胜
    dp[7]=1;
    dp[8]=1;
    while(cin>>n)
    {
    
        for(int i=9; i<=n; i++)
        {
    
            //i取完后剩下的能使后手失败那i状态就能胜
            if(!dp[i-1]||!dp[i-3]||!dp[i-7]||!dp[i-8])
                dp[i]=1;
            else
                dp[i]=0;
        }
        cout<<dp[n]<<endl;
    }

    return 0;
}