http://acm.hdu.edu.cn/showproblem.php?pid=1525
1 //題意: 給定n,m兩個(gè)數(shù)，兩個(gè)人輪流操作:
2 //選m,n小的數(shù)，每次都是大的減去小的數(shù)的k倍,k<=max(n,m)/min(n,m);
3 //知道其中一個(gè)為0時(shí)，執(zhí)行該操作的為勝者
4
5 //Analyse:for example: if n>m,then n=m*k+c(k<=n/m,c=n%m)
6 //if k>1,then the first player can decide who'll win.if current statue is lost,he can decrease (k-1)*m,
7 //the statue is changed to (m+c,m),the second player only operate m,so the statue is changed to (m,c) which
8 //is the winning statue. if current is the winning statue,he can decrease k*m,the statue is changed to (m,c)
9 //which is the lost statue.So if k>1,the one who operate it is the winner,he is active.but if k==1,he can only
10 //operate the small one.the one who first meet k>1 is the winner.specially,if no one meet k>1,the player operate
11 //it in turn,the first makes the n or m to zero is the winner.
12 #include <iostream>
13
14 using namespace std;
15 int main()
16 {
17 int n,m;
18 while(cin>>n>>m,n+m){
19 int cnt=0;
20 int ans=0;
21 while(1){
22 if(n<m)swap(n,m);
23 ans=n/m;
24 if(ans>=2){
25 break;
26 }
27 cnt++;
28 n%=m;
29 if(n==0){
30 cnt++;
31 break;
32 }
33 }
34 if(cnt&1){
35 cout<<"Ollie wins\n";
36 }
37 else cout<<"Stan wins\n";
38 }
39 return 0;
40 }
posted on 2008-07-23 18:55
小果子 閱讀(263)
評(píng)論(0) 編輯 收藏 引用