[Home|Training|Problems|Contests|C Language] | [Login|Register] |
Problems Status Rank Statistics |
Problem D
切绳子
Time Limit: 3000ms
Memory Limit: 65536kb Description
二鸣和晖晖近来试图通过和妹子们玩有趣的小游戏来增进感情。借鉴之前流行的切水果,他们发明了切绳子游戏。游戏的规则如下:开始时你手上有一根长为正整数N的绳子。你选择一个长度X(1 <= X <= N-1且为整数),将绳子切成长为X和N-X两部分,得到操作分(-X^2+N*X+K)。之后,你要在切出来的两段绳子中选择一段再做同样的操作得到三段绳子。继续下去,直到你得到N段长为1的绳子为止(这时你无法再切下去了)。最终得分为你操作分的总和。 为了在妹子面前大显身手,二鸣和晖晖不停地练习这个游戏。突然,他们想到了一个问题:如果每次切绳子时长度X为随机选择的(等概率),手里有多段绳子时切的绳子也是从可以继续切的绳子(长度大于1)中随机选择的,那么最终得分的期望值是多少? Input
一个输入有多组数据(不超过100个)。每组输入只有一行,包含两个整数N,K(N<=1000,K<=10^7)。 Output
对每组输入只输出一行,为得分的期望值,保留整数部分。
Sample Input
2 1 3 1 Sample Output
2 5 Hint
N=2 K=1时,只有一种选择,将绳子切成两个长为1的部分,概率为100%,操作得分为-1+2*1+1=2.N=3 K=1时,第一步有两种选择。 1.X=1 概率为50%,得分为3. 之后只能将长为2的部分切成两半,得分为2.总得分为5 2.X=2 概率为50%,得分为3. 之后只能将长为2的部分切成两半,得分为2.总得分为5 期望为50%*5+50%*5 = 5. Source
whz@USTC ACM team
|