(http://leetcode.com/2011/01/ctrla-ctrlc-ctrlv.html)
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).
The Code:
int findMaxK(int n)
{
int power = ;
double max = 0.0;
int maxK = ;
while (n > )
{
n -= ;
double t = (double)n/power;
double r = pow(t, (double)power);
if (r > max)
{
maxK = power;
max = r;
}
power++;
}
return maxK;
} unsigned int f(int n)
{
if (n <= )
return n;
int k = findMaxK(n); int sum = n - *(k-);
unsigned int mul = ;
while (k > )
{
int avg = sum/k;
mul *= avg;
k--;
sum -= avg;
}
assert(sum == ); return mul;
}