Difference between revisions of "Printing A"

Revision as of 00:09, 18 June 2014

Imagine you have a special keyboard with the following keys:

A

Ctrl+A

Ctrl+C

Ctrl+V

where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” operations respectively.

If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. That is to say, the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce).

Solution by Arjun Suresh

<syntaxhighlight lang="c" name="printa">

1. include <stdio.h>
2. include <string.h>

int main() {

   unsigned int N, i, j;
   unsigned long long M;
   unsigned long long sol[1000];
   unsigned long long buf[3];
   unsigned int ind[1000];
   printf("Enter N: ");
   scanf("%lu", &N);
 
   unsigned long long arr[3];
   memset(arr, 0, 3*sizeof(arr[0]));
   memset(sol, 0, 1000*sizeof(sol[0]));
   /*
   arr[0] = 4;
   buf[0] = 1;
   arr[1] = 6;
   buf[1] = 2;
   arr[2] = 6;
   buf[2] = 3;
   */
   arr[0] = 4;
   buf[0] = 1;
   arr[1] = 6;
   buf[1] = 2;
   arr[2] = 6;
   buf[2] = 3;
   unsigned index;
   char * out[] = { "A\n", "CTRL+A\n", "CTRL+C\n", "CTRL+V\n"};
   unsigned int outf[1000];
   unsigned p = 2, pp = 3; 
   memset(outf, 0, 1000*sizeof(outf[0]));
   for(i=1; i<=N; i++)
   {
       if(i <= 6)
       {
           outf[i] = 0;
           sol[i] = i;
           ind[i] = 0;
           ind[6] = 3;
           
       }
       
       else
       {
            printf("\n\ni = %u\n", i);
           arr[0] = arr[1] + buf[1];
           arr[1] = arr[2] + buf[2]; 
           arr[2] = 2 * sol[i-3];
           buf[0] = buf[1];
           buf[1] = buf[2];
           buf[2] = sol[i-3];
           if(arr[0] > arr[1])
           {
               if(arr[0] > arr[2])
               {
                   index = i-5;
                   sol[i] = arr[0];
                   
                 
                 //  outf[i] = outf[i-1];
                   //outf[i-1] = outf[i-2];
                   if(p > 3){
                   outf[p+1] = 1;
                   outf[p+2] = 2;
                   }
                   
                  // for(j = 0; j < buf[0]; j++)
                    //   outf[j] = 0;
                   for(j = p+3; j <=i; j++)
                       outf[j] = 3;
                   ind[i] = p;
                   if(ind[p] >= 3){
                   outf[ind[p]+1] = 1;
                   outf[ind[p]+2] = 2;
                   }
              
                   for(j = ind[p]+3; j <= p; j++)
                       outf[j] = 3;
                 
               }
               else
               {
                   
                   index = i-3;
                   sol[i] = arr[2];
                   outf[i] = 3;
                  
                   outf[i-1] = 2;
                   outf[i-2] = 1;
                  
                   outf[i-1] = 2;
                   outf[i-2] = 1;
                   
                   ind[i] = i-3;
                   outf[ind[i-3]+1] = 1;
                   outf[ind[i-3]+2] = 2;
                   for(j = ind[i-3]+3; j < i-3; j++)
                   {
                       outf[j] = 3;
                   }
                  // p = pp;
                  // pp = i -3;
                 // printf("CTRL+A\nCTRL+C\nCTRL+V\n");
               }
           }
           else if (arr[1] > arr[2])
           {
               index = i-4;
               sol[i] = arr[1];
              
               outf[pp+1] = 1;
               outf[pp+2] = 2;
              
              // for(j = 0; j < buf[1]; j++)
                //       outf[j] = 0;
               for(j = pp+3; j <=i; j++)
                   outf[j] = 3;
               ind[i] = pp;
               if(ind[pp] >= 3){
               outf[ind[pp]+1] = 1;
               outf[ind[pp]+2] = 2;
               }
               for(j = ind[pp]+3; j <= pp; j++)
               outf[j] = 3;
               
               //outf[i-1] = outf[i-2];
               //outf[i-2]= outf[i-3];
               //printf("CTRL+V\n");
           }
           else
           {
              
               index = i-3;
               sol[i] = arr[2];
               outf[i] = 3;
             
               outf[i-1] = 2;
               outf[i-2] = 1;
               
               ind[i] = i-3;
               outf[ind[i-3]+1] = 1;
               outf[ind[i-3]+2] = 2;
               for(j = ind[i-3]+3; j < i-3; j++)
               {
                   outf[j] = 3;
               }
               //p = pp;
              // pp = i -3;
              
               //printf("CTRL+A\nCTRL+C\nCTRL+V\n");
               
           }
          
          // sol[i] = max(arr[0] , arr[1], arr[2]);
        
           printf("\n%lld %lld %lld\n", arr[0], arr[1], arr[2]);
           printf("%lld %lld %lld\n", buf[0], buf[1], buf[2]);
           printf("p = %u pp = %u\n", p, pp);
           for(j = 1; j <= i; j++)
       {
           
       //    printf(out[outf[j]]);
       }
        p = pp;
           pp = i - 3;
       }
   }
   i = 1;
   while(i+1 < N && outf[i+1] != 2)
   {
       outf[i] = 0;
       i++;
   }
     printf("\n\nKey Sequences:\n\n");
   //  if(N <= 6)
     {
       //  printf("A\nA\nA\nA\nA\nA\n");
         
     }
     //else
     {
       for(i = 1; i <= N; i++)
       {
           
           printf(out[outf[i]]);
       }
     }
   
   for(i = 1; i <= N; i++)
       {
           
           printf("%u ",ind[i]);
       }
   printf("\nM = %llu\n", sol[N]);
   

}

</syntaxhighlight>