Chương trình tìm cuốc nhiều trẻ em sẽ nhận được kẹo trong khi phân phát chúng duy trì các quy tắc bằng Python

Giả sử chúng ta có k số kẹo. Chúng tôi phải phân phát chúng cho trẻ em. Bây giờ có một số quy tắc

• đứa trẻ thứ i sẽ nhận được i ^ 2 số kẹo
• bất kỳ trẻ em nào ở chỉ mục tôi sẽ không nhận được bất kỳ viên kẹo nào cho đến khi tất cả trẻ em từ chỉ mục 1 đến i-i được phục vụ
• Nếu trẻ thứ i không nhận được i ^ 2 số kẹo, thì đó không phải là một phần ăn hợp lệ.

Vì vậy, nếu đầu vào là k =20, thì đầu ra sẽ là 3 bởi vì, đầu tiên sẽ nhận được 1, thứ hai sẽ nhận được 2 ^ 2 =4, thứ ba sẽ nhận được 3 ^ 2 =9, nhưng thứ tư cần 4 ^ 2 =16, nhưng chúng tôi chỉ còn lại 6 viên kẹo, vì vậy đây không phải là phân phối hợp lệ, vì vậy sẽ chỉ có ba trẻ em được phục vụ.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• left:=0, right:=k
• trong khi phải - trái> 1, thực hiện
  • giữa:=tầng của (trái + phải) / 2
  • nếu tầng của (giữa * (giữa + 1) * (2 * giữa + 1) / 6)> k, thì
    • right:=mid
  • nếu không,
    • left:=mid
• nếu đúng * (phải + 1) * (2 * phải + 1) <=k * 6, thì
  • trả lại bên phải
• quay lại bên trái

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

20

Đầu ra

3