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
<syntaxhighlight lang="c" name="printa">
int max(int a, int b, int c) { return a > b ? a > c? a:c : b > c? 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>
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
<syntaxhighlight lang="c" name="printa">
int max(int a, int b, int c) { return a > b ? a > c? a:c : b > c? 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>
GATECSE