หาตำแหน่งสมาชิกในลำดับมโนโทนิกที่กำหนดใน C++

แนวคิด

ได้รับจำนวนเต็ม l และลำดับมโนโทนิกเพิ่มขึ้น:

f(m) = a*m + b*m*[log2(m)] + c*m^3 โดยที่ (a = 1, 2, 3, ...), (b = 1, 2, 3, ...), (c = 0, 1, 2, 3, ...) หมายเหตุ: [log2(m)] หมายถึง log ฐาน 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

อินพุต

a = 7, b = 3, c = 0, l = 119753085330

เอาต์พุต

1234567890

วิธีการ

วิธี Naive - หาค่า f(m) สำหรับทุก m และเปรียบเทียบ

วิธีที่มีประสิทธิภาพ - ใช้ Binary Search เลือก m = (min + max) / 2 โดย min และ max เป็นค่าต่ำสุดและสูงสุดของ m แล้ว:

• ถ้า f(m) < l ให้เพิ่ม m
• ถ้า f(m) > l ให้ลด m
• ถ้า f(m) = l แสดงว่า m คือคำตอบ
• ทำซ้ำจนกว่าจะหาค่าที่ต้องการหรือไม่สามารถหาได้ในลำดับ

ตัวอย่างโค้ด C++

// การนำไปใช้ C++ ของวิธีการ
#include <iostream>
#include <math.h>
#define SMALL_N 1000000
#define LARGE_N 1000000000000000
using namespace std;

// ฟังก์ชันคืนค่า f(m) สำหรับ a, b, c, m ที่กำหนด
long long func(long long a1, long long b1, long long c1, long long m) {
    long long res1 = a1 * m;
    long long logVlaue1 = floor(log2(m));
    res1 += b1 * m * logVlaue1;
    res1 += c1 * (m * m * m);
    return res1;
}

long long getPositionInSeries1(long long a1, long long b1, long long c1, long long l) {
    long long start1 = 1, end1 = SMALL_N;
    // ถ้า c เป็น 0 ค่า m สามารถอยู่ในออเดอร์ 10^15
    // ถ้า c1!=0 ค่า m^3 ต้องอยู่ในออเดอร์ 10^18
    // ดังนั้นค่าสูงสุดของ m คือ 10^6
    if (c1 == 0) {
        end1 = LARGE_N;
    }
    long long ans1 = 0;
    // ค้นหาแบบมีประสิทธิภาพด้วย binary search
    while (start1 <= end1) {
        long long mid1 = (start1 + end1) / 2;
        long long val1 = func(a1, b1, c1, mid1);
        if (val1 == l) {
            ans1 = mid1;
            break;
        } else if (val1 > l) {
            end1 = mid1 - 1;
        } else {
            start1 = mid1 + 1;
        }
    }
    return ans1;
}

// โค้ดหลัก
int main() {
    long long a1 = 2, b1 = 1, c1 = 1;
    long long l = 12168587437017;
    cout << getPositionInSeries1(a1, b1, c1, l) << endl;
    long long a2 = 7, b2 = 3, c2 = 0;
    long long l1 = 119753085330;
    cout << getPositionInSeries1(a2, b2, c2, l1) << endl;
    long long a3 = 6, b3 = 2, c3 = 1;
    long long l2 = 11975309533;
    cout << getPositionInSeries1(a3, b3, c3, l2) << endl;
    return 0;
}

เอาต์พุต

23001 1234567890 0