12045 - Fun with Strings

[brainless_the_swiss]

Dear all,

I keep on having wrong answer for this one. The basic idea behind this challenge is simple : the length a string is the sum of the lengths of the 2 previous strings. Hence if we find the lengths of strings 1 and 2, by using Fibonacci numbers, we can compute the length of every arbitrary string.

It is based on the following formula :

L_n = F_(n-2)*L_1 + F_(n-1)*L_2

where F_k are Fibonacci numbers, with convention F_(-1)=1, F_0=0 and F_1=1

Can one of provide me with a valid input/output ?

Thanks a lot !

Brainless

PS: Here is my code :

Code: Select all

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

/******************************
*                             *
* CONVENTION : F(0)=0, F(1)=1 *
*                             *
*           F(-1)=1           *
*                             *
*******************************/

typedef long long ul;
const ul MOD(1000000007);
ul F[50];

//Warning : The index must be >= -1
ul Fibo(const int& index)
{
    if(index==-1) return 1;
    return F[index];
}

ul mod(ul n)
{
    n%=MOD;
    if(n<0) n += MOD;
    return n;
}

//Returns F_(n+1) and F_n % MOD
//WARNING : the args must be ul type
void mod_fibo(ul& np1, ul& n)
{
    if(np1==0)
    {
        n=mod(-1);
        return;
    }
    else if(np1<50)
    {
        np1 = mod(F[np1]);
        n = mod(F[n]);
    }
    else
    {
        const ul two(2);
        ul F_np1, F_n;
        if(np1%2==0)
        {
            ul F_nd2=np1/two;
            ul F_nd2_m1=np1/two-1;
            mod_fibo(F_nd2, F_nd2_m1);
            F_n=mod(F_nd2*F_nd2+F_nd2_m1*F_nd2_m1);
            F_np1=mod(F_nd2*(F_nd2+two*F_nd2_m1));
        }
        else
        {
            F_np1=n;
            F_n=n-1;
            mod_fibo(F_np1, F_n);
            F_np1=mod(F_np1+F_n);
        }
        np1=F_np1;
        n=F_n;
    }
}

ul mod_fibo(ul n)
{
    ul m=n-1;
    mod_fibo(n, m);
    return n;
}

bool find_initial_lengths(ul& N, ul& L_N, ul& M, ul& L_M, ul& L_1, ul& L_2)
{
    if(M<N)
    {
        swap(M, N);
        swap(L_N, L_M);
    }
    ul F_N_1(Fibo(N-1)), F_N_2(Fibo(N-2)),
        F_M_1(Fibo(M-1)), F_M_2(Fibo(M-2));

    const ul det=F_N_2*F_M_1-F_N_1*F_M_2;

    if(det==0)
    {
        //cerr << "null det" << endl;
        return false;
    }

    ul NOM2=L_M*F_N_2-F_M_2*L_N;
    if(NOM2%det!=0)
    {
        //cerr << "L_2 not an int" << endl;
        return false;
    }
    L_2=NOM2/det;

    ul NOM1=L_N*F_M_1-F_N_1*L_M;
    if(NOM1%det!=0)
    {
        //cerr << "L_1 not an int" << endl;
        return false;
    }
    L_1=NOM1/det;

    return (L_1>=0 and L_2>0) or (L_2>=0 and L_1>0);
}

int main()
{
    F[0]=0;
    F[1]=1;
    int i;
    for(i=2; i<50; ++i)
    {
        F[i]=(F[i-2]+F[i-1]);

    }
    int cases;
    //ifstream in("12045_fun_with_strings_io/output.txt");
    cin >> cases;
    for(int curcase=0; curcase<cases; ++curcase)
    {
        ul N, X, Y, M, K;
        cin >> N >> X >> M >> Y >> K;
        ul L_1, L_2;
        if(find_initial_lengths(N, X, M, Y, L_1, L_2))
        {
            //cout << L_1 << " " << L_2 << endl;
            ul F_n_1(K-1), F_n_2(K-2);
            mod_fibo(F_n_1, F_n_2);
            ul L_K=mod(F_n_2*L_1+F_n_1*L_2);
            cout << L_K << endl;
        }
        else
        {
            //cout << L_1 << " " << L_2 << endl;
            cout << "Impossible" << endl;
        }
    }
    return 0;
}

[brainless_the_swiss]

Dear reader,

If you solved or tried this challenge, can you please tell me if my reasoning is correct ? If so, do you think there is tricky test cases ?

Here is an URL to the statement :
http://uva.onlinejudge.org/index.php?op ... oblem=3196

Thank you in advance !

[brainless_the_swiss]

Finally got AC !!!

The trick is that there are more conditions on L_1 and L_2 (the lengths of first and second string resp.) :

L_1 <= L_2 <= 2*L_1