Difference between revisions of "Printing A"

Revision as of 16:44, 28 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

A key to the solution is that we can continue pressing CTRL-V multiple times and the characters in the buffer will get printed continuously. The recurrence relation for the solution is

sol[n] = max(2 * sol[n-3], 3 * sol[n-4], 4 * sol[n-5]) | n > 6 

and

1 for 1<= n <= 6

The recurrence relation is drawn from the fact that, the optimal solution at position $n$ will be obtained by CTRL-A, CTRL-C, CTRL-V sequence starting at either $(n-3)^{th}$ position or $(n-4)^{th}$ position or $(n-5)^{th}$ position. We needn't consider this sequence starting at $(n-6)^{th}$ position because that will mean the sequence repeating again at $(n-3)^{th}$ position which we have considered. Each CTRL-V puts the same number of characters as was during which the previous CTRL-A was typed. So, if we take $sol[n-3]$, that would mean CTRL-A starting at $n-2$, CTRL-C at $n-1$ and CTRL-V at $n$. So, $sol[n-3]$ is doubled at $n$. If we take $sol[n-4]$, there will be CTRL-V at positions $n-1$ and $n$, and so $sol[n]$ becomes $3$ times $sol[n-4]$. Similarly, if we take $sol[n-5]$, there will be 3 CTRL-V at $n-2$, $n-1$ and $n$ and $sol[n]$ becomes 4 times $sol[n-5]$.

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

1. include <stdio.h>

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

//Returns 1 for a > (b,c), 2 for b > (a,c) and 3 for c > (a,b) 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>

Alternate Solution

The above solution assumes that after CTRL-C, we can do a mouse click as otherwise CTRL-V will override whatever was selected on the screen. If mouse click is not allowed, recurrence relation should be modified as:

sol[n] = max(2 * sol[n-4], 3 * sol[n-5], 4 * sol[n-6], 5 * sol[n-7]) | n > 7 

and

1 for 1<= n <= 7

The code for this will be: <syntaxhighlight lang="c" name="printa2">

1. include <stdio.h>

//Returns max of a,b,c int max(int a, int b, int c, int d) {

   return a > b ? a > c? a > d ? a : d : c > d? c : d  : b > c? b > d? b : d : c > d? c : d ;

}

//Returns 1 for a > (b,c), 2 for b > (a,c) and 3 for c > (a,b) int maxp(int a, int b, int c, int d) {

   return a > b ? a > c? a > d ? 1 : 4 : c > d? 3 : 4 : b > c?  b > d? 2 : 4 : c > d? 3 : 4;

}

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>7? i<=7: i<= n; i++) { sol[i] = i; prin[i] = 0; }

for(i = 8; i <= n; i++) { sol[i] = max( 2 * sol[i-4], 3 * sol[i-5], 4 * sol [i-6], 5 * sol[i-7]); prin[i] = maxp( 2 * sol[i-4], 3 * sol[i-5], 4 * sol [i-6], 5 * sol[i-7]); } 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-4); printf("CTRL-A\nCTRL-C\nCTRL-V\nCTRL-V\n"); break; case 2: print(prin, n-5); printf("CTRL-A\nCTRL-C\nCTRL-V\nCTRL-V\nCTRL-V\n"); break; case 3: print(prin, n-6); printf("CTRL-A\nCTRL-C\nCTRL-V\nCTRL-V\nCTRL-V\nCTRL-V\n");

                       break;
       case 4: 
   		        print(prin, n-7);

printf("CTRL-A\nCTRL-C\nCTRL-V\nCTRL-V\nCTRL-V\nCTRL-V\nCTRL-V\n"); } }

</syntaxhighlight>