a***o
发帖数: 24 | 1 Google Interview Question for Software Enginee
题目如下：
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
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).
给了大约30分钟时间，最后没搞定。请各位大侠赐教，谢谢！ | h**6
发帖数: 4160 | 2 新年早起来做题：
令 m = f(n)
if n≤6, f(n) = n
if n>6, f(n) = max{2*f(n-3), 3*f(n-4), 4*f(n-5), 5*f(n-6)}
后面 6*f(n-7) 就没有必要了，因为 3*f(n-4)≥6*f(n-7)
如果需要打印，也很简单。另外定义一个数组 g(n)，记录每次的比较结果。
n f(n) g(n)
1 1 0
2 2 0
3 3 0
4 4 0
5 5 0
6 6 0
7 9 3
8 12 4
9 16 4
10 20 5
11 27 7
12 36 8
13 48 9
14 64 9
如f(14)=64，那么打印时可逆推数组 g(14)=9, g(9)=4。也就是先输入4个A，然后在4、9这几个地方使用全选、复制，别的时候就粘贴。 | g*******s
发帖数: 490 | | a***o
发帖数: 24 | 4 大虾呀，你这样做是不对的呀。
因为，Ctrl+A, Ctrl+C, Ctrl+V 不能直接double前面A的个数呀，也就是说，Ctrl+A,
Ctrl+C, Ctrl+V，Ctrl+V才可以double前面A的个数.
【在 h**6 的大作中提到】
: 新年早起来做题：
: 令 m = f(n)
: if n≤6, f(n) = n
: if n>6, f(n) = max{2*f(n-3), 3*f(n-4), 4*f(n-5), 5*f(n-6)}
: 后面 6*f(n-7) 就没有必要了，因为 3*f(n-4)≥6*f(n-7)
: 如果需要打印，也很简单。另外定义一个数组 g(n)，记录每次的比较结果。
: n f(n) g(n)
: 1 1 0
: 2 2 0
: 3 3 0
| a***o
发帖数: 24 | 5 组合键算一个Key
【在 g*******s 的大作中提到】
: ctrl+c算是一个Key还是两个？
| h**6
发帖数: 4160 | 6 新年早起来做题之二：
令 m = f(n)
if n≤0, f(n) = 0
if n>0, f(n) = max{f(n-1)+1, 2*f(n-4), 3*f(n-5), 4*f(n-6), 5*f(n-7), 6*f(n-8), 7*f(n-9)}
后面 8*f(n-10) 就没有必要了，因为 4*f(n-6)≥8*f(n-10)
如果需要打印，也很简单。另外定义一个数组 g(n)，记录每次的比较结果。
n f(n) g(n)
1 1 0
2 2 0
3 3 0
4 4 0
5 5 0
6 6 0
7 7 0
8 9 3
9 12 4
10 16 4
11 20 5
12 25 5
13 30 6
14 36 9
15 48 10
16 64 10
如f(16)=64，那么打印时可逆推数组 g(16)=10, g(10)=4。也就是先输入4个A，然后在
4、10这几个地方使用全选、复制，别的时候就粘贴。
这回该对了吧。 | g*******s
发帖数: 490 | 7 A，C，V，V可以让目前的数翻倍，4个KEY。假设目前是n个A，所以n>=4的情况下，都应
该A, C, V, V > 直接type A
再来看A,C,V,V
假设目前是n个A，之前的复制基数是n/2
余留4个key,
A，C，V，V 4个key之后是2n,复制基数变成n
V,V,V,V之后是3n,复制基数还是n/2
再看余留6个key
A,C,V,V,V,V可以给4n,基数变n
V,V,V,V,V,V可以给4n，基数还是n/2
6个key升4倍应该是最优情况了
所以假设一共只可以按m次key, 最后A的个数是f(m)
case 1: m <=8,
f(m) = m
case 2: m >8,
前8次最有利的必然是TYPE 4个A,然后A,C,V,V
then check (m-8)%6, 6个key的操作就是A,C,V,V,V,V，余数用什么key就再根据余几个和(m-8)/6的结果选择 | a***o
发帖数: 24 | 8 这次貌似是对的，我再仔细看看哦，大虾。
【在 h**6 的大作中提到】
: 新年早起来做题：
: 令 m = f(n)
: if n≤6, f(n) = n
: if n>6, f(n) = max{2*f(n-3), 3*f(n-4), 4*f(n-5), 5*f(n-6)}
: 后面 6*f(n-7) 就没有必要了，因为 3*f(n-4)≥6*f(n-7)
: 如果需要打印，也很简单。另外定义一个数组 g(n)，记录每次的比较结果。
: n f(n) g(n)
: 1 1 0
: 2 2 0
: 3 3 0
| a***o
发帖数: 24 | 9 看着有点晕，我研究下。
【在 g*******s 的大作中提到】
: A，C，V，V可以让目前的数翻倍，4个KEY。假设目前是n个A，所以n>=4的情况下，都应
: 该A, C, V, V > 直接type A
: 再来看A,C,V,V
: 假设目前是n个A，之前的复制基数是n/2
: 余留4个key,
: A，C，V，V 4个key之后是2n,复制基数变成n
: V,V,V,V之后是3n,复制基数还是n/2
: 再看余留6个key
: A,C,V,V,V,V可以给4n,基数变n
: V,V,V,V,V,V可以给4n，基数还是n/2
| g*******s
发帖数: 490 | 10 余留4个key，最多可以翻3倍
-8), 7*f(n-9)}
【在 h**6 的大作中提到】
: 新年早起来做题之二：
: 令 m = f(n)
: if n≤0, f(n) = 0
: if n>0, f(n) = max{f(n-1)+1, 2*f(n-4), 3*f(n-5), 4*f(n-6), 5*f(n-7), 6*f(n-8), 7*f(n-9)}
: 后面 8*f(n-10) 就没有必要了，因为 4*f(n-6)≥8*f(n-10)
: 如果需要打印，也很简单。另外定义一个数组 g(n)，记录每次的比较结果。
: n f(n) g(n)
: 1 1 0
: 2 2 0
: 3 3 0
| | | a***o
发帖数: 24 | 11 大虾，你的方法不对呀，
比如，
n=8时，m=9，输入顺序为 AAA23444；
n=12, m=25, 输入顺序为 AAAAA2344444,
不是前8步一定是AAAA，然后2344呀。
【在 g*******s 的大作中提到】
: A，C，V，V可以让目前的数翻倍，4个KEY。假设目前是n个A，所以n>=4的情况下，都应
: 该A, C, V, V > 直接type A
: 再来看A,C,V,V
: 假设目前是n个A，之前的复制基数是n/2
: 余留4个key,
: A，C，V，V 4个key之后是2n,复制基数变成n
: V,V,V,V之后是3n,复制基数还是n/2
: 再看余留6个key
: A,C,V,V,V,V可以给4n,基数变n
: V,V,V,V,V,V可以给4n，基数还是n/2
| g*******s
发帖数: 490 | 12 恩，你的应该是对的，4个key翻3倍应该也是没法出现，因为其他key的最大组合没办法
让复制基数保持在当前A个数的一半，所以
【在 a***o 的大作中提到】
: 大虾，你的方法不对呀，
: 比如，
: n=8时，m=9，输入顺序为 AAA23444；
: n=12, m=25, 输入顺序为 AAAAA2344444,
: 不是前8步一定是AAAA，然后2344呀。
| a***o
发帖数: 24 | 13 请问这步“后面 8*f(n-10) 就没有必要了，因为 4*f(n-6)≥8*f(n-10)” 是怎么得出
来的？
谢谢
6*f(n-8), 7*f(n-9)}
【在 h**6 的大作中提到】
: 新年早起来做题之二：
: 令 m = f(n)
: if n≤0, f(n) = 0
: if n>0, f(n) = max{f(n-1)+1, 2*f(n-4), 3*f(n-5), 4*f(n-6), 5*f(n-7), 6*f(n-8), 7*f(n-9)}
: 后面 8*f(n-10) 就没有必要了，因为 4*f(n-6)≥8*f(n-10)
: 如果需要打印，也很简单。另外定义一个数组 g(n)，记录每次的比较结果。
: n f(n) g(n)
: 1 1 0
: 2 2 0
: 3 3 0
| a***o
发帖数: 24 | 14 我刚才验证了你的方法，在只使用到两次2344的时候是对的，但是当N足够大，也就是
可能使用到好几
次2344的时候，你的方法好像就不对了。
因为实际上，这道题好像用dynamic programming最不了，因为它不存在optimal
structure。
你的现在所使用的这个optimal structure是在只使用两次2344的时候得出来的，要用
到多次2344
的时候，这个optimal structure就不hold啦。 望指正。
6*f(n-8), 7*f(n-9)}
【在 h**6 的大作中提到】
: 新年早起来做题之二：
: 令 m = f(n)
: if n≤0, f(n) = 0
: if n>0, f(n) = max{f(n-1)+1, 2*f(n-4), 3*f(n-5), 4*f(n-6), 5*f(n-7), 6*f(n-8), 7*f(n-9)}
: 后面 8*f(n-10) 就没有必要了，因为 4*f(n-6)≥8*f(n-10)
: 如果需要打印，也很简单。另外定义一个数组 g(n)，记录每次的比较结果。
: n f(n) g(n)
: 1 1 0
: 2 2 0
: 3 3 0
| g*******s
发帖数: 490 | 15 能把n从14-26的结果贴出来看看么
【在 a***o 的大作中提到】
: 我刚才验证了你的方法，在只使用到两次2344的时候是对的，但是当N足够大，也就是
: 可能使用到好几
: 次2344的时候，你的方法好像就不对了。
: 因为实际上，这道题好像用dynamic programming最不了，因为它不存在optimal
: structure。
: 你的现在所使用的这个optimal structure是在只使用两次2344的时候得出来的，要用
: 到多次2344
: 的时候，这个optimal structure就不hold啦。 望指正。
:
: 6*f(n-8), 7*f(n-9)}
| g*******s
发帖数: 490 | 16 因为2*f(n-4)是4 key可能的max（其实应该是3倍，但是感觉上没办法达到）,4*f(n-6)是6key的max
n-10 = n-4-6 = 2*4*f(n-10)=8*f(n-10)，所以8倍是=,但是还是可以3*4,所以是〉=
【在 a***o 的大作中提到】
: 请问这步“后面 8*f(n-10) 就没有必要了，因为 4*f(n-6)≥8*f(n-10)” 是怎么得出
: 来的？
: 谢谢
:
: 6*f(n-8), 7*f(n-9)}
| a***o
发帖数: 24 | 17 我没有正确答案。 我只是感觉上面那位仁兄的算法好像是对的，细节方面，我在仔细
研究。
这是我刚才用笔写的，应该是对的
n=7, m=7, AAAAAAA
n=8, m=9, AAA23444
n=9, m=12, AAAA23444, or AAA234444
n=10, m=16, AAAA234444
n=11, m=20, AAAA2344444, or AAAAA234444
n=12, m=25, AAAAA2344444,
n=13, m=30, AAAAA23444444, or AAAAAA2344444,
n=14, m=36, AAAAAA23444444,
n=15, m=48, AAAA23444234444,
n=16, m=64, AAAA234444234444,
【在 g*******s 的大作中提到】
: 能把n从14-26的结果贴出来看看么
| g*******s
发帖数: 490 | 18 他的方法应该是对的，因为6个key升4倍是最好的情况了，一个key 2/3倍，其他的7，8
，9，10，11就是除6，商〉=1，余数为1，2，3，4，5的情况
【在 a***o 的大作中提到】
: 我刚才验证了你的方法，在只使用到两次2344的时候是对的，但是当N足够大，也就是
: 可能使用到好几
: 次2344的时候，你的方法好像就不对了。
: 因为实际上，这道题好像用dynamic programming最不了，因为它不存在optimal
: structure。
: 你的现在所使用的这个optimal structure是在只使用两次2344的时候得出来的，要用
: 到多次2344
: 的时候，这个optimal structure就不hold啦。 望指正。
:
: 6*f(n-8), 7*f(n-9)}
| y*****a
发帖数: 221 | 19 这个我倒是看明白了，
因为f(n-6)是一排数里取max得来的，f(n-10)对应f(n-6-4)那项
所以 f(n-6) >= 2*f(n-6-4）
【在 a***o 的大作中提到】
: 请问这步“后面 8*f(n-10) 就没有必要了，因为 4*f(n-6)≥8*f(n-10)” 是怎么得出
: 来的？
: 谢谢
:
: 6*f(n-8), 7*f(n-9)}
| a***o
发帖数: 24 | 20 明白了，谢谢了！
【在 y*****a 的大作中提到】
: 这个我倒是看明白了，
: 因为f(n-6)是一排数里取max得来的，f(n-10)对应f(n-6-4)那项
: 所以 f(n-6) >= 2*f(n-6-4）
| | | a***o
发帖数: 24 | 21 大虾，能讲讲你解这个题的思路么？我当时第一感觉是用Dynamic programming. 不过，没想到要比到n-9, 后来加上紧张，思路就乱了，结果就挂了。一般的Dynamic Programming都没有需要比较这么多项，你是怎么想到的，谢谢大虾。
-8), 7*f(n-9)}
【在 h**6 的大作中提到】
: 新年早起来做题之二：
: 令 m = f(n)
: if n≤0, f(n) = 0
: if n>0, f(n) = max{f(n-1)+1, 2*f(n-4), 3*f(n-5), 4*f(n-6), 5*f(n-7), 6*f(n-8), 7*f(n-9)}
: 后面 8*f(n-10) 就没有必要了，因为 4*f(n-6)≥8*f(n-10)
: 如果需要打印，也很简单。另外定义一个数组 g(n)，记录每次的比较结果。
: n f(n) g(n)
: 1 1 0
: 2 2 0
: 3 3 0
| f****g
发帖数: 313 | 22 我也试着解一解：
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
我的assumption: 如果没有Ctrl-A, Ctrl-C只能一次拷贝一个字母。
这4个key里最厉害的组合要算是：（2-3-4） 使原有的A的个数一下子翻倍：
m(n) = m(n-3)*2
再来看一下base case:
n = 1, m(1) = 1
n = 2, m(2) = 2
n = 3, m(3) = 3
n = 4, m(4) = max(m(1)*2, 4)= 4
n = 5, m(5) = max(m(2)*2, 5)= 5
n = 6, m(6) = max(m(3)*2, 6)= 6
n = 7, m(7) = max(m(4)*2, 7)=8
所以，当 n < 7 时， m(n) = n; n >= 7时，m(n) = m(n-3)*2
int numOfA[MAX_LEN] = {0};
for(int i = 1; i < 7; i ++ )
{
numOfA[i] = i;
}
for(int i = 7; i <= N; i ++)
{
numOfA[i] = numOf[i-3]*2；
} | g*********s
发帖数: 1782 | 23 没看懂。说说思路吧。
6*f(n-8), 7*f(n-9)}
【在 h**6 的大作中提到】
: 新年早起来做题之二：
: 令 m = f(n)
: if n≤0, f(n) = 0
: if n>0, f(n) = max{f(n-1)+1, 2*f(n-4), 3*f(n-5), 4*f(n-6), 5*f(n-7), 6*f(n-8), 7*f(n-9)}
: 后面 8*f(n-10) 就没有必要了，因为 4*f(n-6)≥8*f(n-10)
: 如果需要打印，也很简单。另外定义一个数组 g(n)，记录每次的比较结果。
: n f(n) g(n)
: 1 1 0
: 2 2 0
: 3 3 0
| f****g
发帖数: 313 | 24 看了一下han6大侠的帖子，知道自己又把问题想简单了
Ctrl+A, Ctrl+C, Ctrl+V后，还可以直接再Ctrl+V, Ctrl+V, Ctrl+V....
n>6: m(n)=max{m(n-3)*2, m(n-4)*3, m(n-5)*4, m(n-6)*5, m(n-7)*6}
m(n-4)*3 >= m(n-4-3)*3*3= m(n-7)*9>m(n-7)*6
S>
So m(n)= max{m(n-3)*2, m(n-4)*3, m(n-5)*4, m(n-6)*5}
int numOfA[MAX_LEN] = {0};
for(int i = 1; i < 7; i ++ )
{
numOfA[i] = i;
}
for(int i = 7; i <= N; i ++)
{
numOfA[i] = max{numOf[i-3]*2, numOf[i-4]*3, numOf[i-5]*4, numOf[i-6]*5}；
}
【在 f****g 的大作中提到】
: 我也试着解一解：
: 1. A
: 2. Ctrl+A
: 3. Ctrl+C
: 4. Ctrl+V
: 我的assumption: 如果没有Ctrl-A, Ctrl-C只能一次拷贝一个字母。
: 这4个key里最厉害的组合要算是：（2-3-4） 使原有的A的个数一下子翻倍：
: m(n) = m(n-3)*2
: 再来看一下base case:
: n = 1, m(1) = 1
| S*********r
发帖数: 5693 | 25 那个解法的确很牛，我也是看了半天，情况太多一会儿就糊涂了。要是面试的时候第一
次碰到估计也就挂了。
我觉得是不是这么推的（operations: a, A, C, V, ACVV可以翻一番，然后再加V继续）
Suppose 当前已经有k个a, f(n0）= k。如果后面还可以有n步：
n=1:3, 就是 ka, kaa, kaaa
n=4, kaaaa or 2k (ACVV)， 后者就是2f(n-4）
n=5, kaaaaa or 2k+k (ACVV V) = 3f(n-5）
n=6, kaaaaaa or 2k+ kk (ACVV VV) = 4f(n-6),
n=7, kaaaaaaa or 2k+ kkk(ACVV VVV) = 5f(n-7)
n=8, kaaaaaaaa
或者有两次 ACVV
一次： 2k+ kkkk = 6k (ACVV VVVV) wins, 6f(n-8)
两次： 2k + 2k = 4k(ACVV ACVV)
n=9, 一次： 2k + kkkkk = 7k (ACVV VVVVV) wins 7f(n-9)
两次： 2k + 2k + 2k = 6k (ACVV, ACVV, V）
n=10 一次： 2k + kkkkkk = 8k (ACVV VVVVVV)
两次： 2k + 2k + 2k2k = 8k (ACVV, ACVV, VV） ties,
可以把前一个ACCV折到f(n-6)=2k, 所以就是 4f(n-6)
n=11 一次： 2k + kkkkkkk = 9k (ACVV VVVVVV)
两次： 2k + 2k + 2k2k2k = 10k (ACVV, ACVV, VV） wins
same as above, no need to go futher.
过，没想到要比到n-9, 后来加上紧张，思路就乱了，结果就挂了。一般的Dynamic
Programming都没有需要比较这么多项，你是怎么想到的，谢谢大虾。
【在 a***o 的大作中提到】
: 大虾，能讲讲你解这个题的思路么？我当时第一感觉是用Dynamic programming. 不过，没想到要比到n-9, 后来加上紧张，思路就乱了，结果就挂了。一般的Dynamic Programming都没有需要比较这么多项，你是怎么想到的，谢谢大虾。
:
: -8), 7*f(n-9)}
| x***y
发帖数: 633 | 26 If we treat the operations of k 1 and followed by 2+3+4 as a group, then after each group of operations, the problem becomes
A*=(A...A) (totally k A in parenthesis)
1. Ctrl+V will type another A*
2. Ctrl+A Ctrl+C Ctrl+V
if we treat A* as the new unit, it will become the original problem again. So, we can use DP to work on it
F(N) = max_{0<=k<=N} { k+k*F(N-k-3)}
with F(0)=F(-1)=F(-2)=F(-3)=0.
please
【在 a***o 的大作中提到】
: Google Interview Question for Software Enginee
: 题目如下：
: 1. A
: 2. Ctrl+A
: 3. Ctrl+C
: 4. Ctrl+V
: 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),
| B********n
发帖数: 384 | 27 应该是对的，不过可以再简化一下。
首先一旦CtrlA,后面必然是CtrlC, CtrlV, CtrlV，不然不是最优解
所以每次这个序列操作完成后，假设拷贝缓冲区是g(n)，那么g(n) <= f(n)/2
在n-5，n-4, n-3, n-2, n-1, n的操作中，必然有CtrlA, CtrlC, CtrlV, CtrlV系列，
因为如果都是CtrlV,那么f(n) = f(n-6) + 6 * g(n-6) <= 4 * f(n-6)，而使用CtrlA,
CtrlC, CtrlV, CtrlV, CtrlV, CtrlV可以达到同样的效果，而且缓冲区更大
所以n-5,n-4,n-3,n-2,n-1, n只有3种可能
1. CtrlA, CtrlC, CtrlV, CtrlV, CtrlV, CtrlV
2. CtrlV, CtrlA, CtrlC, CtrlV, CtrlV, CtrlV
3. CtrlV, CtrlV, CtrlA, CtrlC, CtrlV, CtrlV
再加上缓冲区是空的情况
so f(n) = max{f(n-1)+1, 2*f(n-4), 3*f(n-5), 4*f(n-6)}
-8), 7*f(n-9)}
【在 h**6 的大作中提到】
: 新年早起来做题之二：
: 令 m = f(n)
: if n≤0, f(n) = 0
: if n>0, f(n) = max{f(n-1)+1, 2*f(n-4), 3*f(n-5), 4*f(n-6), 5*f(n-7), 6*f(n-8), 7*f(n-9)}
: 后面 8*f(n-10) 就没有必要了，因为 4*f(n-6)≥8*f(n-10)
: 如果需要打印，也很简单。另外定义一个数组 g(n)，记录每次的比较结果。
: n f(n) g(n)
: 1 1 0
: 2 2 0
: 3 3 0
| j********x
发帖数: 2330 | 28 google的题虽然很欠揍，想想倒还是蛮有意思的。。。 | a***o
发帖数: 24 | 29 Han6大虾的算法是对的。尤其是4*f(n-6)>=8*f(n-10)这步抓的很好，真是这步使这道
题可以用
Dynamic programming去做了。大概的思路如下
n-10, n-9, n-8, n-7, n-6, n-5, n-4, n-3,
n-2, n-1, n,
1. CtrlV, CtrlA, CtrlC, CtrlV, CtrlV, CtrlV, CtrlV, CtrlV,
CtrlV, CtrlV, CtrlV 8*f(n-10)
2. CtrlV, CtrlV, CtrlA, CtrlC, CtrlV, CtrlV, CtrlV, CtrlV,
CtrlV, CtrlV, CtrlV 7*f(n-9)
3. CtrlV, CtrlV, CtrlV, CtrlA, CtrlC, CtrlV, CtrlV, CtrlV,
CtrlV, CtrlV, CtrlV 6*f(n-8)
4. CtrlV, CtrlV, CtrlV, CtrlV, CtrlA, CtrlC, CtrlV, CtrlV,
CtrlV, CtrlV, CtrlV 5*f(n-7)
5. CtrlV, CtrlV, CtrlV, CtrlV, CtrlV, CtrlA, CtrlC, CtrlV,
CtrlV, CtrlV, CtrlV 4*f(n-6)
6. CtrlV, CtrlV, CtrlV, CtrlV, CtrlV, CtrlV, CtrlA, CtrlC,
CtrlV, CtrlV, CtrlV 3*f(n-5)
7. CtrlV, CtrlV, CtrlV, CtrlV, CtrlV, CtrlV, CtrlV, CtrlA,
CtrlC, CtrlV, CtrlV 2*f(n-4)
你说的简化方法，我再仔细看看哦。谢了
列，
CtrlA,
【在 B********n 的大作中提到】
: 应该是对的，不过可以再简化一下。
: 首先一旦CtrlA,后面必然是CtrlC, CtrlV, CtrlV，不然不是最优解
: 所以每次这个序列操作完成后，假设拷贝缓冲区是g(n)，那么g(n) <= f(n)/2
: 在n-5，n-4, n-3, n-2, n-1, n的操作中，必然有CtrlA, CtrlC, CtrlV, CtrlV系列，
: 因为如果都是CtrlV,那么f(n) = f(n-6) + 6 * g(n-6) <= 4 * f(n-6)，而使用CtrlA,
: CtrlC, CtrlV, CtrlV, CtrlV, CtrlV可以达到同样的效果，而且缓冲区更大
: 所以n-5,n-4,n-3,n-2,n-1, n只有3种可能
: 1. CtrlA, CtrlC, CtrlV, CtrlV, CtrlV, CtrlV
: 2. CtrlV, CtrlA, CtrlC, CtrlV, CtrlV, CtrlV
: 3. CtrlV, CtrlV, CtrlA, CtrlC, CtrlV, CtrlV
| C*****n
发帖数: 1872 | 30 那么如何判断9*f(n-11),10*f(n-12),....不需要考虑了？
【在 a***o 的大作中提到】
: Han6大虾的算法是对的。尤其是4*f(n-6)>=8*f(n-10)这步抓的很好，真是这步使这道
: 题可以用
: Dynamic programming去做了。大概的思路如下
: n-10, n-9, n-8, n-7, n-6, n-5, n-4, n-3,
: n-2, n-1, n,
: 1. CtrlV, CtrlA, CtrlC, CtrlV, CtrlV, CtrlV, CtrlV, CtrlV,
: CtrlV, CtrlV, CtrlV 8*f(n-10)
: 2. CtrlV, CtrlV, CtrlA, CtrlC, CtrlV, CtrlV, CtrlV, CtrlV,
: CtrlV, CtrlV, CtrlV 7*f(n-9)
: 3. CtrlV, CtrlV, CtrlV, CtrlA, CtrlC, CtrlV, CtrlV, CtrlV,
| | | a***o
发帖数: 24 | 31 类似的，这是因为多出来的四步，可以用CtrlA，CtrlC，CtrlV, CtrlV去double。所以
有5*f(n-7)>9*f(n-11),6*f(n-8)>10*f(n-12),……
【在 C*****n 的大作中提到】
: 那么如何判断9*f(n-11),10*f(n-12),....不需要考虑了？
| C*****n
发帖数: 1872 | 32 明白了，谢谢
【在 a***o 的大作中提到】
: 类似的，这是因为多出来的四步，可以用CtrlA，CtrlC，CtrlV, CtrlV去double。所以
: 有5*f(n-7)>9*f(n-11),6*f(n-8)>10*f(n-12),……
| a***o
发帖数: 24 | 33 不客气，大家共同学习。
【在 C*****n 的大作中提到】
: 明白了，谢谢
| h**6
发帖数: 4160 | 34 简化版的方法不对，因为在 n-6 的时候，有可能以 CtrlA 或者 CtrlC 结尾。缓冲区g
(n) <= f(n)/2这个式子有问题。
反例出现在计算 f(12) 和 f(13) 时。
CtrlA,
【在 B********n 的大作中提到】
: 应该是对的，不过可以再简化一下。
: 首先一旦CtrlA,后面必然是CtrlC, CtrlV, CtrlV，不然不是最优解
: 所以每次这个序列操作完成后，假设拷贝缓冲区是g(n)，那么g(n) <= f(n)/2
: 在n-5，n-4, n-3, n-2, n-1, n的操作中，必然有CtrlA, CtrlC, CtrlV, CtrlV系列，
: 因为如果都是CtrlV,那么f(n) = f(n-6) + 6 * g(n-6) <= 4 * f(n-6)，而使用CtrlA,
: CtrlC, CtrlV, CtrlV, CtrlV, CtrlV可以达到同样的效果，而且缓冲区更大
: 所以n-5,n-4,n-3,n-2,n-1, n只有3种可能
: 1. CtrlA, CtrlC, CtrlV, CtrlV, CtrlV, CtrlV
: 2. CtrlV, CtrlA, CtrlC, CtrlV, CtrlV, CtrlV
: 3. CtrlV, CtrlV, CtrlA, CtrlC, CtrlV, CtrlV
| b***e
发帖数: 1419 | 35 I don't think this will need DP eventually, coz it's too slow. Given n,
you need O(n) to compute f(n).
We know the 6-pattern
4 * f(n-6)
is giving the highest exponential rate. As a result, if the input n is
big, in the beginning we will always apply this pattern, until some
certain
point n0. So the end of the day, the time would be O(log(n)).
The next question is to give an upper bound of n0. One naive upper
bound
would be:
n0 = (4 + 5 + 7 + 8 + 9) * 5 = 165
This is the max you can go without applying a 6-pattern. For any n >=
165,
we can replace 6 k-patterns with k 6-pattern.
区g
【在 h**6 的大作中提到】
: 简化版的方法不对，因为在 n-6 的时候，有可能以 CtrlA 或者 CtrlC 结尾。缓冲区g
: (n) <= f(n)/2这个式子有问题。
: 反例出现在计算 f(12) 和 f(13) 时。
:
: CtrlA,
| h*********3
发帖数: 111 | 36 应该是 2*f(n-3) 吧,而且应该加上 f(n-2)+2
还有，n=7时候，最大应该是9吧: AAA2344
-8), 7*f(n-9)}
【在 h**6 的大作中提到】
: 新年早起来做题之二：
: 令 m = f(n)
: if n≤0, f(n) = 0
: if n>0, f(n) = max{f(n-1)+1, 2*f(n-4), 3*f(n-5), 4*f(n-6), 5*f(n-7), 6*f(n-8), 7*f(n-9)}
: 后面 8*f(n-10) 就没有必要了，因为 4*f(n-6)≥8*f(n-10)
: 如果需要打印，也很简单。另外定义一个数组 g(n)，记录每次的比较结果。
: n f(n) g(n)
: 1 1 0
: 2 2 0
: 3 3 0
| w*****p
发帖数: 215 | 37 应该是greedy。
上面错了，应该是这样的
n f(n) g(n)
1 1 0
2 2 0
3 3 0
4 4 0
5 5 0
6 6 0
7 8 4
8 10 5
9 12 6
10 16 7
11 20 8
12 24 9
13 30 10
14 40 11
15 48 12
16 64 13
n>6, f(n)=2f(n-3). 这个具有greedy 的结构。数学可以证明。
首先证明 f(n)>=f(n-1)+1, 很简单，不写了。
然后 f(n)=max(f(n-1)+1, f(n-2)+2,, 2*f(n-4)+1, ....) 但是 2f(n-3)>= 2f(n-4)+
1, 所以 f(n)=max(f(n-1)+1, f(n-2)+2,f(n-3)*2)。
最后，归纳证明 f(n)=2f(n-3).
Trace back 就是一堆 Ctrl+A, Ctrl+C, Ctrl+V, 直到 n-3<=6,剩下的输出A。
Done | w*****p
发帖数: 215 | 38 SORRY
f(13)=32, the rest is correct. | c***n
发帖数: 809 | 39 ACV 啥也不是, 至少也要ACVV才能增加个数.
【在 w*****p 的大作中提到】
: 应该是greedy。
: 上面错了，应该是这样的
: n f(n) g(n)
: 1 1 0
: 2 2 0
: 3 3 0
: 4 4 0
: 5 5 0
: 6 6 0
: 7 8 4
| c***n
发帖数: 809 | 40 AAA2344 就是6, 234只会overwrite已经存在的AAA.
【在 h*********3 的大作中提到】
: 应该是 2*f(n-3) 吧,而且应该加上 f(n-2)+2
: 还有，n=7时候，最大应该是9吧: AAA2344
:
:
: -8), 7*f(n-9)}
| | | w*****p
发帖数: 215 | 41 sorry, my bad. 少考虑了三种情况。
when n>6, f(n)=max(2f(n-3),3f(n-4),4f(n-5),5f(n-6)). 就是这四种情况。分别表
示一次 Ctrl+A, Ctrl+C, Ctrl+V;
Ctrl+A, Ctrl+C, Ctrl+V,Ctrl+V;
Ctrl+A, Ctrl+C, Ctrl+V,Ctrl+V,Ctrl+V;
Ctrl+A, Ctrl+C, Ctrl+V,Ctrl+V,Ctrl+V,Ctrl+V;
其他情况可以写成 (k-1)f(n-k), k>6, 以及 f(n+1)+1,f(n+2)+2
其他情况都比2f(n-3),3f(n-4),4f(n-5),5f(n-6))小。 比如 3f(n-4)>=2*3f(n-7)=6f
(n-7),due to the recursive structure.
所以，optimal structure 就是 f(n)=max(2f(n-3),3f(n-4),4f(n-5),5f(n-6)).
希望这次俺没犯错误。 | b***e
发帖数: 1419 | 42 Greedy是对的, 不需要从头到尾的DP。不过要从4*f(n-6)这个pattern出发。最后的常
数情况要DP
求一下。前面我给出了一个常数情况的上界。
【在 w*****p 的大作中提到】
: 应该是greedy。
: 上面错了，应该是这样的
: n f(n) g(n)
: 1 1 0
: 2 2 0
: 3 3 0
: 4 4 0
: 5 5 0
: 6 6 0
: 7 8 4
| B********n
发帖数: 384 | 43 You are right, thanks.
区g
【在 h**6 的大作中提到】
: 简化版的方法不对，因为在 n-6 的时候，有可能以 CtrlA 或者 CtrlC 结尾。缓冲区g
: (n) <= f(n)/2这个式子有问题。
: 反例出现在计算 f(12) 和 f(13) 时。
:
: CtrlA,
| h**6
发帖数: 4160 | 44 我把 blaze 大虾的方法翻译一下，贴在这里。
我们把以 ACV... 开头到下一次出现 A 之前称为1节。
为什么以每节6击键(ACVVVV)为单位循环的效率最高？而不是每节5击键(ACVVV)或者每节7击键(ACVVVVV)。
假设前面已有 x 个 A，此后还能敲键盘 n 次，这里 n 特别大，以致可以忽略余数。
那么假设每节长度为 k，最终能得到 x(k-2)^(n/k) 个 A。
令 h(k) 表示平均每次击键 A 的数目的增加倍数，则
h(k) = (k-2)^(1/k)
h'(k) = h(k)*[(-1/k^2)log(k-2)+1/(k*(k-2))]，当 k=6.31914 时 h'(k)=0 函数 h(k) 有最大值。
但 k 只能取整数，因此
h(3) = 1
h(4) = 1.1892
h(5) = 1.2457
h(6) = 1.2599
h(7) = 1.2585
h(8) = 1.2510
最大值在h(6)处。
对于 n 非常大的情况下，可以使用ACVVVV的结构，在中间添加6节一段的循环。
现在接着考虑，n 究竟为多大才可以称为“非常大”？我们注意到，当每节长度 k=10 时可以拆为 k=4 和 k=6 两节，产生的字符长度相等但缓冲区更大。当 k>10 时也可以拆分成较短的小节而取代。因此，可以断言长度 k≥10 的小节不存在。同样 k≤3 的小节也不存在。
本题转为背包问题：
有重量为w1, w2, ..., wn的若干包裹，其价值为v1, v2, ..., vn。现在不限个数的取以上包裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
已知包裹 i 的单位重量价值最高，是否存在一个 W，对于所有 M≥W，f(M+wi) = f(M)+vi
对于每个包裹 j(j≠i)，其所取个数均小于 wi 个，否则可以把 wi 个包裹 j 换成 wj 个包裹 i，总重量不变，总价值增加。
因此 W = [sum(w)-wi]*(wi-1)
回到原题，这个“非常大”的 n 可以求出为 (4+5+7+8+9)*(6-1) = 165
加上最前面一些手工输入的 A，可以认为当 n≥172 时，f(n+6) = 4f(n) | w*****p
发帖数: 215 | 45 f(n+6) = 4f(n) 是不可能的。
n+6 就是 ACVVVV 和 ACVACV 选择。 对于前者结果是 5f(n),对于后者就是 4f(n), 根
据最优 f(n+6) 有可能是 5f(n)， 绝不可能是4f(n)。
欢迎指教。 | b***e
发帖数: 1419 | 46 丁页！
如果我是interviewer的话，我会最终像要一个这样的答案或思路，而不仅仅是naive
DP. 因为
当n很大的时候，naive DP是做不出来的。就像是计算fib(n)，最终的理想是O(log(n))
的算
法。
Some more clarifications to help understanding:
1. It's easy to see for any k >= 10, (k-2) * f(n-k) pattern is not
needed because, (k/2 - 2)^2 > k - 2. So instead of the k-pattern, you
can always apply 2 consecutive (k/2)-patterns.
2. Note that all the steps are commutable. If you have a 4-pattern and
9-pattern, it doesn't matter which one you apply first. That's why if
you have 6-patterns, you can always apply them all at the beginning.
3. Why is 6-pattern the best? The effectiveness of a k-pattern can be
computed by (k-2)^(1/k). This function gets its maximum (for integer k)
when k = 6.
3. The upper bound of the converging point at which 6-pattern must
occurs can be lowered:
First 4-pattern and 8-pattern are conflicting coz you can replace them
with two 6-patterns. Same story for 5-pattern and 7-pattern.
Second, you can have only two 8-patterns because three 8-patterns can
replaced by four 6-paterns. For similar reasons, you can only have one
9-pattern at most.
So n0 could be:
7 * 5 + 2 * 8 + 9 = 35 + 16 + 9 = 60
This will make your program smaller (in the constant array that you are
hosting).
每节7击键
(ACVVVVV)。
数 h(k) 有最大值。
【在 h**6 的大作中提到】
: 我把 blaze 大虾的方法翻译一下，贴在这里。
: 我们把以 ACV... 开头到下一次出现 A 之前称为1节。
: 为什么以每节6击键(ACVVVV)为单位循环的效率最高？而不是每节5击键(ACVVV)或者每节7击键(ACVVVVV)。
: 假设前面已有 x 个 A，此后还能敲键盘 n 次，这里 n 特别大，以致可以忽略余数。
: 那么假设每节长度为 k，最终能得到 x(k-2)^(n/k) 个 A。
: 令 h(k) 表示平均每次击键 A 的数目的增加倍数，则
: h(k) = (k-2)^(1/k)
: h'(k) = h(k)*[(-1/k^2)log(k-2)+1/(k*(k-2))]，当 k=6.31914 时 h'(k)=0 函数 h(k) 有最大值。
: 但 k 只能取整数，因此
: h(3) = 1
| b***e
发帖数: 1419 | 47 你给我翻译一下，什么叫惊喜？
每节7击键
(ACVVVVV)。
h(k) 有最大值。
【在 h**6 的大作中提到】
: 我把 blaze 大虾的方法翻译一下，贴在这里。
: 我们把以 ACV... 开头到下一次出现 A 之前称为1节。
: 为什么以每节6击键(ACVVVV)为单位循环的效率最高？而不是每节5击键(ACVVV)或者每节7击键(ACVVVVV)。
: 假设前面已有 x 个 A，此后还能敲键盘 n 次，这里 n 特别大，以致可以忽略余数。
: 那么假设每节长度为 k，最终能得到 x(k-2)^(n/k) 个 A。
: 令 h(k) 表示平均每次击键 A 的数目的增加倍数，则
: h(k) = (k-2)^(1/k)
: h'(k) = h(k)*[(-1/k^2)log(k-2)+1/(k*(k-2))]，当 k=6.31914 时 h'(k)=0 函数 h(k) 有最大值。
: 但 k 只能取整数，因此
: h(3) = 1
| h**6
发帖数: 4160 | 48 请看楼主在四楼的解释：
大虾呀，你这样做是不对的呀。
因为，Ctrl+A, Ctrl+C, Ctrl+V 不能直接double前面A的个数呀，也就是说，Ctrl+A,
Ctrl+C, Ctrl+V，Ctrl+V才可以double前面A的个数.
【在 w*****p 的大作中提到】
: f(n+6) = 4f(n) 是不可能的。
: n+6 就是 ACVVVV 和 ACVACV 选择。 对于前者结果是 5f(n),对于后者就是 4f(n), 根
: 据最优 f(n+6) 有可能是 5f(n)， 绝不可能是4f(n)。
: 欢迎指教。
| h**6
发帖数: 4160 | 49 关于背包问题，我再补充一点：
有重量为w1, w2, ..., wn的若干包裹，其价值为v1, v2, ..., vn。现在不限个数的取以上包裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
已知包裹 i 的单位重量价值最高，是否存在一个 W，对于所有 M≥W，f(M+wi) = f(M)+vi
前面已经求出 W = [sum(w)-wi]*(wi-1)，对于 M>W 的情况，可以先使用 DP，后用包裹 i 作补充，凑出总重量 M，并求出总价值。
但是当 sum(w) 非常大的时候，W 可能超出计算范围。使用复杂度为 O(W) 的 DP 算法求出 1~W 之间的所有解也不现实。这时候注意观察，我们需要的只是 1~W 之间与 M 关于 wi 的模相等的解，
x ≡ M (MOD wi)
只有这些 x 才能构造出总重量为 M 的情况。其余值的解与所求问题无关。
求出所有的 x 处的解，及相对应 M 处的总价值，然后取其最大者就可以了。
当然，条件是 M>W，否则仍然只能老老实实用 DP 求出答案。 | g*********s
发帖数: 1782 | 50 这个讨论不错。版主一定要合集啊。
不过周瑜你最后的解法到底在几楼？
取以上包
裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
M)+vi
包裹 i
作补充，凑出总重量 M，并求出总价值。
有解也不现
实。这时候注意观察，我们需要的只是 1~W 之间与 M 关于 wi 的模相等的解，
【在 h**6 的大作中提到】
: 关于背包问题，我再补充一点：
: 有重量为w1, w2, ..., wn的若干包裹，其价值为v1, v2, ..., vn。现在不限个数的取以上包裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
: 已知包裹 i 的单位重量价值最高，是否存在一个 W，对于所有 M≥W，f(M+wi) = f(M)+vi
: 前面已经求出 W = [sum(w)-wi]*(wi-1)，对于 M>W 的情况，可以先使用 DP，后用包裹 i 作补充，凑出总重量 M，并求出总价值。
: 但是当 sum(w) 非常大的时候，W 可能超出计算范围。使用复杂度为 O(W) 的 DP 算法求出 1~W 之间的所有解也不现实。这时候注意观察，我们需要的只是 1~W 之间与 M 关于 wi 的模相等的解，
: x ≡ M (MOD wi)
: 只有这些 x 才能构造出总重量为 M 的情况。其余值的解与所求问题无关。
: 求出所有的 x 处的解，及相对应 M 处的总价值，然后取其最大者就可以了。
: 当然，条件是 M>W，否则仍然只能老老实实用 DP 求出答案。
| | | b***e
发帖数: 1419 | 51 Overall speaking, the complexity will be still linear. The DP part only
takes O(1).
取以上包
裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
M)+vi
包裹 i
作补充，凑出总重量 M，并求出总价值。
有解也不现
实。这时候注意观察，我们需要的只是 1~W 之间与 M 关于 wi 的模相等的解，
【在 h**6 的大作中提到】
: 关于背包问题，我再补充一点：
: 有重量为w1, w2, ..., wn的若干包裹，其价值为v1, v2, ..., vn。现在不限个数的取以上包裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
: 已知包裹 i 的单位重量价值最高，是否存在一个 W，对于所有 M≥W，f(M+wi) = f(M)+vi
: 前面已经求出 W = [sum(w)-wi]*(wi-1)，对于 M>W 的情况，可以先使用 DP，后用包裹 i 作补充，凑出总重量 M，并求出总价值。
: 但是当 sum(w) 非常大的时候，W 可能超出计算范围。使用复杂度为 O(W) 的 DP 算法求出 1~W 之间的所有解也不现实。这时候注意观察，我们需要的只是 1~W 之间与 M 关于 wi 的模相等的解，
: x ≡ M (MOD wi)
: 只有这些 x 才能构造出总重量为 M 的情况。其余值的解与所求问题无关。
: 求出所有的 x 处的解，及相对应 M 处的总价值，然后取其最大者就可以了。
: 当然，条件是 M>W，否则仍然只能老老实实用 DP 求出答案。
| j****a
发帖数: 12 | 52 //不才献丑了
sum[0]=0,buf[0]=0,i=0;
P1(i){
i++;
buf[i]=buf[i-1];
sum[i]=sum[i-1]+1;
return sum[i];
}
p234(i){
i+=3;
buf[i]=sum[i-3];
sum[i]=sum[i-3];
return sum[i];
}
p4(i){
i+=1;
buf[i]=buf[i-1];
sum[i]=sum[i-1]+buf[i-1];
return sum[i];
}
sum[i]=max{p1(i-1),p234(i-3),p4(i-1)};
M=sum[n];
//有不好之处，请不吝赐教 | j****a
发帖数: 12 | 53 //不才献丑了
sum[0]=0,buf[0]=0,i=0;
P1(i){
i++;
buf[i]=buf[i-1];
sum[i]=sum[i-1]+1;
return sum[i];
}
p234(i){
i+=3;
buf[i]=sum[i-3];
sum[i]=sum[i-3];
return sum[i];
}
p4(i){
i+=1;
buf[i]=buf[i-1];
sum[i]=sum[i-1]+buf[i-1];
return sum[i];
}
sum[i]=max{p1(i-1),p234(i-3),p4(i-1)};
M=sum[n];
//有不好之处，请不吝赐教 | i**********e
发帖数: 1145 | 54 我也尝试解一解这题，不知道是不是跟各位大侠的解法一样，欢迎讨论。
假设定义：
4A 为 连敲 4 次 A，
2D 为 CTRL+A, CTRL+C, CTRL+V, CTRL+V,将之前的 A X 2，
3D 为 CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V,将之前的 A X 3.
f(N) 为最优解.
n <= 7, 那么 f(n) = n.
n = 8, f(n) = 3A3D = 9.
n = 9, f(n) = 3A4D = 12.
n = 10, f(n) = 4A4D = 16.
n = 11, f(n) = 4A5D = 20.
n = 12, f(n) = 5A5D = 25.
n = 13, f(n) = 5A6D = 30.
n = 14, f(n) = 6A6D = 36.
思路很明显，就是要求 a*b = n-2, 并且 a 和 b 相乘为最大值。
注意了，
n = 15, f(n) = 6A7D = 42？
这是错的，因为当 n = 15,
f(n) = 3A4D4D = 48.
n = 16, f(n) = 4A4D4D = 64.
以此类推，
n = 21, f(n) = 3A4D4D4D = 192.
...
n = 25, f(n) = 4A5D5D5D = 500.
n = 26, f(n) = 5A5D5D5D = 625.
n = 27, f(n) = 3A4D4D4D4D = 768.
将此扩展，不难发现：
f(n) = MAX (a1 * a2 * ... * ak),
where SUM (a1, a2, ... ak) = n - 2*(k-1)
要得到 MAX (al * a2 * ... * ak),
必定条件就是 MAX (diff( ai - aj ) ) = 1, where i, j belong to {1,2,...,k}.
可以先得到 SUM 的平均值，之后就很直接了。
至于有什么方法能找到这个 k 的值，我现在除了 brute force 之外还没想到更好的解
法。欢迎各位大侠讨论讨论。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | i**********e
发帖数: 1145 | 55 谢谢你的总结。
可是我不明白，为什么以每节6击键(ACVVVV = 4D)为单位循环的效率最高？
给个例子，
当 n = 26,
f(n) = 5A5D5D5D (AAAAA ACVVVVV ACVVVVV ACVVVVV) = 625.
里面并没有 ACVVVV (4D) 的连接呀？
可能我理解错了？如果我的答案是错的，请指教。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
每节7击键(ACVVVVV)。
h(k) 有最大值。
【在 h**6 的大作中提到】
: 我把 blaze 大虾的方法翻译一下，贴在这里。
: 我们把以 ACV... 开头到下一次出现 A 之前称为1节。
: 为什么以每节6击键(ACVVVV)为单位循环的效率最高？而不是每节5击键(ACVVV)或者每节7击键(ACVVVVV)。
: 假设前面已有 x 个 A，此后还能敲键盘 n 次，这里 n 特别大，以致可以忽略余数。
: 那么假设每节长度为 k，最终能得到 x(k-2)^(n/k) 个 A。
: 令 h(k) 表示平均每次击键 A 的数目的增加倍数，则
: h(k) = (k-2)^(1/k)
: h'(k) = h(k)*[(-1/k^2)log(k-2)+1/(k*(k-2))]，当 k=6.31914 时 h'(k)=0 函数 h(k) 有最大值。
: 但 k 只能取整数，因此
: h(3) = 1
| g*****k
发帖数: 623 | 56 不太明白你的a 和 b 都指代 什么
【在 i**********e 的大作中提到】
: 我也尝试解一解这题，不知道是不是跟各位大侠的解法一样，欢迎讨论。
: 假设定义：
: 4A 为 连敲 4 次 A，
: 2D 为 CTRL+A, CTRL+C, CTRL+V, CTRL+V,将之前的 A X 2，
: 3D 为 CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V,将之前的 A X 3.
: f(N) 为最优解.
: n <= 7, 那么 f(n) = n.
: n = 8, f(n) = 3A3D = 9.
: n = 9, f(n) = 3A4D = 12.
: n = 10, f(n) = 4A4D = 16.
| i**********e
发帖数: 1145 | 57 n = 13, f(n) = 5A6D = 30. ( a = 5, b = 6, f(n) = a*b = 5*6 = 30 )
n = 14, f(n) = 6A6D = 36. ( a = 6, b = 6, f(n) = a*b = 6*6 = 36 )
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g*****k 的大作中提到】
: 不太明白你的a 和 b 都指代 什么
| h***n
发帖数: 276 | 58 My solution is based on backtracking
Given:
- n: # of types (can be viewed as some credits)
- b: # of A in the buffer
- m: # of A is shown
Three types of (simple and complex) actions
A: m = m + 1, n = n - 1 (only valid when b=0, already analyzed above why it
is only shown at the beginning of type sequence)
Crtl+A, Crtl+C, Crtl+V, Crtl+V: b = m, m = 2*m, n = n - 4
Crtl+V: m = m + b, n = n - 1
Source codes are as follows:
void get_max_A(int n, int b, int m, int *max)
{
if (n == 0) {
if (*max < m)
*max = m;
return;
}
if (b == 0) {
get_max_A(n - 1, b, m + 1, max);
} else {
get_max_A(n - 1, b, m + b, max);
}
if (n - 4 >= 0) {
get_max_A(n - 4, m, 2*m, max);
}
}
initial call is
get_max_A(n, 0, 0, &max);
Sample output:
max A for 1 types is 1
max A for 2 types is 2
max A for 3 types is 3
max A for 4 types is 4
max A for 5 types is 5
max A for 6 types is 6
max A for 7 types is 7
max A for 8 types is 9
max A for 9 types is 12
max A for 10 types is 16
max A for 11 types is 20
max A for 12 types is 25
max A for 13 types is 30
max A for 14 types is 36
max A for 15 types is 48
max A for 16 types is 64
max A for 17 types is 80
max A for 18 types is 100
max A for 19 types is 125
max A for 20 types is 150
max A for 21 types is 192
max A for 22 types is 256
max A for 23 types is 320
max A for 24 types is 400
...
By the way, does DP work for this problem? I somehow feel the principle of o
ptimality could not hold. Anyone to clarify? Thanks!
please
【在 a***o 的大作中提到】
: Google Interview Question for Software Enginee
: 题目如下：
: 1. A
: 2. Ctrl+A
: 3. Ctrl+C
: 4. Ctrl+V
: 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),
| x******3
发帖数: 245 | 59 哪位大虾说下为啥234不能翻倍， 2344才能翻
234不是已经把前面的A都全选了copy paste吗， 那样已经多了一倍啊 | x******3
发帖数: 245 | 60 I used a DP method and get the same result with your sample outputs.
My approach is to assume the last Ctrl-C is at position j,
then everything after the last Ctrl-C should be Ctrl-V.
I also think the operation right before Ctrl-C should be Ctrl-A.
So j can be varied to pick the maximum.
python code here, it prints out the solution key sequence
#!/usr/bin/env python
import sys
from collections import deque
num_keys_pressed = int(sys.argv[1])
print "number of keys pressed = %d\n" % num_keys_pressed
f = []
trace_map = {}
f.append(0)
trace_map[0] = -1
f.append(1)
trace_map[1] = -1
f.append(2)
trace_map[2] = -1
f.append(3)
trace_map[3] = -1
print "initial f"
print f
print "initial trace_map"
print trace_map
for i in range(4, num_keys_pressed+1):
#print i
current_max = i
trace_map[i] = -1
for j in range(2, i+1):
current_f = f[j-2]*(i-j)
if current_f > current_max:
current_max = current_f
trace_map[i] = j
f.append(current_max)
key_seq = deque([])
i = num_keys_pressed
while i > 0 :
if trace_map[i] == -1:
while i > 0:
key_seq.appendleft("A")
i = i-1
else:
j = trace_map[i]
while i > j:
key_seq.appendleft("Ctrl-V")
i = i-1
key_seq.appendleft("Ctrl-C")
key_seq.appendleft("Ctrl-A")
i = i-2
print
print "result f"
print f
print "result trace_map"
print trace_map
print
print "key sequence"
print key_seq
it
【在 h***n 的大作中提到】
: My solution is based on backtracking
: Given:
: - n: # of types (can be viewed as some credits)
: - b: # of A in the buffer
: - m: # of A is shown
: Three types of (simple and complex) actions
: A: m = m + 1, n = n - 1 (only valid when b=0, already analyzed above why it
: is only shown at the beginning of type sequence)
: Crtl+A, Crtl+C, Crtl+V, Crtl+V: b = m, m = 2*m, n = n - 4
: Crtl+V: m = m + b, n = n - 1
| | | s*****i
发帖数: 24 | 61 我觉得可以转换下思路看这个题：
A cost 1 len += 1;
(CA, CC) => M cost 2 temp = len;
CV cost 1 len = len + temp;
len初值是0，题目中N为总的cost，M是最后len的值。
动态规划貌似可用
至于到底是CV是复制还是(CV, CV)复制，要问考官。 | c***n
发帖数: 809 | 62 能解释一下为什么.
"要得到 MAX (al * a2 * ... * ak),
必定条件就是 MAX (diff( ai - aj ) ) = 1, where i, j belong to {1,2,...,k}."
【在 i**********e 的大作中提到】
: 我也尝试解一解这题，不知道是不是跟各位大侠的解法一样，欢迎讨论。
: 假设定义：
: 4A 为 连敲 4 次 A，
: 2D 为 CTRL+A, CTRL+C, CTRL+V, CTRL+V,将之前的 A X 2，
: 3D 为 CTRL+A, CTRL+C, CTRL+V, CTRL+V, CTRL+V,将之前的 A X 3.
: f(N) 为最优解.
: n <= 7, 那么 f(n) = n.
: n = 8, f(n) = 3A3D = 9.
: n = 9, f(n) = 3A4D = 12.
: n = 10, f(n) = 4A4D = 16.
| i**********e
发帖数: 1145 | 63 假定四个数相乘，
M = a*b*c*d
你要使得 M 的值为最大，
那么 a,b,c,d 之间的差别必定不能超于 1.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 c***n 的大作中提到】
: 能解释一下为什么.
: "要得到 MAX (al * a2 * ... * ak),
: 必定条件就是 MAX (diff( ai - aj ) ) = 1, where i, j belong to {1,2,...,k}."
| c***n
发帖数: 809 | 64 靠，我居然还能记的起n年前的公式。
根据fermat's theorem, partial derivative 必须为0在最大值.
f = x*y*z*(n-x-y-z)
于是得三个partial derivative 方程，
yz(n-1-y-z) = 0
xz(n-x-1-z)=0
xy(n-x-y-1)=0
解这三个方程应该的到x=y=z=n/4.
【在 i**********e 的大作中提到】
: 假定四个数相乘，
: M = a*b*c*d
: 你要使得 M 的值为最大，
: 那么 a,b,c,d 之间的差别必定不能超于 1.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| i**********e
发帖数: 1145 | 65 这不一定。
if n = 19,
x=y=z= 19/4 = 4
4*4*4*7 = 448
But the max should be
4*5*5*5 = 500
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 c***n 的大作中提到】
: 靠，我居然还能记的起n年前的公式。
: 根据fermat's theorem, partial derivative 必须为0在最大值.
: f = x*y*z*(n-x-y-z)
: 于是得三个partial derivative 方程，
: yz(n-1-y-z) = 0
: xz(n-x-1-z)=0
: xy(n-x-y-1)=0
: 解这三个方程应该的到x=y=z=n/4.
| b***e
发帖数: 1419 | 66 这个好，不过知音难找。 请问是否原创？
取以上包
裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
M)+vi
包裹 i
作补充，凑出总重量 M，并求出总价值。
法求出
1~W 之间的所有解也不现实。这时候注意观察，我们需要的只是 1~W 之间与 M 关于
wi 的模相等的
解，
【在 h**6 的大作中提到】
: 关于背包问题，我再补充一点：
: 有重量为w1, w2, ..., wn的若干包裹，其价值为v1, v2, ..., vn。现在不限个数的取以上包裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
: 已知包裹 i 的单位重量价值最高，是否存在一个 W，对于所有 M≥W，f(M+wi) = f(M)+vi
: 前面已经求出 W = [sum(w)-wi]*(wi-1)，对于 M>W 的情况，可以先使用 DP，后用包裹 i 作补充，凑出总重量 M，并求出总价值。
: 但是当 sum(w) 非常大的时候，W 可能超出计算范围。使用复杂度为 O(W) 的 DP 算法求出 1~W 之间的所有解也不现实。这时候注意观察，我们需要的只是 1~W 之间与 M 关于 wi 的模相等的解，
: x ≡ M (MOD wi)
: 只有这些 x 才能构造出总重量为 M 的情况。其余值的解与所求问题无关。
: 求出所有的 x 处的解，及相对应 M 处的总价值，然后取其最大者就可以了。
: 当然，条件是 M>W，否则仍然只能老老实实用 DP 求出答案。
| b*****e
发帖数: 474 | 67 A programmer probably will use a DP solution, but it really just
needs grade school math:
Let X*n mean X key appears n times in a row.
The form of the answer must be:
A*k + (CA+CC+CV*x_1) + (CA+CC+CV*x_2) + ... (CA+CC+CV*x_m)
while the total # of keys should be n. The order of (CA+CC+CV*x)
combos doesn't matter.
Note the following:
1) First notice that CV should not occur more than 5 times in a row:
CA+CC+CV*n < CA+CC+CV*(n-3)+CA+CC+CV
2) Second, since
CA+CC+CV*5 = CA+CC+CV+CA+CC+CV*2, which means that if CV appears 5 times
in a row, it can be replaced by CA+CC+CV+CA+CC+CV*2.
So now we only need to consider these combos:
K3: CA+CC+CV --> 2x combo
K4: CA+CC+CV+CV --> 3x
K5: CA+CC+CV+CV+CV --> 4x
K6: CA+CC+CV+CV+CV+CV --> 5x
3) At most 1 K3: since 2 K3 is 4x, while K6 is 5x
4) No K3 & K6 together: K3 + K6 is 10x, while K4+K5 is 12x
5) No K3 & K5 together: K3 + K5 is 8k, K4+K4 is 9x
6) No K3 & 2 K4 together: K5 + K6 is 20x
7) At most 4 K4: 5 K4 is 243x, 4 K5 is 256x
8) No K4 & K6 together: K4 + K6 is 15x, K5+K5 is 16x
9) At most 1 K6: 2 K6 is 25x, while 3 K4 is 27x
10) No K6 & 2 K5: 4 K4 is better
Thus, since the number of K3, K4, K6 are limited, most of the combos
should be K5. Thus, given a large enough M keys, if (M modulo 5) =
0: all K5
1: 4 K4 + rest K5 s
2: 3 K4 + rest K5 s
3: 2 K4 + rest K5 s
4: 1 K4 + rest K5 s
Special cases: M=11: K5+K6, M=8: K4+K4, M=7: K3+K4
11) How many A's in the beginning? Only choice is 2, 3, 4, 5, 6,
Since n < (n-3)*2 when n>6 (i.e. A*n is worse than A*(n-3)+ K3)
6 is same as 3: A*6 = A*3 + K3.
So only need to consider 2,3,4,5.
Consider all 4 possible M values: N-2, N-3, N-4, N-5, find the
largest product. For example, Let N = 100:
M=95: A*5 + K5*19 => 5* 4^19
M=96: A*4 + K4*4 + K5*16 => 4* 3^4 * 4^16 A's
M=97: A*3 + K4*3 + K5*17 => 3* 3^3 * 4^17 A's
M=98: A*2 + K4*2 + K5*18 => 2* 3^2 * 4^18 A's
Obviously M=96 or 97 is the max (a tie), i.e. the answer is
either A*4 + K4*4 + K5*16 or A*3 K4*3 + K5*17, with
81*4^17 A's.
please
【在 a***o 的大作中提到】
: Google Interview Question for Software Enginee
: 题目如下：
: 1. A
: 2. Ctrl+A
: 3. Ctrl+C
: 4. Ctrl+V
: 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),
| h**6
发帖数: 4160 | 68
别处看来的算法，稍加修改。
关于背包问题的另一思考：
有重量为w1, w2, ..., wn的若干包裹，其价值为v1, v2, ..., vn。现在不限个数的取以上包裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
已知包裹 i 的单位重量价值最高，是否存在一个 W，对于所有 M>W，f(M) = f(M-wi)+vi
这里的 W，也就是贪婪算法起点的上限。前面求出 W = [sum(w)-wi]*(wi-1)
具体到这题，也就是 W = (4+5+7+8+9)*(6-1) = 165
blaze 给出一个更小的 W 值，但用到了这些数字的特殊性，不能成为通解。我思考了一下，可以给出更小的 W 的通解形式：
不失一般性，设 w1
除了包裹 i 之外所有包裹总数不得大于等于 wi
设选取的包裹为 p1, p2, ... pk
另 S1=w[p1], S2=w[p1]+w[p2], ..., Sk=w[p1]+w[p2]+...+w[pk]
如果 k≥wi，根据鸽巢原理，则S1, S2, ..., Sk必有一项被wi整除，或者两项除以wi余数相等。
如果S1, S2, ..., Sk中有一项被 wi 整除，可以把该项转为若干 wi 之和
如果S1, S2, ..., Sk中有两项除以 wi 余数相等，可以把这两项的差转为若干 wi 之和
因此，除了包裹 i 之外所有包裹总数应严格小于 wi
W = wn*(wi-1)
具体到这题，W = 9*(6-1) = 45
【在 b***e 的大作中提到】
: 这个好，不过知音难找。 请问是否原创？
:
: 取以上包
: 裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
: M)+vi
: 包裹 i
: 作补充，凑出总重量 M，并求出总价值。
: 法求出
: 1~W 之间的所有解也不现实。这时候注意观察，我们需要的只是 1~W 之间与 M 关于
: wi 的模相等的
| b*****e
发帖数: 474 | 69 Ah, some one pointed out that CA+CC+CV does not duplicate;
CA+CC+CV*2 duplicates; thus CA+CC+CV*n is n times, not n+1 times.
This will cause some changes to the answer, but the O(1) solution
remains.
This problems remains me of a similar problem:
任何一个整数 N, 把它拆分成几个整数之和。 问怎样拆分后，所有数的积最大？
【在 b*****e 的大作中提到】
: A programmer probably will use a DP solution, but it really just
: needs grade school math:
: Let X*n mean X key appears n times in a row.
: The form of the answer must be:
: A*k + (CA+CC+CV*x_1) + (CA+CC+CV*x_2) + ... (CA+CC+CV*x_m)
: while the total # of keys should be n. The order of (CA+CC+CV*x)
: combos doesn't matter.
: Note the following:
: 1) First notice that CV should not occur more than 5 times in a row:
: CA+CC+CV*n < CA+CC+CV*(n-3)+CA+CC+CV
| c***n
发帖数: 809 | 70 n/4 = 19/4 = 4.75, 所以究竟是4还是5, 要看具体情况.
【在 i**********e 的大作中提到】
: 这不一定。
: if n = 19,
: x=y=z= 19/4 = 4
: 4*4*4*7 = 448
: But the max should be
: 4*5*5*5 = 500
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| | | b***e
发帖数: 1419 | 71 这个也行，more rigid upper bound. 不过没必要。 前面那招直接上确界就求出来了
(每个最短路一算sum(w)再max).
取以上包
裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
)+vi
了一下，可以给
出更小的 W 的通解形式：
【在 h**6 的大作中提到】
:
: 别处看来的算法，稍加修改。
: 关于背包问题的另一思考：
: 有重量为w1, w2, ..., wn的若干包裹，其价值为v1, v2, ..., vn。现在不限个数的取以上包裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
: 已知包裹 i 的单位重量价值最高，是否存在一个 W，对于所有 M>W，f(M) = f(M-wi)+vi
: 这里的 W，也就是贪婪算法起点的上限。前面求出 W = [sum(w)-wi]*(wi-1)
: 具体到这题，也就是 W = (4+5+7+8+9)*(6-1) = 165
: blaze 给出一个更小的 W 值，但用到了这些数字的特殊性，不能成为通解。我思考了一下，可以给出更小的 W 的通解形式：
: 不失一般性，设 w1: 除了包裹 i 之外所有包裹总数不得大于等于 wi
| K*******g
发帖数: 26 | 72 你俩思路很对，不过f(n)=5f(n-6)，而不是4f(n-6)。
所以结果要重新算.
【在 b***e 的大作中提到】
: 这个也行，more rigid upper bound. 不过没必要。 前面那招直接上确界就求出来了
: (每个最短路一算sum(w)再max).
:
: 取以上包
: 裹使总重量恰好为 M，怎么样才能使得包裹总价值最高？
: )+vi
: 了一下，可以给
: 出更小的 W 的通解形式：
| p*****l
发帖数: 721 | 73 This is the same result as x=y=z=(n-x-y-z)
In general,
if x1+x2+...+Xn=C (C is a const) then
Max(x1*x2*...*xn) happens when x1==x2....=xn
【在 c***n 的大作中提到】
: n/4 = 19/4 = 4.75, 所以究竟是4还是5, 要看具体情况.
|
|
