Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 21: | Line 21: | ||
<syntaxhighlight lang="c" name="printa"> | <syntaxhighlight lang="c" name="printa"> | ||
#include <stdio.h> | #include <stdio.h> | ||
− | + | #include <string.h> | |
+ | |||
int main() | int main() | ||
{ | { | ||
− | unsigned | + | unsigned int N, i, j; |
+ | unsigned long long M; | ||
+ | unsigned long long sol[1000]; | ||
+ | unsigned long long buf[3]; | ||
+ | unsigned int ind[1000]; | ||
printf("Enter N: "); | printf("Enter N: "); | ||
scanf("%lu", &N); | scanf("%lu", &N); | ||
− | + | ||
− | + | unsigned long long arr[3]; | |
+ | memset(arr, 0, 3*sizeof(arr[0])); | ||
+ | memset(sol, 0, 1000*sizeof(sol[0])); | ||
+ | /* | ||
+ | arr[0] = 4; | ||
+ | buf[0] = 1; | ||
+ | arr[1] = 6; | ||
+ | buf[1] = 2; | ||
+ | arr[2] = 6; | ||
+ | buf[2] = 3; | ||
+ | */ | ||
+ | arr[0] = 4; | ||
+ | buf[0] = 1; | ||
+ | arr[1] = 6; | ||
+ | buf[1] = 2; | ||
+ | arr[2] = 6; | ||
+ | buf[2] = 3; | ||
+ | unsigned index; | ||
+ | char * out[] = { "A\n", "CTRL+A\n", "CTRL+C\n", "CTRL+V\n"}; | ||
+ | unsigned int outf[1000]; | ||
+ | unsigned p = 2, pp = 3; | ||
+ | memset(outf, 0, 1000*sizeof(outf[0])); | ||
+ | for(i=1; i<=N; i++) | ||
{ | { | ||
− | + | if(i <= 6) | |
− | for(i = 0; i < | + | { |
− | + | outf[i] = 0; | |
+ | sol[i] = i; | ||
+ | ind[i] = 0; | ||
+ | ind[6] = 3; | ||
+ | |||
+ | } | ||
+ | |||
+ | else | ||
+ | { | ||
+ | printf("\n\ni = %u\n", i); | ||
+ | arr[0] = arr[1] + buf[1]; | ||
+ | arr[1] = arr[2] + buf[2]; | ||
+ | arr[2] = 2 * sol[i-3]; | ||
+ | buf[0] = buf[1]; | ||
+ | buf[1] = buf[2]; | ||
+ | buf[2] = sol[i-3]; | ||
+ | if(arr[0] > arr[1]) | ||
+ | { | ||
+ | if(arr[0] > arr[2]) | ||
+ | { | ||
+ | index = i-5; | ||
+ | sol[i] = arr[0]; | ||
+ | |||
+ | |||
+ | // outf[i] = outf[i-1]; | ||
+ | //outf[i-1] = outf[i-2]; | ||
+ | if(p > 3){ | ||
+ | outf[p+1] = 1; | ||
+ | outf[p+2] = 2; | ||
+ | } | ||
+ | |||
+ | // for(j = 0; j < buf[0]; j++) | ||
+ | // outf[j] = 0; | ||
+ | for(j = p+3; j <=i; j++) | ||
+ | outf[j] = 3; | ||
+ | ind[i] = p; | ||
+ | if(ind[p] >= 3){ | ||
+ | outf[ind[p]+1] = 1; | ||
+ | outf[ind[p]+2] = 2; | ||
+ | } | ||
+ | |||
+ | for(j = ind[p]+3; j <= p; j++) | ||
+ | outf[j] = 3; | ||
+ | |||
+ | } | ||
+ | else | ||
+ | { | ||
+ | |||
+ | index = i-3; | ||
+ | sol[i] = arr[2]; | ||
+ | outf[i] = 3; | ||
+ | |||
+ | outf[i-1] = 2; | ||
+ | outf[i-2] = 1; | ||
+ | |||
+ | outf[i-1] = 2; | ||
+ | outf[i-2] = 1; | ||
+ | |||
+ | ind[i] = i-3; | ||
+ | outf[ind[i-3]+1] = 1; | ||
+ | outf[ind[i-3]+2] = 2; | ||
+ | for(j = ind[i-3]+3; j < i-3; j++) | ||
+ | { | ||
+ | outf[j] = 3; | ||
+ | } | ||
+ | // p = pp; | ||
+ | // pp = i -3; | ||
+ | // printf("CTRL+A\nCTRL+C\nCTRL+V\n"); | ||
+ | } | ||
+ | } | ||
+ | else if (arr[1] > arr[2]) | ||
+ | { | ||
+ | index = i-4; | ||
+ | sol[i] = arr[1]; | ||
+ | |||
+ | outf[pp+1] = 1; | ||
+ | outf[pp+2] = 2; | ||
+ | |||
+ | // for(j = 0; j < buf[1]; j++) | ||
+ | // outf[j] = 0; | ||
+ | for(j = pp+3; j <=i; j++) | ||
+ | outf[j] = 3; | ||
+ | ind[i] = pp; | ||
+ | if(ind[pp] >= 3){ | ||
+ | outf[ind[pp]+1] = 1; | ||
+ | outf[ind[pp]+2] = 2; | ||
+ | } | ||
+ | for(j = ind[pp]+3; j <= pp; j++) | ||
+ | outf[j] = 3; | ||
+ | |||
+ | //outf[i-1] = outf[i-2]; | ||
+ | //outf[i-2]= outf[i-3]; | ||
+ | //printf("CTRL+V\n"); | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | |||
+ | index = i-3; | ||
+ | sol[i] = arr[2]; | ||
+ | outf[i] = 3; | ||
+ | |||
+ | outf[i-1] = 2; | ||
+ | outf[i-2] = 1; | ||
+ | |||
+ | ind[i] = i-3; | ||
+ | outf[ind[i-3]+1] = 1; | ||
+ | outf[ind[i-3]+2] = 2; | ||
+ | for(j = ind[i-3]+3; j < i-3; j++) | ||
+ | { | ||
+ | outf[j] = 3; | ||
+ | } | ||
+ | //p = pp; | ||
+ | // pp = i -3; | ||
+ | |||
+ | //printf("CTRL+A\nCTRL+C\nCTRL+V\n"); | ||
+ | |||
+ | } | ||
+ | |||
+ | // sol[i] = max(arr[0] , arr[1], arr[2]); | ||
+ | |||
+ | printf("\n%lld %lld %lld\n", arr[0], arr[1], arr[2]); | ||
+ | printf("%lld %lld %lld\n", buf[0], buf[1], buf[2]); | ||
+ | printf("p = %u pp = %u\n", p, pp); | ||
+ | for(j = 1; j <= i; j++) | ||
+ | { | ||
+ | |||
+ | // printf(out[outf[j]]); | ||
+ | } | ||
+ | p = pp; | ||
+ | pp = i - 3; | ||
+ | } | ||
} | } | ||
− | + | i = 1; | |
− | + | while(i+1 < N && outf[i+1] != 2) | |
{ | { | ||
− | + | outf[i] = 0; | |
− | + | i++; | |
− | + | } | |
− | for(i = 1; i < N | + | printf("\n\nKey Sequences:\n\n"); |
+ | // if(N <= 6) | ||
+ | { | ||
+ | // printf("A\nA\nA\nA\nA\nA\n"); | ||
+ | |||
+ | } | ||
+ | //else | ||
+ | { | ||
+ | for(i = 1; i <= N; i++) | ||
{ | { | ||
− | + | ||
− | + | printf(out[outf[i]]); | |
− | printf( | ||
} | } | ||
− | + | } | |
− | + | ||
− | + | for(i = 1; i <= N; i++) | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{ | { | ||
− | + | ||
− | + | printf("%u ",ind[i]); | |
− | printf(" | ||
} | } | ||
− | + | printf("\nM = %llu\n", sol[N]); | |
− | + | ||
− | |||
− | |||
− | printf("\nM = % | ||
} | } | ||
+ | |||
+ | |||
</syntaxhighlight> | </syntaxhighlight> | ||
{{Template:FBD}} | {{Template:FBD}} |
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).
<syntaxhighlight lang="c" name="printa">
int main() {
unsigned int N, i, j; unsigned long long M; unsigned long long sol[1000]; unsigned long long buf[3]; unsigned int ind[1000]; printf("Enter N: "); scanf("%lu", &N); unsigned long long arr[3]; memset(arr, 0, 3*sizeof(arr[0])); memset(sol, 0, 1000*sizeof(sol[0])); /* arr[0] = 4; buf[0] = 1; arr[1] = 6; buf[1] = 2; arr[2] = 6; buf[2] = 3; */ arr[0] = 4; buf[0] = 1; arr[1] = 6; buf[1] = 2; arr[2] = 6; buf[2] = 3; unsigned index; char * out[] = { "A\n", "CTRL+A\n", "CTRL+C\n", "CTRL+V\n"}; unsigned int outf[1000]; unsigned p = 2, pp = 3; memset(outf, 0, 1000*sizeof(outf[0])); for(i=1; i<=N; i++) { if(i <= 6) { outf[i] = 0; sol[i] = i; ind[i] = 0; ind[6] = 3; } else { printf("\n\ni = %u\n", i); arr[0] = arr[1] + buf[1]; arr[1] = arr[2] + buf[2]; arr[2] = 2 * sol[i-3]; buf[0] = buf[1]; buf[1] = buf[2]; buf[2] = sol[i-3]; if(arr[0] > arr[1]) { if(arr[0] > arr[2]) { index = i-5; sol[i] = arr[0]; // outf[i] = outf[i-1]; //outf[i-1] = outf[i-2]; if(p > 3){ outf[p+1] = 1; outf[p+2] = 2; } // for(j = 0; j < buf[0]; j++) // outf[j] = 0; for(j = p+3; j <=i; j++) outf[j] = 3; ind[i] = p; if(ind[p] >= 3){ outf[ind[p]+1] = 1; outf[ind[p]+2] = 2; } for(j = ind[p]+3; j <= p; j++) outf[j] = 3; } else { index = i-3; sol[i] = arr[2]; outf[i] = 3; outf[i-1] = 2; outf[i-2] = 1; outf[i-1] = 2; outf[i-2] = 1; ind[i] = i-3; outf[ind[i-3]+1] = 1; outf[ind[i-3]+2] = 2; for(j = ind[i-3]+3; j < i-3; j++) { outf[j] = 3; } // p = pp; // pp = i -3; // printf("CTRL+A\nCTRL+C\nCTRL+V\n"); } } else if (arr[1] > arr[2]) { index = i-4; sol[i] = arr[1]; outf[pp+1] = 1; outf[pp+2] = 2; // for(j = 0; j < buf[1]; j++) // outf[j] = 0; for(j = pp+3; j <=i; j++) outf[j] = 3; ind[i] = pp; if(ind[pp] >= 3){ outf[ind[pp]+1] = 1; outf[ind[pp]+2] = 2; } for(j = ind[pp]+3; j <= pp; j++) outf[j] = 3; //outf[i-1] = outf[i-2]; //outf[i-2]= outf[i-3]; //printf("CTRL+V\n"); } else { index = i-3; sol[i] = arr[2]; outf[i] = 3; outf[i-1] = 2; outf[i-2] = 1; ind[i] = i-3; outf[ind[i-3]+1] = 1; outf[ind[i-3]+2] = 2; for(j = ind[i-3]+3; j < i-3; j++) { outf[j] = 3; } //p = pp; // pp = i -3; //printf("CTRL+A\nCTRL+C\nCTRL+V\n"); } // sol[i] = max(arr[0] , arr[1], arr[2]); printf("\n%lld %lld %lld\n", arr[0], arr[1], arr[2]); printf("%lld %lld %lld\n", buf[0], buf[1], buf[2]); printf("p = %u pp = %u\n", p, pp); for(j = 1; j <= i; j++) { // printf(out[outf[j]]); } p = pp; pp = i - 3; } } i = 1; while(i+1 < N && outf[i+1] != 2) { outf[i] = 0; i++; } printf("\n\nKey Sequences:\n\n"); // if(N <= 6) { // printf("A\nA\nA\nA\nA\nA\n"); } //else { for(i = 1; i <= N; i++) { printf(out[outf[i]]); } } for(i = 1; i <= N; i++) { printf("%u ",ind[i]); } printf("\nM = %llu\n", sol[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).
<syntaxhighlight lang="c" name="printa">
int main() {
unsigned int N, i, j; unsigned long long M; unsigned long long sol[1000]; unsigned long long buf[3]; unsigned int ind[1000]; printf("Enter N: "); scanf("%lu", &N); unsigned long long arr[3]; memset(arr, 0, 3*sizeof(arr[0])); memset(sol, 0, 1000*sizeof(sol[0])); /* arr[0] = 4; buf[0] = 1; arr[1] = 6; buf[1] = 2; arr[2] = 6; buf[2] = 3; */ arr[0] = 4; buf[0] = 1; arr[1] = 6; buf[1] = 2; arr[2] = 6; buf[2] = 3; unsigned index; char * out[] = { "A\n", "CTRL+A\n", "CTRL+C\n", "CTRL+V\n"}; unsigned int outf[1000]; unsigned p = 2, pp = 3; memset(outf, 0, 1000*sizeof(outf[0])); for(i=1; i<=N; i++) { if(i <= 6) { outf[i] = 0; sol[i] = i; ind[i] = 0; ind[6] = 3; } else { printf("\n\ni = %u\n", i); arr[0] = arr[1] + buf[1]; arr[1] = arr[2] + buf[2]; arr[2] = 2 * sol[i-3]; buf[0] = buf[1]; buf[1] = buf[2]; buf[2] = sol[i-3]; if(arr[0] > arr[1]) { if(arr[0] > arr[2]) { index = i-5; sol[i] = arr[0]; // outf[i] = outf[i-1]; //outf[i-1] = outf[i-2]; if(p > 3){ outf[p+1] = 1; outf[p+2] = 2; } // for(j = 0; j < buf[0]; j++) // outf[j] = 0; for(j = p+3; j <=i; j++) outf[j] = 3; ind[i] = p; if(ind[p] >= 3){ outf[ind[p]+1] = 1; outf[ind[p]+2] = 2; } for(j = ind[p]+3; j <= p; j++) outf[j] = 3; } else { index = i-3; sol[i] = arr[2]; outf[i] = 3; outf[i-1] = 2; outf[i-2] = 1; outf[i-1] = 2; outf[i-2] = 1; ind[i] = i-3; outf[ind[i-3]+1] = 1; outf[ind[i-3]+2] = 2; for(j = ind[i-3]+3; j < i-3; j++) { outf[j] = 3; } // p = pp; // pp = i -3; // printf("CTRL+A\nCTRL+C\nCTRL+V\n"); } } else if (arr[1] > arr[2]) { index = i-4; sol[i] = arr[1]; outf[pp+1] = 1; outf[pp+2] = 2; // for(j = 0; j < buf[1]; j++) // outf[j] = 0; for(j = pp+3; j <=i; j++) outf[j] = 3; ind[i] = pp; if(ind[pp] >= 3){ outf[ind[pp]+1] = 1; outf[ind[pp]+2] = 2; } for(j = ind[pp]+3; j <= pp; j++) outf[j] = 3; //outf[i-1] = outf[i-2]; //outf[i-2]= outf[i-3]; //printf("CTRL+V\n"); } else { index = i-3; sol[i] = arr[2]; outf[i] = 3; outf[i-1] = 2; outf[i-2] = 1; ind[i] = i-3; outf[ind[i-3]+1] = 1; outf[ind[i-3]+2] = 2; for(j = ind[i-3]+3; j < i-3; j++) { outf[j] = 3; } //p = pp; // pp = i -3; //printf("CTRL+A\nCTRL+C\nCTRL+V\n"); } // sol[i] = max(arr[0] , arr[1], arr[2]); printf("\n%lld %lld %lld\n", arr[0], arr[1], arr[2]); printf("%lld %lld %lld\n", buf[0], buf[1], buf[2]); printf("p = %u pp = %u\n", p, pp); for(j = 1; j <= i; j++) { // printf(out[outf[j]]); } p = pp; pp = i - 3; } } i = 1; while(i+1 < N && outf[i+1] != 2) { outf[i] = 0; i++; } printf("\n\nKey Sequences:\n\n"); // if(N <= 6) { // printf("A\nA\nA\nA\nA\nA\n"); } //else { for(i = 1; i <= N; i++) { printf(out[outf[i]]); } } for(i = 1; i <= N; i++) { printf("%u ",ind[i]); } printf("\nM = %llu\n", sol[N]);
}
</syntaxhighlight>