Pythonで赤ちゃんと巨大なステップによって目的地に到達するために必要な最適なステップの数を見つけるためのプログラム

クエリQのリストがあり、各クエリQ [i]にトリプレット[a_i、b_i、d_i]が含まれているとします。最初は位置（0、0）にいると考えてください。その後、1つのステップで、ある位置（x1、y1）から（x2、y2）に移動できます。ここで、これら2点間のユークリッド距離は少なくともa、最大でbです。ここで、クエリごとに、（0、0）から（d_i、0）に到達するために必要な最小ステップ数を見つける必要があります。

したがって、入力がQ =[（2,3,1）、（1,2,0）、（3,4,11）]のようである場合、出力は[2、0、3]になります。 a =2の（0、0）からの最初のクエリは、$ \ left（\ frac {1} {2}、\ frac {\ sqrt {15}} {2} \ right）$、次に（1、0）に移動できます。したがって、2つのステップが必要なので、出力は2です。次のクエリdは0なので、ステップを移動する必要はないので、出力は0です。3番目のステップでは、b=4およびa=3が（0、0 ）から（4、0）、次に（8、0）、次に（11、0）。

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

• 関数steps（）を定義します。これにはa、b、dが必要です
• mmin：=a、bの最小値
• mmax：=a、bの最大値
• dが0の場合、
  • 0を返す
• dがmminまたはmmaxの場合、
  • 1を返す
• d
• リターン2

例

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

from math import ceil

def steps(a, b, d):
   mmin = min(a, b)
   mmax = max(a, b)
   if d is 0:
      return 0
   if d in [mmin, mmax]:
      return 1
   if d < mmax:
      return 2
   return ceil(d / mmax)

def solve(Q):
   res = []
   for q in Q:
      a, b, d = q
      res.append(steps(a, b, d))
   return res

Q = [(2,3,1), (1,2,0), (3,4,11)]
print(solve(Q))

入力

[(2,3,1), (1,2,0), (3,4,11)]

出力

[2, 0, 2.0]