原题连接:https://ac.nowcoder.com/acm/contest/903/F
题目大意:有三堆苹果,分别有M,N,N个苹果,有两种操作。
1.从任意一堆中取不超过S个苹果
2.分别从三堆中各取相同的任意个苹果,但不能超过所拥有的数量
不能不取或取零个苹果,取得最后一个苹果的人获胜。Alice先手,Bob后手。
思路:博弈论
1.当 n==m时,Alice可以一次取走,Alice胜
2.当n>m时,可以取剩两堆都是(n-m)个,此时Alice必胜;
3.当n<m<=s 时,与三堆苹果,只能从一堆中取任意数量情况结果一致,且m^n^n一定不为0,Alice赢;
4.当n<s+1<m时,与只有一对个数为m的苹果每次取不超过S个情况结果一致,即当m%(s+1)!=0时,Alice赢,m%(s+1)==0时,Bob赢;
5.当s+1<=n<m时,一定可以一步从三堆中取所需要的个数,获得n<s+1,m%(s+1)==0的情况,所以Alice赢。
综上,只有n<s+1,m%(s+1)==0是Bob赢,其他Alice赢。
ac代码:
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<cmath> using namespace std; #define ll long long #define ull unsigned long long #define ldb long double #define db double #define lowbit(x) (x&-x) #define fi first #define se second #define INF 0x3f3f3f3f #define endl "\n" #define rush() int T;scanf("%d",&T);while(T--) #define mem(a,b) memset((a),(b),sizeof(a)) const db pi = acos((db)-1); const ll MAXN = 5e8; const ll mod = 1e9+7; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdin); int s,m,n; while(~scanf("%d%d%d",&m,&n,&s)) { if(m%(s+1)==0&&n<(s+1))puts("Bob"); else puts("Alice"); } return 0; }