fib2.cpp

#include <fstream>
#include <iostream>

std::ifstream in("fib2.inp");
std::ofstream out("fib2.out");

struct fib_str {
    uint32_t len;
    uint32_t count_a;
};

struct fib_str fib_strs[46];

void generate() {
    int i;

    fib_strs[0].len = 1;
    fib_strs[0].count_a = 1;

    fib_strs[1].len = 1;
    fib_strs[1].count_a = 0;

    for (i = 2; i <= 45; i++){
        fib_strs[i].len = fib_strs[i-1].len + fib_strs[i-2].len;
        fib_strs[i].count_a = fib_strs[i-1].count_a + fib_strs[i-2].count_a;
    }
}

uint32_t calc(uint32_t n, uint32_t k){
    int left = n-2,
        right = n-1,
        result = 0;
    if (fib_strs[n].len == k){
        return fib_strs[n].count_a;
    }
    
    if (k <= fib_strs[left].len) {
        return calc(left, k);
    } else {
        result += fib_strs[left].count_a;
        k -= fib_strs[left].len;
        return result + calc(right, k);
    }
}

int main(){
    uint32_t t, n, k;

    generate();
    in >> t;
    while (t) {
        in >> n >> k;
        out << calc(n, k) << std::endl;
        t--;
    }
    in.close();
    out.close();
}