Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 주어진 단조 시퀀스에서 요소 위치 찾기


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입니다. 따라서 on

f(m) =l이 되도록 m 값을 찾아야 합니다. l이 시퀀스에 없으면 0을 인쇄해야 합니다. 값은 64비트 및 100보다 작거나 같은 세 개의 정수 a, b 및 c.

따라서 입력이 a =2, b =1, c =1, l =12168587437017이면 출력은 f(23001) =12168587437017과 같이 23001이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • SMALLER_VAL :=1000000

  • LARGER_VAL :=1000000000000000

  • solve() 함수를 정의합니다. 이것은, b, c, n

    이 걸립니다.
  • 답변 :=a * n

  • lg_val :=n의 로그 밑수 2의 바닥

  • ans :=ans + b * n * lg_val

  • ans :=ans + c * n^3

  • 반환

  • 기본 방법에서 다음을 수행하십시오 -

  • 시작 :=1

  • 끝 :=SMALLER_VAL

  • c가 0과 같으면

    • 끝 :=LARGER_VAL

  • 답변 :=0

  • 동안 시작 <=종료, 수행

    • mid :=(시작 + 끝) / 2(정수 부분만 사용)

    • val :=해결(a, b, c, 중간)

    • val이 k와 같으면

      • as :=중간

      • 루프에서 나오다

    • 그렇지 않으면 val> k일 때

      • 끝 :=중간 - 1

    • 그렇지 않으면

      • 시작 :=중간 + 1

  • 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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