/*
 *************************************************************************
 *          Compute the N-th power of 3 and print the result
 *
 * Yes, it is that simple: compute 3^N and print out the result as
 * *fast* as possible. N is a non-negative integer number not
 * exceeding 2000. Yes, it can be that big, that's the catch you've
 * been looking for. Modern cryptography often requires raising
 * numbers to very big powers, so here's a little exercise.
 *
 * The program should read the number N from the file "pow3.in"
 * and print 3^N. You should write no more than 70 digits per line.
 * If the result appears longer than that, put a backslash after
 * the 70-th digit, and continue printing digits on the next line.
 * Don't print leading zeros!
 *
 * For example, if the file "pow3.in" contains "100", the program
 * should print 
 * 3^100
 * 515377520732011331036461129765621272702107522001
 * 
 * If the file "pow3.in" contains "1000", the program
 * should print 
 * 3^1000
 * 1322070819480806636890455259752144365965422032752148167664920368226828\
 * 5973467048995407783138506080619639097776968725823559509545821006189118\
 * 6534272525795367402762022519832080387801477422896484127439040011758861\
 * 8041128947815623094438061566173054086674490506178125480344405547054397\
 * 0388958174653682549161362208302685637785822902284163983078878969185564\
 * 0408489893760937324217184635993869551676501894058810906042608967143886\
 * 4102814350385648747165832010614366132173102768902855220001
 *
 * Performance counts!
 * The program has to handle numbers as big as 2000. If your program takes
 * more than 4 secs to raise 3 to the power of order 2000, it's considered
 * failed the test. Moreover, you would be punished by 20 minutes, or by the
 * time it takes a judge to reboot his PC and restore his working
 * environment, whichever is bigger (keep in mind that the judge would
 * probably be very mad at you...) So, be careful in testing your program
 * before submission.
 *
 * The algorithm
 * The longest operation appears not a multiplication of a very long integer
 * by 3, but its division by 10 to figure out the next decimal digit to
 * print. To cut down this expense, we perform arithmetic in decimal rather
 * than in binary. Furthermore, we make radix 10000. It means, that a single
 * "digit" (ranging from 0 to 9999) can comfortably fit into a short
 * int, and even have space for a carry (which can be 0, 1, 2 or 3).
 * Since the log10(3) = 0.477 is almost 0.5, 3^2000 < 10^1000, so we need
 * at most 1000/4 = 250 radix-10000 digits.
 * Note, multiplication by three is most conveniently done as a shift
 * followed by addition. So, the present program uses no multiplication
 * or division to compute and print 3^N, isn't that neat?
 *
 * $Id: pow3.c,v 1.2 2002/10/28 21:03:54 oleg Exp oleg $
 *
 *************************************************************************
 */

#include <stdio.h>
#include <string.h>
#include <assert.h>

typedef short int DIGIT;	/* Radix-10000 digit with a room for carry */
#define MAX_DIGITS 251		/* Max no. of digits we expect in a result*/
static DIGIT Digits[MAX_DIGITS];/* Our result in REVERSE order of digits */
				/* That is, Digits[0] is the least	 */
				/* significant digit			 */
static int valid_digits;	/* How many digits in Digits are valid	 */

				/* Prepare the stuff for work		*/
static void init_digits(void)
{
  memset(Digits,0,sizeof(Digits));
  valid_digits = 0;
}

				/* Compute 3^N in Radix-10000 digits */
static void raise_3(const long N)
{
  register int i;
  register DIGIT * dp;
  register int carry = 0;

  assert( N >= 0 );

  Digits[valid_digits++] = 1;
  if( N == 0 )
    return;				/* 3^0 is 1 always		*/

  for(i=1; i<=N; i++)			/* Computing 3^i  */
  {
    carry = 0;
    for(dp=Digits; dp<Digits+valid_digits; dp++)  /* Multiply every digit */
    {
      register DIGIT new_digit = (*dp << 1) + *dp + carry;
      if( new_digit >= 30000 )			/* Can happen if dp[0] was */
	new_digit -= 30000, carry = 3;		/* 9999 and was a carry in */
      else if( new_digit >= 20000 )
	new_digit -= 20000, carry = 2;
      else if( new_digit >= 10000 )
	new_digit -= 10000, carry = 1;
      else
	carry = 0;
      *dp = new_digit;
    }
    if( carry )
      Digits[valid_digits++] = carry;
  }
  assert( valid_digits < MAX_DIGITS );
}

				/* Print the digits (in reverse order!)*/
static void print_digits(void)
{
  const int digits_per_line = 70;
  register int counter = 0;
  register DIGIT * dp;
  char buffer[10];

  if( valid_digits == 0 || (valid_digits == 1 && Digits[0] == 0) )
  {
    printf("0\n");
    return;
  }

  assert( Digits[valid_digits-1] > 0 );

				/* We don't want to print leading 0 */
  {				/* handle the most-signif digit w/ care*/
    sprintf(buffer,"%d",Digits[valid_digits-1]);
    printf("%s",buffer);
    counter = strlen(buffer);
    assert( counter <= 4 );
  }

					/* print less-significant digits  */
					/* with *all* zeros */
  for(dp=&Digits[valid_digits-1]-1; dp >= Digits; dp--)
  {
    register char * p;
    sprintf(buffer,"%04d",*dp);
    for(p=buffer; *p != '\0'; p++,counter++)
    {
      if( counter >= digits_per_line )
	printf("\\\n"), counter = 0;
      putchar(*p);
    }
  }
  putchar('\n');
}

int main(void)
{
  const char * input_file_name = "pow3.in";
  FILE * fp;
  long int N;

  if( (fp=fopen(input_file_name,"r")) == (FILE *)0 )
    perror("Failed to open the input file"),
    exit(4);

  if( fscanf(fp,"%ld",&N) != 1 )
    fprintf(stderr,"Failed to read the number N"),
    exit(4);

  fclose(fp);

  init_digits();
  printf("\n3^%ld\n",N);
  assert( N <= (MAX_DIGITS-1)*4*2 );
  raise_3(N);
  print_digits();

  return 0;
}