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]