Difference between revisions of "Printing A"

 
(27 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
Imagine you have a special keyboard with the following keys:
 
Imagine you have a special keyboard with the following keys:
 +
 
A
 
A
 +
 
Ctrl+A
 
Ctrl+A
 +
 
Ctrl+C
 
Ctrl+C
 +
 
Ctrl+V
 
Ctrl+V
 +
 
where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste”
 
where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste”
 
operations respectively.
 
operations respectively.
 +
 
If you can only press the keyboard for N times (with the above four keys), please write a program to produce
 
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.
 
maximum numbers of A. If possible, please also print out the sequence of keys.
Line 12: 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()
 
int main()
 
{
 
{
−
    int N, M, i;
+
unsigned int n, i;
−
    printf("Enter N: ");
+
unsigned long long sol[1000];
−
    scanf("%d", &N);
+
unsigned int prin[1000];
−
    if(N <= 6)
+
printf("Enter N: ");
−
    {
+
scanf("%u", &n);
−
        M = 6;
+
−
        for(i = 0; i < N; i++)
+
for(i = 1 ;n>5? i<=5: i<= n; i++)
−
        printf("A\n");
+
{
−
    }
+
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");
 +
}
 +
}
  
−
    else if (N % 3 == 0)
+
</syntaxhighlight>
−
    {
+
 
−
        M = 3 * (1<< (2, (N-3)/3)); //1<<x gives pow(2,x)
+
===Alternate Solution===
−
        for(i = 0; i < 3; i++)
+
 
−
            printf("A\n");
+
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:
−
        for(i = 1; i < N/3; i++)
+
 
−
        {
+
sol[n] = max(2 * sol[n-4], 3 * sol[n-5], 4 * sol[n-6], 5 * sol[n-7]) | n > 7
−
            printf("Select\n");
+
and
−
            printf("Copy\n");
+
1 for 1<= n <= 7
−
            printf("Paste\n");
+
 
−
        }
+
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 ;
 +
}
  
−
    else
+
−
    {
+
//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)
−
        M = 4 * (1 << (2, (N-4)/3)) + (N-4)%3; //1<<x gives pow(2,x)
+
int maxp(int a, int b, int c, int d)
−
        for(i = 0; i < 4; i++)
+
{
−
            printf("A\n");
+
    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=0; i < (N-4)/3; i++)
+
for(i = 8; i <= n; i++)
−
        {
+
{
−
            printf("Select\n");
+
sol[i] = max(  2 * sol[i-4], 3 * sol[i-5], 4 * sol [i-6], 5 * sol[i-7]);
−
            printf("Copy\n");
+
prin[i] = maxp( 2 * sol[i-4], 3 * sol[i-5], 4 * sol [i-6], 5 * sol[i-7]);
−
            printf("Paste\n");
+
}
−
        }
+
printf("M = %llu\n", sol[n]);
−
   
+
printf("Enter any char to start printing the key sequence: \n");
−
        for(i = 0; i < N%3; i++)
+
scanf("%d", &n);
−
            printf("A\n");
+
printf("Printing the sequence: \n\n");
−
    }
+
print(prin, n);
−
    printf("\nM = %d\n", M);
 
 
}
 
}
 +
 +
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>
 
</syntaxhighlight>
 +
  
 
{{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() { 

   int N, M, i;
   printf("Enter N: ");
   scanf("%d", &N);
   if(N <= 6)
   {
       M = 6;
       for(i = 0; i < N; i++)
       printf("A\n");
   }

   else if (N % 3 == 0)
   {
       M = 3 * (1<< (2, (N-3)/3)); //1<<x gives pow(2,x)
       for(i = 0; i < 3; i++)
           printf("A\n");
       for(i = 1; i < N/3; i++)
       {
           printf("Select\n");
           printf("Copy\n");
           printf("Paste\n");
       }
   }

   else 
   {
       M = 4 * (1 << (2, (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("Select\n");
           printf("Copy\n");
           printf("Paste\n");
       }
   
       for(i = 0; i < N%3; i++)
           printf("A\n");
   } 
   printf("\nM = %d\n", M);

} </syntaxhighlight>




blog comments powered by Disqus