View source for Printing A ← Printing A

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

==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
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 solution at position $(n-6)$ because that is already considered while calculating the solution at position $(n-3)$ which we are considering. Each CTRL-V prints the same number of characters as was on the screen 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">
#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 if a = max(a,b,c), 2 if b = max(a,b,c) and 3 if c = max(a,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>

===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">
#include <stdio.h>
 
//Returns max of a,b,c,d 
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 if a = max(a,b,c,d), 2 if b = max(a,b,c,d), 3 if c = max(a,b,c,d) and 4 if d = max(a,b,c,d)
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>


{{Template:FBD}}

[[Category:Arrays]]
[[Category:Placement Coding Questions from Arrays]]