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> | ||
| − | + | ||
| + | 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() | 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> | </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 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).
<syntaxhighlight lang="c" name="printa">
int main() {
GATECSE 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>