Subtask ~1~:

Ta sinh cây có độ sâu tối đa là ~17~. Sau đó truy vết đường đi trên cây một cách đơn giản.

Subtask ~2~:

Nếu ta có hai phân số ~\frac{a}{b}~ < ~\frac{c}{d}~, ta luôn chứng minh được rằng ~\frac{a}{b} < \frac{a + c}{b + d} < \frac{c}{d}~. Ta sẽ biết được nên đi theo cây con gốc phải nếu ~\frac{a + c}{b + d} < \frac{x}{y}~. Và đi theo cây con gốc trái trong trường hợp ngược lại. Cài đặt thuật toán này tương tự chặt nhị phân. Việc so sánh hai phân số có thể dùng tích chéo.

Subtask ~3~:

Việc khó duy nhất lúc này là so sánh hai phân số. Nếu dùng double hoặc tích chéo long long sẽ xảy ra hiện tượng chạy vô hạn do sai số. Ngoài cách sử dụng bignum hoặc python ra, chúng ta có thể đệ quy để so sánh hai phân số trong thời gian chạy rất nhanh.

Giả sử ta cần so sánh hai phân số ~\frac{a}{b}~ và ~\frac{c}{d}~. Ta quy về hỗn số có phần nguyên lớn nhất: ~\frac{a}{b} = e_1\frac{r_1}{b}~ với ~a = b \times e_1 + r_1~. Tương tự ~\frac{c}{d} = e_2\frac{r_2}{d}~ với ~c = d \times e_2 + r_2~. Khi đó nếu ~e_1 > e_2~ thì ~\frac{a}{b} > \frac{c}{d}~. Nếu ~e_1 < e_2~ thì ~\frac{a}{b} < \frac{c}{d}~. Nếu ~e_1 = e_2~, ta so sánh tiếp ~\frac{b}{r_1}~ và ~\frac{d}{r_2}~ bằng đệ quy. Cứ làm như vậy đến khi ~r_1 = 0~ hoặc ~r_2 = 0~ hoặc tìm ra đáp án.

Code mẫu

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

pll n;

bool ss(pll a, pll b) {
    ll x = a.F / a.S;
    ll y = b.F / b.S;
    if (x != y) return x > y;
    a.F %= a.S;
    b.F %= b.S;
    if (!a.F && !b.F) return 0;
    if (!a.F) return 0;
    if (!b.F) return 1;
    swap(a.F, a.S);
    swap(b.F, b.S);
    return !ss(a, b);
}

void solve() {
    cin >> n.first >> n.second;
    string res = "";
    pll l = {0, 1};
    pll r = {1, 0};
    pll mid = {1, 1};
    while (n != mid) {
        if (ss(n, mid)) {
            res += 'R';
            l = mid;
        } else {
            res += 'L';
            r = mid;
        }
        mid = {l.F + r.F, l.S + r.S};
    }
    cout << res << endl;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt;
    cin >> tt;
    while (tt --) {
        solve();
    }
    return 0;
}