Line 21: Line 21:
 
<syntaxhighlight lang="c" name="printa">
 
<syntaxhighlight lang="c" name="printa">
 
#include <stdio.h>
 
#include <stdio.h>
+
#include <string.h>
 +
 
 
int main()
 
int main()
 
{
 
{
     unsigned long N, M, i;
+
     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: ");
 
     printf("Enter N: ");
 
     scanf("%lu", &N);
 
     scanf("%lu", &N);
     printf("\n\nKey Sequences:\n\n");
+
 
     if(N <= 6)
+
    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++)
 
     {
 
     {
         M = 6;
+
         if(i <= 6)
         for(i = 0; i < N; i++)
+
        {
        printf("A\n");
+
            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;
     else if (N % 3 == 0)
+
     while(i+1 < N && outf[i+1] != 2)
 
     {
 
     {
         M = 3 * (1L<< (N-3)/3); //1<<x gives pow(2,x) and I'm too lazy to include math.h
+
         outf[i] = 0;
         for(i = 0; i < 3; i++)
+
        i++;
            printf("A\n");
+
    }
         for(i = 1; i < N/3; 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("\nCTRL+A\n");
+
              
            printf("CTRL+C\n");
+
             printf(out[outf[i]]);
             printf("CTRL+V\n\n");
 
 
         }
 
         }
    }
+
      }
+
      
     else
+
     for(i = 1; i <= N; i++)
     {
 
        M = 4 * (1L << (N-4)/3) + (N-4)%3; //1<<x gives pow(2,x)
 
        for(i = 0; i < 4; i++)
 
            printf("A\n");
 
 
        for(i=0; i < (N-4)/3; i++)
 
 
         {
 
         {
             printf("\nCTRL+A\n");
+
              
            printf("CTRL+C\n");
+
             printf("%u ",ind[i]);
             printf("CTRL+V\n\n");
 
 
         }
 
         }
+
     printf("\nM = %llu\n", sol[N]);
        for(i = 0; i < N%3; i++)
+
   
            printf("A\n");
 
    }
 
     printf("\nM = %lu\n", M);
 
 
}
 
}
 +
 +
 
</syntaxhighlight>
 
</syntaxhighlight>
  
  
 
{{Template:FBD}}
 
{{Template:FBD}}

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>




blog comments powered by Disqus

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[edit]

<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>




blog comments powered by Disqus