Pythonでn人が反転したライトの数をカウントするプログラム

番号がnで、部屋にn個のトグルスイッチがあり、その部屋にn人がいるとすると、次のようにスイッチを切り替えます-

• 人1が来て、すべてのスイッチを切り替えます。
• Person 2が来て、2：2、4、6、...の倍数のスイッチを切り替えます。
• 人iが来て、iの倍数のスイッチを切り替えます。など。

最終的にオンの位置にあるスイッチの数を見つける必要があります。

したがって、入力がn =5の場合、最初の電球は[0、0、0、0、0]であるため、出力は2になります。

• プレーヤー1の後：[1、1、1、1、1]
• プレーヤー2の後：[1、0、1、0、1]
• プレーヤー3の後：[1、0、0、0、1]
• プレーヤー4の後：[1、0、0、1、1]
• プレーヤー5の後：[1、0、0、1、0]

最後に2つのライトがオン状態になっています

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

• l：=0
• r：=n
• l <=rの場合、do
  • mid：=l +（r --l）/2のフロア
  • mid * mid <=n <（mid + 1）^ 2の場合、
    • 途中で戻る
  • それ以外の場合、n
  • r：=mid
• それ以外の場合、
  • l：=mid + 1

例

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

def solve(n):
   l, r = 0, n
   while l <= r:
      mid = l + (r - l) // 2
      if mid * mid <= n < (mid + 1) * (mid + 1):
         return mid
      elif n < mid * mid:
         r = mid
      else:
         l = mid + 1

n = 5
print(solve(n))

入力

5

出力

2