Difference between revisions of "Printing A"

Revision as of 17:23, 26 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

include <stdio.h>

int max(int a, int b, int c) { return a > b ? a > c? a:c : b > c? b:c; }

int maxp(int a, int b, int c) { return a > b ? a > c? 1:3 : b > c? 2:3; }

void print(int *, int);

int main() { unsigned int n, i; unsigned long long sol[1000]; unsigned int prin[1000]; printf("Enter N: "); scanf("%u", &n);

for(i = 1 ;n>5? i<=5: i<= n; i++) { sol[i] = i; prin[i] = 0; } if(n >= 6) { sol[6] = 6; prin[6] = 1; } for(i = 7; i <= n; i++) { sol[i] = max(2 * sol[i-3], 3 * sol[i-4], 4 * sol[i-5]); prin[i] = maxp(2 * sol[i-3], 3 * sol[i-4], 4 * sol[i-5]); } printf("M = %llu\n", sol[n]); printf("Enter any char to start printing the key sequence: \n"); scanf("%d", &n); printf("Printing the sequence: \n\n"); print(prin, n); }

void print(int * prin, int n) { if(n < 1 ) return; switch(prin[n]) { case 0: print(prin, n-1); printf("A\n"); break; case 1: print(prin, n-3); printf("CTRL-A\nCTRL-C\nCTRL-V\n"); break; case 2: print(prin, n-4); printf("CTRL-A\nCTRL-C\nCTRL-V\nCTRL-V\n"); break; case 3: print(prin, n-5); printf("CTRL-A\nCTRL-C\nCTRL-V\nCTRL-V\n"); } }

</syntaxhighlight>

@@ Line 21: / Line 21: @@
 <syntaxhighlight lang="c" name="printa">
 #include <stdio.h>
-#include <string.h>
+int max(int a, int b, int c)
+{
+ return a > b ? a > c? a:c : b > c? b:c;
+}
+int maxp(int a, int b, int c)
+{
+ return a > b ? a > c? 1:3 : b > c? 2:3;
+}
+void print(int *, int);
 int main()
 {
-    unsigned int N, i, j;
+ unsigned int n, i;
-    unsigned long long M;
+ unsigned long long sol[1000];
-    unsigned long long sol[1000];
+ unsigned int prin[1000];
-    unsigned long long buf[3];
+ printf("Enter N: ");
-    unsigned int ind[1000];
+ scanf("%u", &n);
-    printf("Enter N: ");
-    scanf("%lu", &N);
+ for(i = 1 ;n>5? i<=5: i<= n; i++)
+ {
-    unsigned long long arr[3];
+ sol[i] = i;
-    memset(arr, 0, 3*sizeof(arr[0]));
+ prin[i] = 0;
-    memset(sol, 0, 1000*sizeof(sol[0]));
+ }
-    /*
+ if(n >= 6)
-    arr[0] = 4;
+ {
-    buf[0] = 1;
+ sol[6] = 6;
-    arr[1] = 6;
+ prin[6] = 1;
-    buf[1] = 2;
+ }
-    arr[2] = 6;
+ for(i = 7; i <= n; i++)
-    buf[2] = 3;
+ {
-    */
+ sol[i] = max(2 * sol[i-3], 3 * sol[i-4], 4 * sol[i-5]);
-    arr[0] = 4;
+ prin[i] = maxp(2 * sol[i-3], 3 * sol[i-4], 4 * sol[i-5]);
-    buf[0] = 1;
+ }
-    arr[1] = 6;
+ printf("M = %llu\n", sol[n]);
-    buf[1] = 2;
+ printf("Enter any char to start printing the key sequence: \n");
-    arr[2] = 6;
+ scanf("%d", &n);
-    buf[2] = 3;
+ printf("Printing the sequence: \n\n");
-    unsigned index;
+ print(prin, n);
-    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]);
 }
+void print(int * prin, int n)
+{
+ if(n < 1 )
+ return;
+ switch(prin[n])
+ {
+ case 0:
+ print(prin, n-1);
+ printf("A\n");
+ break;
+ case 1:
+ print(prin, n-3);
+ printf("CTRL-A\nCTRL-C\nCTRL-V\n");
+ break;
+ case 2:
+ print(prin, n-4);
+ printf("CTRL-A\nCTRL-C\nCTRL-V\nCTRL-V\n");
+ break;
+ case 3:
+ print(prin, n-5);
+ printf("CTRL-A\nCTRL-C\nCTRL-V\nCTRL-V\n");
+ }
+}
 </syntaxhighlight>

Difference between revisions of "Printing A"

Revision as of 17:23, 26 June 2014

Solution by Arjun Suresh

Solution by Arjun Suresh[edit]