首页 > 代码库 > hdu 2177 取(2堆)石子游戏

hdu 2177 取(2堆)石子游戏

天资愚笨啊,网上的一大堆没看懂。。。。。。

总结百科的方法为:

1.a==b

同时减去a 得到0,0

2.a==a_k      b>b_k

b -(b-b_k)

3.a==a_k     b<b_k

同时拿走a_k-a_(b-a_k)

得到 a_(b-a_k)    a_(b-a_k) + b-a_k

4.a>a_k       b==b_k

从a中拿走 a-a_k

5.a<a_k       b==b_k

5.1 a==a_ j   (j<k) 

b-(b-b_ j)

得到 a_ j    b_ j

5.2 a==b_ j   (j<k)

b-(b-a_ j)

得到 b_ j   a_ j  

反正我是没搞懂!!o(╯□╰)o。。。。

我的方法就是 穷举了:

第一个分支,从两堆物品中同时取出相同数量的物品

第二个分支,只从一堆物品中取物品

代码如下:

#include<stdio.h>
#include<math.h>
int main()
{
  int a,b,k,temp,n,i,aa,bb,x,y;
  double m;
  
  while(~scanf("%d%d",&a,&b)&&a+b)
  {
    if(a>b)
    {
      temp=a;
      a=b;
      b=temp;
    }
    k=b-a;
    m=(1+sqrt(5.0))/2.0;
    n=(int)k*m;
    if(a==n)
      printf("0\n");
    else
     {
         printf("1\n");
         for(i=1;i<=a;i++)
         {
           aa=a-i;
           bb=b-i;
           if(n==aa)
           {
              printf("%d %d\n",aa,bb);
              break; 
           } 
         }
         for(i=b;i>=0;i--)
         {
            x=a;y=i;
            if(x>y)
            {
              temp=y;
              y=x;
              x=temp;
            }
            k=y-x;
            n=(int)k*m;
            if(x==n)
             {
               printf("%d %d\n",x,y);
               break;
             }
         }
         
     }
  } 
  return 0;  
}