Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 24: | Line 24: | ||
1 for 1<= n <= 6 | 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 | + | 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"> | <syntaxhighlight lang="c" name="printa"> | ||
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).
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">
//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>
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).
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">
//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>
GATECSE