这题好X难。

    题目大概意思是：两人轮流乘一个2－9的数，从1开始乘，求谁的乘积先大于N。

    如果是加法就好做了。凑到剩下的数能整除11，然后对称着加。问题是乘法。

    所以寻找必胜点（段）。以1000为例。

    1000 | 999 ... 112 |    若占住999到112，则对手必胜。必须让对手占领此段。

    1000 | 999 ... 112 | 111 ... 56 |   因此必占段是 111 －? 。如果56被对手占住，则56×2＝112，入必败段。问题转化成为占56。

    如此循环。如下 1000 | 999 ... 112 | 111 ... 56 | 55 ... 7 | 6 ... 4 | 3 ... 1

   仔细考虑端点，我在处理端点情况时想了好久。

    这是牛人的代码。

#include <stdio.h>

unsigned int N;

bool StanWins ()
{
// printf ( "%u\n" , N );
 if ( N == 1 ) return true;
 int step;
 for ( step = 1; N > 1; step ++ )
  if ( step & 1 ) N = ( N - 1 ) / 9 + 1;
   else N = ( N + 1 ) / 2;
 return ( step & 1 ) == 0;
}

int main()
{
// freopen ( "p.in" , "r" , stdin );

 while ( scanf ( "%u" , &N ) != EOF )
  if ( StanWins () ) printf ( "Stan wins.\n" );
   else printf ( "Ollie wins.\n" );
 return 0;
}

    这是我的代码。

#include <cstdio>

unsigned int n;

int main()
{
 //freopen("in.txt", "r", stdin);
 while(scanf("%u", &n) != EOF)
 {
  int step = 0;
  //printf("%u\n", n);
  if(n == 1)
  {
   printf("Stan wins.\n");
   continue;
  }
  while(n > 1)
  {
   n = (n - 1) / 9 + 1;
   step ++;
   if(n <= 1) break;
   n = (n + 1) / 2;
   step --;
  }
  if(step)
   printf("Stan wins.\n");
  else
   printf("Ollie wins.\n");
 }
 return 0;
}

评论