Xâu FIBONACCI (đơn giản)


Submit solution

Points: 2
Time limit: 1.0s
Memory limit: 250M

Author:
Problem types

Một dãy xâu ký tự G chỉ bao gồm các chữ cái A và B được gọi là dãy xâu Fibonacci nếu thỏa mãn tính chất: \(G(1) = A; G(2) = B; G(n) = G(n-2) + G(n - 1)\). Với phép cộng (+) là phép nối hai xâu với nhau. Bài toán đặt ra là tìm ký tự ở vị trí thứ i (với số thứ tự được tính từ 1) của xâu Fibonacci thứ n.

Input:

  • Dòng đầu tiên gồm 1 số nguyên T là số lượng bộ test với \((T \le 100)\)
  • T Dòng tiếp theo gồm 2 số nguyên Ni với \((0 < N < 93)\) và \((1 \le i \le 10^{18})\)

Output:

  • Ứng với mỗi dòng test case in ra đáp án của bài toán

Example:

Input:

 2
 6 4
 8 19

Output:

 A
 B

Explanation:

  • Ở test case 1: ta có F[6] = BABABBAB vì trí thứ 4 là ký tự A

Comments


  • 1
    cotyey  commented on Sept. 1, 2018, 12:18 a.m.

    code của hieuvip1301 đúng r nhưng chưa gọi hàm run() trong main