| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1353
切绳子
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
|