博弈问题。
输入是两个数A、B（设A>=B），有两个人轮流操作，每轮可以从A中减去B*k，k满足A>=B*k，随后令A’=A-B*k，A=max(A’,B)，B=min(A’,B)，再进行下一轮。先使得B==0的人获胜。
分析题意易得，A、B两数的组合每次的mxk=A/B值决定了当前选手是否拥有主动权：若mxk>1，那么自己可以选择(mxk-1)，对手只能选1，下一轮依然自己先选，若下一轮mxk==1还可以本轮自己全取，依然是主动；但若mxk==1，那么自己这轮就无法选择了。由于这里每轮都是最优操作，那么首先获得主动权的人可以赢得比赛。由此迭代更新A、B，并找到首先不为1的A/B值，此轮的先手就是赢家。
另外，最后一组A、B的值无关紧要，因为此时无论谁先手，都必定全取k=A/B。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include<cstdio> int a,b; int main() { int i,w; while(~scanf("%d%d",&a,&b)&&a) { if(a<b) a^=b^=a^=b; for(w=1;a%b&&a/b==1;w^=1,i=a,a=b,b=i%b); puts(w?"Stan wins":"Ollie wins"); } return 0; } |