How to print maximum number of A's using given four keys - GeeksforGeeks
Imagine you have a special keyboard with the following keys: Key 1: Prints 'A' on screen Key 2: (Ctrl-A): Select screen Key 3: (Ctrl-C): Copy selection to buffer Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed. If you can only press the keyboard for N times (with the above four keys), write a program to produce maximum numbers of A's. 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).
Recursive:
http://articles.leetcode.com/2011/01/ctrla-ctrlc-ctrlv.html -- A little different from geeksforgeeks
https://futurnist.wordpress.com/2012/05/22/1-a2-ctrla3-ctrlc/
When N is small, best strategy would be simply type A as much as possible.
When N is large, best strategy is to type A’s first and then start copy and paste. There’s no need to type A’s anymore after ^A is first pressed. Why? If another A is pressed after ^A is pressed, we can always swap these two key strokes and get a better solution, because we made one more letter in the clipboard by swapping.
When is a good time to update clipboard content by re-selecting everything? An upper bound is after a ^A^C^V action, it makes sense to press ^V at most 6 times. Original content is duplicated 7 times in this case. If you are allowed one more key stroke, the best option is NOT press ^V one more time and make an 8-th copy. Instead, the best option is (^A^C^V^V^V) followed by another cycle of itself. In the first cycle the original content is duplicated 3 times. In the second cycle the content is duplicated 9 times in total.
double from 4 steps before (^V pressed twice)
triple from 5 steps before (^V pressed three times)
4 times from 6 steps before
5 times from 7 steps before
6 times from 8 steps before
7 times from 9 steps before (^V pressed 6 times)
f(n) = max (
2*f(n-4),
3*f(n-5),
4*f(n-6),
5*f(n-7),
6*f(n-8),
7*f(n-9) // (N-b-1)*findoptimal(b);
)
def f(N):
li = [0, 1, 2, 3, 4, 5, 6, 7, 9]
for i in range(9, N + 1):
li.append(max(2*li[i-4], 3*li[i-5], 4*li[i-6], 5*li[i-7], 6*li[i-8], 7*li[i-9]))
return li[N]
http://articles.leetcode.com/2011/01/ctrla-ctrlc-ctrlv.html
1. For N < 7, the output is N itself. Please verify this yourself.
http://www.cnblogs.com/chkkch/archive/2012/11/04/2754297.html
Read full article from How to print maximum number of A's using given four keys - GeeksforGeeks
Imagine you have a special keyboard with the following keys: Key 1: Prints 'A' on screen Key 2: (Ctrl-A): Select screen Key 3: (Ctrl-C): Copy selection to buffer Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed. If you can only press the keyboard for N times (with the above four keys), write a program to produce maximum numbers of A's. 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).
int findoptimal(int N){ // The optimal string length is N when N is smaller than 7 if (N <= 6) return N; // An array to store result of subproblems int screen[N]; int b; // To pick a breakpoint // Initializing the optimal lengths array for uptil 6 input // strokes. int n; for (n=1; n<=6; n++) screen[n-1] = n; // Solve all subproblems in bottom manner for (n=7; n<=N; n++) { // Initialize length of optimal string for n keystrokes screen[n-1] = 0; // For any keystroke n, we need to loop from n-3 keystrokes // back to 1 keystroke to find a breakpoint 'b' after which we // will have ctrl-a, ctrl-c and then only ctrl-v all the way. for (b=n-3; b>=1; b--) { // if the breakpoint is at b'th keystroke then // the optimal string would have length // (n-b-1)*screen[b-1]; int curr = (n-b-1)*screen[b-1]; if (curr > screen[n-1]) screen[n-1] = curr; } } return screen[N-1];}int findoptimal(int N){ // The optimal string length is N when N is smaller than 7 if (N <= 6) return N; // Initialize result int max = 0; // TRY ALL POSSIBLE BREAK-POINTS // For any keystroke N, we need to loop from N-3 keystrokes // back to 1 keystroke to find a breakpoint 'b' after which we // will have Ctrl-A, Ctrl-C and then only Ctrl-V all the way. int b; for (b=N-3; b>=1; b--) { // If the breakpoint is s at b'th keystroke then // the optimal string would have length // (n-b-1)*screen[b-1]; int curr = (N-b-1)*findoptimal(b); if (curr > max) max = curr; } return max;}http://articles.leetcode.com/2011/01/ctrla-ctrlc-ctrlv.html -- A little different from geeksforgeeks
int findMaxK(int n) {
int power = 2;
double max = 0.0;
int maxK = 0;
while (n > 0) {
n -= 2;
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 <= 7) return n;
int k = findMaxK(n);
int sum = n - 2*(k-1);
unsigned int mul = 1;
while (k > 0) {
int avg = sum/k;
mul *= avg;
k--;
sum -= avg;
}
assert(sum == 0);
return mul;
}
https://futurnist.wordpress.com/2012/05/22/1-a2-ctrla3-ctrlc/
When N is small, best strategy would be simply type A as much as possible.
When N is large, best strategy is to type A’s first and then start copy and paste. There’s no need to type A’s anymore after ^A is first pressed. Why? If another A is pressed after ^A is pressed, we can always swap these two key strokes and get a better solution, because we made one more letter in the clipboard by swapping.
When is a good time to update clipboard content by re-selecting everything? An upper bound is after a ^A^C^V action, it makes sense to press ^V at most 6 times. Original content is duplicated 7 times in this case. If you are allowed one more key stroke, the best option is NOT press ^V one more time and make an 8-th copy. Instead, the best option is (^A^C^V^V^V) followed by another cycle of itself. In the first cycle the original content is duplicated 3 times. In the second cycle the content is duplicated 9 times in total.
double from 4 steps before (^V pressed twice)
triple from 5 steps before (^V pressed three times)
4 times from 6 steps before
5 times from 7 steps before
6 times from 8 steps before
7 times from 9 steps before (^V pressed 6 times)
f(n) = max (
2*f(n-4),
3*f(n-5),
4*f(n-6),
5*f(n-7),
6*f(n-8),
7*f(n-9) // (N-b-1)*findoptimal(b);
)
def f(N):
li = [0, 1, 2, 3, 4, 5, 6, 7, 9]
for i in range(9, N + 1):
li.append(max(2*li[i-4], 3*li[i-5], 4*li[i-6], 5*li[i-7], 6*li[i-8], 7*li[i-9]))
return li[N]
http://articles.leetcode.com/2011/01/ctrla-ctrlc-ctrlv.html
int findMaxK(int n) {
int power = 2;
double max = 0.0;
int maxK = 0;
while (n > 0) {
n -= 2;
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 <= 7) return n;
int k = findMaxK(n);
int sum = n - 2*(k-1);
unsigned int mul = 1;
while (k > 0) {
int avg = sum/k;
mul *= avg;
k--;
sum -= avg;
}
assert(sum == 0);
return mul;
}
http://www.ideserve.co.in/learn/how-to-print-maximum-number-of-a-using-given-four-keys
1. For N < 7, the output is N itself. Please verify this yourself.
2. If you notice, to produce the maximum number of A's, the sequence of N keystrokes that will be used will end with a suffix of Ctrl-A, Ctrl-C, followed by only Ctrl-V's (For N > 6).
3. The task is to find out the critical-point after which we get the above suffix of keystrokes.
4. A critical-point is that instance after which we need to only press Ctrl-A, Ctrl-C once and the only Ctrl-V's afterwards to generate maximum number of A's.
5. We loop from N-3 to 1 and choose each of these values for the critical-point, and compute that optimal string they would produce. While computing optimal number of As for each critical point, we use optimal number of As already computed for number of keystrokes < N.
6. Once the above loop ends, we will have the maximum of the optimal lengths for various critical-points, thereby giving us the optimal length for N keystrokes.
// assuming max input for 'n' won't be greater than 10. // you might want to change it according to your need. private static int MAX = 10; public static int findMaxAs(int n, int[] maxAsSolution) { if (n <= 6) return n; int maxSoFar = 0, maxAsWithThis_i = 0, multiplier = 2; for (int i = n-3; i >=0; i--) { if (maxAsSolution[i] == -1) { maxAsSolution[i] = findMaxAs(i, maxAsSolution); } maxAsWithThis_i = multiplier*maxAsSolution[i]; if(maxAsWithThis_i > maxSoFar) { maxSoFar = maxAsWithThis_i; } multiplier +=1; } return maxSoFar; }http://www.cnblogs.com/chkkch/archive/2012/11/04/2754297.html
打印这种类似最大结果的问题一般都会想到用DP
f[i][4]: 表示有四种方法，f[i][j] = max(f[i-1][k] + 各种操作)
如果要打印每个操作步骤，则要再设一个parent[i][j]数组，记录他的前任操作是哪个，然后递归调用。
http://www.careercup.com/question?id=7184083Read full article from How to print maximum number of A's using given four keys - GeeksforGeeks
