2524. Fibonacci strings

 

In mathematics, so-called recurrence relations are often used. They are usually employed to define numerical sequences; however, they can also be used to define sequences of strings.

One example of strings defined by recurrence relations is the Fibonacci strings. They are defined as follows:

F0 = a,

F1 = b,

Fi = Fi - 2 + Fi - 1, i > 1

 

The first seven Fibonacci strings are:

a,

b,

ab,

bab,

abbab,

bababbab,

abbabbababbab

 

Dima attends an olympiad programming club and is interested in string algorithms. Recently, he learned about Fibonacci strings and quickly noticed that as the index i increases, the length of the string Fi grows very rapidly. Therefore, storing the entire string requires too much memory. As a result, Dima decided to restrict himself to the problem of finding individual characters.

Write a program that determines the k-th character of the string Fn.

 

Input. The first line contains the number of test cases t (1 ≤ t ≤ 100). Each of the next t lines contains two integers n and k (0 ≤ n ≤ 45, 1 ≤ k ≤ |Fn|), where |Fn| denotes the length of the string Fn. Character positions in the string are numbered starting from one.

 

Output. Print t lines. Each line should contain exactly one character – the answer to the corresponding test case.

 

Sample input

Sample output

 
4
0 1
1 1
3 2

7 7

a

b

a

a

 

 

SOLUTION

recursion

 

Algorithm analysis

Fibonacci strings are defined recursively:

Fn = Fn–2 + Fn–1

This means that the string Fn consists of two consecutive parts:

·        the first Fn–2 characters form the string Fn–2,

·        the next Fn–1 characters form the string Fn–1.

Therefore, to find the k-th character of the string Fn, it is not necessary to construct the entire string. It is enough to determine in which of the two parts it lies.

 

Let Fn(k) denote the k-th character of the string Fn.

Then:

·        if k ≤ |Fn–2|, the required character lies in the first part:

Fn(k) = Fn-2(k)

·        otherwise (if k > |Fn–2|), the character lies in the second part:

Fn(k) = Fn-1(k – |Fn–2|)

Thus, the problem reduces to finding a character in strings with smaller indices.

 

Example

Consider the string F6, for which the following relations hold:

·        F6 = F4 + F5,

·        |F4| = 5, |F5| = 8

Let us compute F6(4). Since k = 4 ≤ |F4| = 5, we have F6(4) = F4(4).

Let us compute F6(7). Since k = 7 > |F4| = 5, we have F6(7) = F5(7 – 5) = F5(2).

 

Algorithm implementation

The array fib stores the lengths of the Fibonacci strings:

·        fib[i] contains the length of the string Fi.

 

#define MAX 44

int fib[MAX] = {1, 1};

 

The function solve returns the k-th character of the string Fn without constructing the string itself in full.

 

char solve(int n, int k)

{

 

The base cases n = 0 and n = 1 are handled separately.

 

  if (n == 0) return 'a';

  if (n == 1) return 'b';

 

It is known that Fn = Fn - 2 + Fn - 1.

·        If k ≤ Fn - 2, then the k-th character lies in the string Fn - 2.

·        If k > Fn - 2, then the k-th character lies in the string Fn - 1. However, its position is shifted by the length of the first part, so we look for the character with index k – Fn - 2.

 

  if (k <= fib[n-2]) return solve(n - 2, k);

  return solve(n - 1, k - fib[n-2]);

}

 

The main part of the program. Compute the first MAX Fibonacci numbers.

 

for (i = 2; i < MAX; i++)

  fib[i] = fib[i-1] + fib[i-2];

 

Read the number of test cases tests.

 

scanf("%d",&tests);

while (tests--)

{

 

Compute and print the answer for each test case.

 

  scanf("%d %d",&n,&k);

  printf("%c\n",solve(n,k));

}