Difference between revisions of "Printing A"

 
(20 intermediate revisions by the same user not shown)
Line 18: Line 18:
  
 
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
 
==={{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">
 
<syntaxhighlight lang="c" name="printa">
 
#include <stdio.h>
 
#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);
 
   
 
   
−
int main()
+
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)
 
{
 
{
−
     unsigned long N, M, i;
+
     return a > b ? a > c? a > d ? 1 : 4 : c > d? 3 : 4 : b > c?  b > d? 2 : 4 : c > d? 3 : 4;
−
    printf("Enter N: ");
+
}
−
    scanf("%lu", &N);
 
−
    printf("\n\nKey Sequences:\n\n");
 
−
    if(N <= 6)
 
−
    {
 
−
        M = 6;
 
−
        for(i = 0; i < N; i++)
 
−
        printf("A\n");
 
−
    }
 
 
   
 
   
−
    else if (N % 3 == 0)
+
void print(int *, int);
−
    {
 
−
        M = 3 * (1L<< (N-3)/3); //1<<x gives pow(2,x) and I'm too lazy to include math.h
 
−
        for(i = 0; i < 3; i++)
 
−
            printf("A\n");
 
−
        for(i = 1; i < N/3; i++)
 
−
        {
 
−
            printf("\nCTRL+A\n");
 
−
            printf("CTRL+C\n");
 
−
            printf("CTRL+V\n\n");
 
−
        }
 
−
    }
 
 
   
 
   
−
    else
+
int main()
−
    {
+
{
−
        M = 4 * (1L << (N-4)/3) + (N-4)%3; //1<<x gives pow(2,x)
+
unsigned int n, i;
−
        for(i = 0; i < 4; i++)
+
unsigned long long sol[1000];
−
            printf("A\n");
+
unsigned int prin[1000];
 +
printf("Enter N: ");
 +
scanf("%u", &n);
 
   
 
   
−
        for(i=0; i < (N-4)/3; i++)
+
for(i = 1 ;n>7? i<=7: i<= n; i++)
−
        {
+
{
−
            printf("\nCTRL+A\n");
+
sol[i] = i;
−
            printf("CTRL+C\n");
+
prin[i] = 0;
−
            printf("CTRL+V\n\n");
+
}
−
        }
+
 
 +
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);
 +
}
 
   
 
   
−
        for(i = 0; i < N%3; i++)
+
void print(int * prin, int n)
−
            printf("A\n");
+
{
−
    }
+
if(n < 1)
−
    printf("\nM = %lu\n", M);
+
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>
 
</syntaxhighlight>
  
Line 71: Line 186:
 
{{Template:FBD}}
 
{{Template:FBD}}
  
−
[[Category:Coding Questions for Placements]]
+
[[Category:Placement Coding Questions from Arrays]]

Latest revision as of 14:25, 23 July 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 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">

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

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




blog comments powered by Disqus
Retrieved from "https://gatecse.in/w/index.php?title=Printing_A&oldid=4119"

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>

int main() { 

   unsigned long N, M, i;
   printf("Enter N: ");
   scanf("%lu", &N);
   printf("\n\nKey Sequences:\n\n");
   if(N <= 6)
   {
       M = 6;
       for(i = 0; i < N; i++)
       printf("A\n");
   }

   else if (N % 3 == 0)
   {
       M = 3 * (1L<< (N-3)/3); //1<<x gives pow(2,x) and I'm too lazy to include math.h
       for(i = 0; i < 3; i++)
           printf("A\n");
       for(i = 1; i < N/3; i++)
       {
           printf("\nCTRL+A\n");
           printf("CTRL+C\n");
           printf("CTRL+V\n\n");
       }
   }

   else 
   {
       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("CTRL+V\n\n");
       }

       for(i = 0; i < N%3; i++)
           printf("A\n");
   } 
   printf("\nM = %lu\n", M);

} </syntaxhighlight>




blog comments powered by Disqus