在Python中编写程序以找到在分发糖果时保持规则的前提下有多少个孩子会得到糖果
假设我们有k个糖果。我们必须将它们分配给孩子们。有一些规则:
- 第i个孩子将获得i ^ 2颗糖果
- 任何位于索引i的孩子在从索引1到i-i的所有孩子都被服务之前都不会得到任何糖果
- 如果第i个孩子没有获得i ^ 2颗糖果,则这不是一个有效的服务。
因此,如果输入为k = 20,则输出将为3,因为第一个人将获得1,第二个人将获得2 ^ 2 = 4,第三个人将获得3 ^ 2 = 9,但第四个孩子需要4 ^ 2 = 16,但我们只剩下6颗糖果,所以这不是一个有效的分配,因此只有三个孩子将被服务。
为了解决这个问题,我们将按以下步骤进行 –
- left:= 0,right:= k
- while right – left>1,do
- mid:=(left + right)/ 2的floor
- 如果(mid (mid + 1)(2 * mid + 1)/ 6的floor)>k,则
- right:=中
- 否则,
- left:=中
- 如果right (right + 1)(2 * right + 1)≤k * 6,则
- 返回正确
- 返回左
例子
让我们看一下以下实现以更好地理解 –
def solve(k):
left = 0
right = k
while(right-left> 1):
mid =(left + right)// 2
if((mid *(mid + 1)*(2 * mid + 1)// 6> k):
right = mid
else:
left = mid
if(right *(right + 1)*(2 * right + 1)≤k * 6):
return right
return left
k = 20
print(solve(k))
输入
20
输出
3