TOJ 3348 Scales

  

   

    

     

    
    

     

      /***********************************
     
    
   

    

     

    
    

     

      Problem: TOJ 3348 Scales
     
    
   

    

     

    
    

     

      Time: 0'00.00"
     
    
   

    

     

    
    

     

      Memory: 720K
     
    
   

    

     

    
    

     

      Accepted Time: 2009-08-04 19:39:53
     
    
   

    

     

    
    

     

      Tip: DP min(放左盘，放右盘，不放)
     
    
   

    

     

    
    

     

      ************************************/
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <stdlib.h>
     
    
   

    

     

    
    

     

      int table[18]={1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163};
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int m;
     
    
   

    

     

    
    

     
	while(scanf("%d",&m)!=EOF)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		int aa[30],bb[30],ca=0,cb=0,i;
     
    
   

    

     

    
    

     
		int dp[2];
     
    
   

    

     

    
    

     

      		dp[0]=m;dp[1]=0;
     
    
   

    

     

    
    

     
		for(i=0;table[i]<m;i++);
     
    
   

    

     

    
    

     
		for(;i>=0;i--)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			int a=dp[0],b=dp[1];
     
    
   

    

     

    
    

     
			if(abs(a-b)>abs(a-b-table[i]))
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

       b+=table[i];
     
    
   

    

     

    
    

     
 if(abs(a-b)>abs(dp[0]+table[i]-dp[1]))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       dp[0]+=table[i];
     
    
   

    

     

    
    

     

       aa[ca++]=table[i];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else 
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       dp[1]+=table[i];
     
    
   

    

     

    
    

     

       bb[cb++]=table[i];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			else
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     
 if(abs(a-b)>abs(dp[0]+table[i]-dp[1]))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       dp[0]+=table[i];
     
    
   

    

     

    
    

     

       aa[ca++]=table[i];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			if(dp[0]==dp[1])break;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		printf("%d",ca);
     
    
   

    

     

    
    

     
		for(i=ca-1;i>=0;i--)printf(" %d",aa[i]);
     
    
   

    

     

    
    

     
		printf("/n");
     
    
   

    

     

    
    

     
		printf("%d",cb);
     
    
   

    

     

    
    

     
		for(i=cb-1;i>=0;i--)printf(" %d",bb[i]);
     
    
   

    

     

    
    

     
		printf("/n");
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：万猫学社，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/heihaozi/article/details/4409009