Fibonacci

[adina0822]

We consider two words A1 and A2 which contain only lowercase. The An (n>=3) word is formed like this An=An-1 + An-2, where (+) means concatenation. All these words A1, A2, A3 ... An are concatenated and form a new word A. We want to form a new word which has m characters from the word A.

The input file bifo.in contains the two words A1 and A2, the integer number m and m integer numbers that represent the position of the character we want to use from the word A. This numbers may have maximum 100 figures.

The output file bifo.out will contain the word formed using the m characters.

the length of A1 and A2 <=100
1 ≤ M ≤ 100
The numbering of the positions in the word A begins with 1

e.g.
bifo.in
ab
cdx
3
10
4
15

bifo.out
xdb

Explanations
The first five words A1, A2, A3, A4 and A5 are ab, cdx, abcdx, cdxabcdx, abcdxcdxabcdx.
Concatenating this words we obtain the word A
abcdxabcdxcdxabcdxabcdxcdxabcdx...


How should I solve this without actually concatenating the words?

[ne555]

Let's make a variation: the number represents the index in the A_m word.
You know that A_m = concat( A_{m-1}, A_{m-2} which means that length( A_m ) = length( A_{m-1} ) + length( A_{m-2} )
so it's quite easy to see if the character is from the A_{m-1} word or from the A_{m-2}. Just keep descending till you reach one of the base words.

Because at most you would descend two positions, you'll need O(m) steps to reach a base word. Having to check 'm' characters make it O(m^2), but as m is small that may be acceptable.

[adina0822]

Thank you. I'll try to apply that.