k個の監視ステーションがPythonの特定のポイントを監視するのに十分かどうかを調べるプログラム

半径rまでの近くの環境を監視できるセンサーモジュールがあるとします。モジュールの監視円のラティスポイントには、監視する必要のあるものがいくつかあります。したがって、k個の低電力モジュールは、それらの特定のポイントのみを監視できるように配置されます。半径の2乗と低電力モジュールのk数を考えると、ポイントを正しく監視できるかどうかを確認する必要があります。監視が可能な場合はtrueを返し、そうでない場合はfalseを返します。

したがって、入力が半径の2乗（j）=4、監視ポイントの数（k）=3のような場合、出力はFalseになります

j =4の場合、監視円の円周上に4つのポイントがあります。つまり、（0,2）、（0、-2）、（2,0）、および（-2,0）です。したがって、3つの新しい監視ステーションを導入すると、ポイントを完全に監視することはできません。

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

• square_set：=44721までの値の2乗を含むセット
• i：=0
• res：=0
• i <（j ^ 0.5）の間、do
  • （j --i ^ 2）がsquare_setに存在する場合、
    • res：=res + 1
  • i：=i + 1
• res：=res * 4
• k> =resの場合、
  • Trueを返す
• それ以外の場合、
  • Falseを返す

例

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

square_set = set([z ** 2 for z in range(44722)])
def solve(j, k):
    i = 0
    res = 0
    while i < (j ** 0.5):
        if j - i ** 2 in square_set:
            res += 1
        i += 1    
    res *= 4
    if k >= res:
        return True
    else:
        return False

print(solve(4, 3))

入力

4, 3

出力

False