## 12045 - Fun with Strings

All about problems in Volume 120. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brainless_the_swiss
New poster
Posts: 5
Joined: Sat Feb 16, 2013 2:19 am

### 12045 - Fun with Strings

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
New poster
Posts: 5
Joined: Sat Feb 16, 2013 2:19 am

### Re: 12045 fun with strings - WA !

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
New poster
Posts: 5
Joined: Sat Feb 16, 2013 2:19 am

### Re: 12045 fun with strings - WA !

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