k개의 사탕이 있다고 가정합니다. 아이들에게 나누어주어야 합니다. 이제 몇 가지 규칙이 있습니다.
- 이 아이는 i^2개의 사탕을 받습니다.
- 색인 i의 모든 어린이는 색인 1에서 i-i까지의 모든 어린이에게 제공될 때까지 사탕을 받지 않을 것입니다.
- i번째 아이들이 i^2개의 사탕을 받지 못하면 유효한 서브가 아닙니다.
따라서 입력이 k =20과 같으면 출력은 3이 됩니다. 왜냐하면 첫 번째 것은 1을 얻고, 두 번째는 2^2 =4를, 세 번째는 3^2 =9를 얻지만 네 번째는 4가 필요하기 때문입니다. ^2 =16이지만 사탕이 6개밖에 남지 않았으므로 유효한 배포가 아니므로 3명의 어린이만 제공됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 왼쪽 :=0, 오른쪽 :=k
- 오른쪽 - 왼쪽> 1, do
- 중간 :=(왼쪽 + 오른쪽) / 2의 바닥
- 바닥이 (mid * (mid + 1) * (2 * mid + 1) / 6)> k인 경우
- 오른쪽 :=중간
- 그렇지 않으면
- 왼쪽 :=중간
- 맞으면 *(오른쪽 + 1) *(2 * 오른쪽 + 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