Hiểu bài toán

Xác định một dãy số bắt đầu bằng A0 = 0, A1 = 0, A2 = 1. Các số tiếp theo được tính theo công thức An = A{n-1} + A{n-2} + A{n-3}. Với mỗi giá trị đầu vào M, bài toán yêu cầu tìm số Ax đầu tiên trong dãy sao cho A_x >= M.

Các cách tiếp cận

Cách Tìm kiếm tuần tự (Linear Search)

#include <bits/stdc++.h>
using namespace std;
#define int long long 
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  int n; 
  while(cin >> n){
    // Khoi tao day so
    int a0 = 0, a1 = 0, a2 = 1;
    int current = 0;

    // Truong hop dac biet cho nho hon hoac bang 1
    if(n <= 0){
        cout << 0 << '\n';
        continue;
    }
    if(n == 1){
        cout << 1 << '\n';
        continue;
    }

    // Vong lap tim so dau tien >= n
    while(current < n){
        current = a2;
        int next_val = a2 + a1 + a0;
        a0 = a1;
        a1 = a2;
        a2 = next_val;
    }
    cout << current << '\n';
  }
  return 0;
}

• Time Complexity: O(K) với K là chỉ số của số tìm được (tương đương log(M) theo hàm số mũ)
• Space Complexity: O(1)

Phương pháp này không cần lưu trữ toàn bộ dãy số. Nó chỉ cần 3 biến để lưu 3 số gần nhất và lặp lại việc sinh số cho đến khi tìm được số >= M. Đây là cách tiếp cận đơn giản nhất về mặt logic.

Cách Tiền xử lý và Tìm kiếm nhị phân (Precomputation + Binary Search)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<unsigned long long> precomputeTribonacci() {
    vector<unsigned long long> tribonacci;
    tribonacci.push_back(0); // A0
    tribonacci.push_back(0); // A1
    tribonacci.push_back(1); // A2

    while (true) {
        int n = tribonacci.size();
        unsigned long long next = tribonacci[n-1] + tribonacci[n-2] + tribonacci[n-3];

        // Kiểm tra tràn số
        if (next < tribonacci[n-1]) { 
            break;
        }
        tribonacci.push_back(next);
    }
    return tribonacci;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<unsigned long long> tribonacci = precomputeTribonacci();

    unsigned long long M;
    while (cin >> M) {
        // Sử dụng lower_bound để tìm vị trí đầu tiên >= M
        auto it = lower_bound(tribonacci.begin(), tribonacci.end(), M);
        if (it != tribonacci.end()) {
            cout << *it << '\n';
        }
    }
    return 0;
}

• Time Complexity: O(T log T) cho tiền xử lý (T là số lượng phần tử trong dãy tới giới hạn), O(log T) cho mỗi truy vấn
• Space Complexity: O(T) (khoảng 100-200 phần tử cho số unsigned long long)

Đầu tiên, ta sinh và lưu trữ toàn bộ dãy số vào một vector cho đến khi vượt quá giới hạn kiểu dữ liệu (ví dụ: unsigned long long). Với mỗi truy vấn M, ta sử dụng hàm lower_bound (tìm kiếm nhị phân) để tìm phần tử >= M đầu tiên trong vector đã được sắp xếp sẵn. Cách này xử lý nhiều truy vấn rất nhanh.

Cách Tiền xử lý mảng tĩnh (Static Precomputation)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
int const limit = 1e6;
ll a[limit+5];

void sang() {
    a[0]=0;
    a[1]=0;
    a[2]=1;
    for (ll i=3; i<=limit; i++) {
        a[i]=a[i-1]+a[i-2]+a[i-3];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    sang();
    while(cin>>n) {
        for(ll i=0; ; i++) {
            if (a[i]>=n) {
                cout<<a[i]<<'\n';
                break;
            }
        }
    }
    return 0;
}

• Time Complexity: O(1) cho mỗi truy vấn (sau khi tiền xử lý)
• Space Complexity: O(K)

Giải pháp này sử dụng một mảng tĩnh lớn được tính toán sẵn (trong hàm sang). Với mỗi đầu vào, nó chỉ cần duyệt tuyến tính từ đầu mảng để tìm giá trị >= M. Tuy nhiên, do limit cố định, giải pháp này có thể không đúng nếu M nằm ngoài khoảng đã tính hoặc vượt quá giới hạn biến long long.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Dãy số tăng rất nhanh (tốc độ tăng trưởng lũy thừa), nên số lượng phần tử cần tính để vượt qua ngưỡng M (kể cả M rất lớn) là rất nhỏ (dưới 200 phần tử cho界限 của unsigned long long).
• Bài toán có thể được giải quyết hiệu quả bằng cách sinh dãy số một lần (tiền xử lý) và sử dụng tìm kiếm nhị phân cho các truy vấn sau đó.

Lỗi thường gặp

• Lựa chọn kiểu dữ liệu: Do các số trong dãy tăng rất nhanh, cần sử dụng kiểu dữ liệu có phạm vi lớn như long long hoặc unsigned long long để tránh tràn số (overflow).
• Bị infinite loop: Nếu M quá lớn (lớn hơn số lớn nhất có thể biểu diễn), chương trình phải có cơ chế dừng (ví dụ: kiểm tra tràn số khi sinh dãy hoặc giới hạn số lần lặp).