Pythonで指定された単調シーケンスの要素位置を検索します

数lと単調増加シーケンスf（m）があるとします。ここで、f（m）=am + bm [log2（m）] + cm ^ 3および（a =1、2、3、…）、（b =1、2、3、…）、（c =0、1、2、3、…）

ここで、[log2（m）]は2を底とする対数であり、値を切り捨てます。だから、

m =1の場合、値は0です。

m =2-3の場合、値は1です。

m =4-7の場合、値は2です。

m =8-15の場合、値は3などです。

f（m）=lとなるような値mを見つける必要があります。シーケンスにlが存在しない場合は、0を出力する必要があります。値は次のように表すことができるようになっていることに注意する必要があります。 64ビットおよび100以下の3つの整数a、b、c。

したがって、入力がa =2、b =1、c =1、l =12168587437017のような場合、出力はf（23001）=12168587437017

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

• SMALLER_VAL：=1000000

• LARGER_VAL：=1000000000000000

• 関数solve（）を定義します。これにはa、b、c、nが必要です

• ans：=a * n

• lg_val：=nの対数基数2のフロア

• ans：=ans + b * n * lg_val

• ans：=ans + c * n ^ 3

• ansを返す

• メインの方法から、次のようにします-

• 開始：=1

• 終了：=SMALLER_VAL

• cが0と同じ場合、

  • 終了：=LARGER_VAL

• ans：=0

• 開始<=終了、実行

  • mid：=（開始+終了）/ 2（整数部分のみを取る）

  • val：=resolve（a、b、c、mid）

  • valがkと同じ場合、

    • ans：=mid

    • ループから出てきます

  • それ以外の場合、val> kの場合、

    • 終了：=半ば-1

  • それ以外の場合

    • 開始：=mid + 1

• ansを返す

例

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

from math import log2, floor
SMALLER_VAL = 1000000
LARGER_VAL = 1000000000000000
def solve(a, b, c, n) :
   ans = a * n
   lg_val = floor(log2(n))
   ans += b * n * lg_val
   ans += c * n**3
   return ans
def get_pos(a, b, c, k) :
   begin = 1
   end = SMALLER_VAL
   if (c == 0) :
      end = LARGER_VAL
   ans = 0
   while (begin <= end) :
      mid = (begin + end) // 2
      val = solve(a, b, c, mid)
      if (val == k) :
         ans = mid
         break
      elif (val > k) :
         end = mid - 1
      else :
         begin = mid + 1
   return ans
a = 2
b = 1
c = 1
k = 12168587437017
print(get_pos(a, b, c, k))

入力

2,1,1,12168587437017

出力

23001