# 13086 - Golden Ratio Overheat

>author: Utin
###### tags: `recursion`

---

## Brief
See the code below
Similar to 12602 OuQ String

## Solution 0

#include <stdio.h>
#include <string.h>

int T, n;
char f0[2001], f1[2001];
long long int k, len[61];

char search(int n, long long int k);

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%s %s %d %lld", f0, f1, &n, &k);
        len[0] = strlen(f0);
        len[1] = strlen(f1);
        for (int i = 2; i <= n; i++) {
            len[i] = len[i-1] + len[i-2];
        }
        char ans = search(n, k);
        printf("%c\n", ans);
    }
}

char search(int n, long long int k) {
    if (n == 0) return f0[k];
    if (n == 1) return f1[k];
    if (k < len[n-2]) return search(n-2, k);
    return search(n-1, k-len[n-2]);
}
// By Utin

## Reference