[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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.4ms with 1 query(s).