We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #230: Fibonacci Words
  4. Discussions

Project Euler #230: Fibonacci Words

  • michael_lb_qu
     + 0 comments

    I believe my algorithm below should be correct and it works for cases 1-21. But it is not optimized since it reports "time limit exceeded" for cases beyond 22... Any thoughts about it? Thanks!

    void findInd(vector <long long> &fib, long long &n, int &j){
    //Note that fib[j] = fib[j-2] + fib[j-1]
    //We need to confirm whether n is within fib[j-2] or fib[j-1]
    if (j==0 || j==1){
        return;
    }
    if (n > fib[j-2]){
        //n is beyond fib[j-2], so we chop off fib[j-2] from n
        //And look for new n within fib[j-1]
        n -= fib[j-2];
        j--;
        findInd(fib, n, j);
    }
    else{
        //n is within fib[j-2] 
        j = j-2;
        findInd(fib, n, j);
    }
}
char findChar(string sa, string sb, long long n){
    long long la = sa.length();
    long long lb = sb.length();
    if (n <= la){
        return(sa[n-1]);
    }
    if (n <= la + lb){
        string sc = sa + sb;
        return(sc[n-1]);
    }
    vector <long long> fib;
    fib.push_back(la);
    fib.push_back(lb);
    while(fib[fib.size()-1]<n){
        fib.push_back(fib[fib.size()-2]+fib[fib.size()-1]);
    }
    int j = fib.size()-1;
    findInd(fib, n, j);
    if (j==0){
        return sa[n-1];
    }
    else{
        return sb[n-1];
    }
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++){
        string sa, sb;
        long long n;
        cin >> sa >> sb >> n;
        cout<<findChar(sa, sb, n)<<endl;
    }
    return 0;
}