สมมติว่าเรามีขนมอยู่ k จำนวน เราต้องแจกจ่ายให้กับเด็กๆ ตอนนี้มีกฎบางอย่าง
- ลูกจะได้รับ i^2 จำนวนลูกอม
- เด็กที่ดัชนีฉันจะไม่ได้รับขนมใดๆ จนกว่าเด็กทุกคนจากดัชนี 1 ถึง i-i จะได้รับบริการ
- หากลูกๆ ไม่ได้รับลูกอม i^2 จำนวน นั่นถือว่าไม่ใช่การเสิร์ฟที่ถูกต้อง
ดังนั้น ถ้าอินพุตเท่ากับ k =20 ผลลัพธ์จะเป็น 3 เพราะอันแรกจะได้ 1 อันที่สองจะได้ 2^2 =4 อันที่สามจะได้ 3^2 =9 แต่อันที่สี่ต้องการ 4 ^2 =16 แต่เรามีลูกอมเหลืออยู่เพียง 6 ลูก ดังนั้นนี่ไม่ใช่การแจกจ่ายที่ถูกต้อง ดังนั้นจะเสิร์ฟลูกเพียงสามคนเท่านั้น
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ซ้าย :=0, ขวา :=k
- ขณะขวา-ซ้าย> 1 ทำ
- กลาง :=ชั้นของ (ซ้าย + ขวา) / 2
- ถ้าชั้นของ (กลาง * (กลาง + 1) * (2 * กลาง + 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
