ACM_1906

Three powers

Time Limit:1000MS  Memory Limit:30000K
Total Submit:936 Accepted:319

Description
Consider the set of all non-negative integer powers of 3.

S = { 1, 3, 9, 27, 81, ... }

Consider the sequence of all subsets of S ordered by the value of the sum of their elements.
The question is simple:
find the set at the n-th position in the sequence and print it in increasing order of its elements.

Input
Each line of input contains a number n, which is a positive integer with no more than 19 digits.
The last line of input contains 0 and it should not be processed.

Output
For each line of input, output a single line displaying the n-th set as described above,
in the format used in the sample output.

Sample Input

1
7
14
783
1125900981634049
0

Sample Output

{ }
{ 3, 9 }
{ 1, 9, 27 }
{ 3, 9, 27, 6561, 19683 }
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 }

Source
Waterloo local 2004.06.12
http://acm.pku.edu.cn

// Source
// Problem Id:1906  User Id:IceAngel
// Memory:24K  Time:15MS
// Language:C++  Result:Accepted

#include "iostream.h"
#include "fstream.h"
#include "string.h"
#include "stdlib.h"

#define maxLen 1024

typedef struct tagHugeNum
{
 char digit[maxLen];
 int len;
} HUGENUM, *PHUGENUM;

//
void hugeNumInit( HUGENUM &hugeNum , int n )
{
 hugeNum.digit[0] = n;
 for( int i = 1 ; i < maxLen ; i++ )
  hugeNum.digit[i] = 0;
 hugeNum.len = 1;
}

//
void multi( HUGENUM &hugeNum , int n )
{
 int i;
 for( i = 0 ; i < hugeNum.len ; i++ )
 {
  hugeNum.digit[i] *= n;
 }
 for( i = 0 ; i < hugeNum.len ; i++ )
 {
  if( hugeNum.digit[i] >= 10 )
  {
   hugeNum.digit[i+1] += hugeNum.digit[i] / 10;
   hugeNum.digit[i] %= 10;
   if( i == hugeNum.len - 1 )
    hugeNum.len++;
  }
 }
}

//
void print( HUGENUM hugeNum , char str[] )
{
 char append[1024] = { 0 };
 for( int i = hugeNum.len - 1 , j = 0 ; i >= 0 ; i-- , j++ )
  append[j] = hugeNum.digit[i] + '0';
 strcat( str , append );
}

int main()
{
 char str[1024];
 char msg[1024];
 __int64 x;
 __int64 map;
 __int64 lastp;
 __int64 p;
 __int64 mask;
 HUGENUM num;

 cin>>str;
 x = _atoi64( str );
 while( x > 0 )
 {
  map = x - 1;
  mask = 1;
  lastp = 0;
  hugeNumInit( num , 1 );
  msg[0] = '{';
  msg[1] = ' ';
  msg[2] = 0;
  for( int i = 0 ; i < 64 ; i++ )
  {
   p = map & mask;
   if( p ^ lastp )
   {
    lastp = p;
    print( num , msg );
    strcat( msg , ", " );
   }
   multi( num , 3 );
   mask = (mask<<1) + 1;
  }
  int len = strlen(msg);
  if( len > 2 )
  {
   msg[len-2] = ' ';
   msg[len-1] = '}';
  }
  else
  {
   strcat( msg , "}" );
  }
  cout<<msg<<endl;

  cin>>str;
  x = _atoi64( str );
 }

 return 0;
}