สมมติว่าเรามีตัวเลข 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 เป็นต้น
เราต้องหาค่า m ให้ f(m) =l ถ้า l ไม่อยู่ในลำดับ เราต้องพิมพ์ 0 เราต้องจำไว้ว่าค่าต่างๆ อยู่ในลักษณะที่สามารถแทนค่าได้ 64 บิตและจำนวนเต็มสามจำนวน a, b และ c น้อยกว่าหรือเท่ากับ 100
ดังนั้น หากอินพุตเป็น a =2, b =1, c =1, l =12168587437017 ผลลัพธ์จะเป็น 23001 โดย f(23001) =12168587437017
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
SMALLER_VAL :=1000000
-
LARGER_VAL :=1000000000000000
-
กำหนดฟังก์ชัน Solve() นี่จะใช้เวลา a, b, c, n
-
ตอบ :=a * n
-
lg_val :=พื้นของล็อกฐาน 2 ของ n
-
ans :=ans + b * n * lg_val
-
ans :=ans + c * n^3
-
กลับมาอีกครั้ง
-
จากวิธีหลัก ให้ทำดังนี้ −
-
เริ่มต้น :=1
-
สิ้นสุด :=SMALLER_VAL
-
ถ้า c เท่ากับ 0 แล้ว
-
สิ้นสุด :=LARGER_VAL
-
-
ตอบ :=0
-
ขณะที่เริ่ม <=สิ้นสุด ทำ
-
mid :=(begin + end) / 2 (ใช้เฉพาะส่วนจำนวนเต็มเท่านั้น)
-
val :=แก้ (a, b, c, กลาง)
-
ถ้า val เท่ากับ k แล้ว
-
ตอบ :=กลาง
-
ออกจากวง
-
-
มิฉะนั้นเมื่อ val> k แล้ว
-
end :=mid - 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
