多くの子供たちがPythonでルールを維持しながらキャンディーを配布しながらキャンディーを手に入れる鍬を見つけるプログラム

k個のキャンディーがあるとします。私たちはそれらを子供たちに分配しなければなりません。今、いくつかのルールがあります

• i番目の子供はi^2個のキャンディーを受け取ります
• インデックスiの子供は、インデックス1からi-iまでのすべての子供にサービスが提供されるまでキャンディーを受け取りません
• i番目の子供がi^2個のキャンディーを受け取らない場合、それは有効なサーブではありません。

したがって、入力がk =20の場合、出力は3になります。これは、最初の1つが1になり、2番目の値が2 ^ 2 =4になり、3番目の値が3 ^ 2 =9になりますが、4番目の値には4が必要だからです。 ^ 2 =16ですが、キャンディーは6つしか残っていないため、これは有効な配布ではないため、3人の子供のみが提供されます。

これを解決するには、次の手順に従います-

• 左：=0、右：=k
• 右-左>1、実行
  • mid：=（左+右）の床/ 2
  • （mid *（mid + 1）*（2 * mid + 1）/ 6）> kのフロアの場合、
    • 右：=半ば
  • それ以外の場合、
    • 左：=中央
• if right *（right + 1）*（2 * right + 1）<=k * 6、then
  • 右に戻る
• 左に戻る

例

理解を深めるために、次の実装を見てみましょう-

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