// link: http://uva.onlinejudge.org/external/120/12041.html
// Runtime: 0.080s
// Tag: Recursive, Dp
/*
* File: main.cpp
* Author: shahab
*
* Created on August 5, 2011, 8:58 PM
*/
#include <cstdlib>
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
long long fibo [50];
string bfs [50];
void generateFibo ()
{
fibo [0] = 1;
fibo [1] = 1;
for ( int i = 2; i <= 50; i++ ) fibo [i] = fibo [i - 1] + fibo [i - 2];
}
int bfsOfPosition (int n, long long pos)
{
if ( n < 31 ) return bfs [n] [pos] - '0';
if ( pos < fibo [n - 2] ) return bfsOfPosition (n - 2, pos);
else return bfsOfPosition (n - 1, pos - fibo [n - 2]);
}
void generateBfs ()
{
bfs [0] = "0";
bfs [1] = "1";
for ( int i = 2; i < 31; i++ ) bfs [i] = bfs [i - 2] + bfs [i - 1];
}
int main(int argc, char** argv)
{
generateFibo ();
generateBfs ();
int testCase; scanf ("%d", &testCase);
while ( testCase-- ) {
long long n, start, end; scanf ("%lld %lld %lld", &n, &start, &end);
if ( n > 48 ) {
n = n % 2 ? 47 : 48;
}
if ( n < 31 )
for ( long long i = start; i <= end; i++ ) printf ("%c", bfs [n] [i]);
else
for ( long long i = start; i <= end; i++ ) printf ("%d", bfsOfPosition (n, i));
printf ("\n");
}
return 0;
}

### Like this:

Like Loading...

*Related*

Could you explain how have you implemented DP here?

@Niteesh Mehra

There are 2 gotchas here

1. bfs string position query wont exceed 2^31. (i, j < 2^31 – 1)

for example,

50th bfs = 48th bfs + 49th bfs

that means, 1st portion of 50th bfs is exactly same as 48th bfs

so, if 48th bfs length exceeds 2^31 then you don't need to find 50th bfs

you can tell the answer of any question on 50th bfs using 48th bfs

so its enough to create upto 48th bfs … but that will exceed time and space complexity

thats why, i created upto 30 bfs, which is feasible in terms of space & time complexity

now we need to think about 31th to 48th bfs

2. query won't exceed 10000. ( j – i <= 10000 )

so i ran a recursive function here, which returns 0 / 1

bfsOfPosition (int n, long long pos)

that is, nth bfs contains 0 or 1 in the pos-th position

if ( n < 31 ) i’ve already calculated it, so just return the result

otherwise

we need to determine, pos-th character of nth bfs whether comes from (n-2)th bfs or (n-1)th bfs

for example, we want to find the 250th character of 14th bfs

14th bfs length = 377

13th bfs length = 233

12th bfs length = 144

as we know 14th bfs = 12th bfs + 13th bfs

so 250th character of 14th bfs definitely not in 12th bfs

250th character of 14th bfs is same as -> (250 – 133)th character of 13th bfs

hope it helps 🙂

my solution is not a good dp .. but its similar to a dp solution 😛