Bedao Mini Contest 13 - FRACPATH

View as PDF

Submit solution


Points: 0.25 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho hai phân số ~\frac{0}{1}~ và ~\frac{1}{0}~. Ta tạo ra dãy vô hạn bằng cách: xét hai phân số ~\frac{a}{b}~ và ~\frac{c}{d}~ đang ở cạnh nhau, ta thêm phân số ~\frac{a\ +\ c}{b\ +\ d}~ vào vị trí giữa. Dãy số có thể tạo ra cây nhị phân vô hạn đầy đủ như hình minh hoạ:

image
hình minh hoạ

Ta lần lượt sử dụng ~L~ và ~R~ thể hiện việc đi sang cây con trái và cây con phải khi đi từ gốc ~\frac{1}{1}~. trungnotchung có ~q~ thắc mắc bấy lâu nay: tìm đường đi ngắn nhất giữa hai phân số ~\frac{1}{1}~ và ~\frac{x}{y}~.

Input

  • Dòng đầu tiên nhập số nguyên dương ~q~ ~(1 \le q \le 100)~ - số câu hỏi của bạn Trung.

  • Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa hai số nguyên dương ~(x_i, y_i)~ trong câu hỏi thứ ~i~ mà bạn Trung đưa ra. Dữ liệu đảm bảo luôn có ít nhất một đường đi giữa hai phân số ~\frac{1}{1}~ và ~\frac{x_i}{y_i}~ ~(x_i, y_i \le 9 \times 10^{18},\ max(x_i, y_i) > 1,\ gcd(x_i, y_i) = 1)~.

Output

  • In ra ~q~ dòng là đáp án của các câu hỏi.

Subtask

  • ~20\%~ số test có độ dài xâu kết quả không vượt quá ~17~.

  • ~70\%~ số test có ~x_i, y_i \le 10^9~.

  • ~10\%~ số test không có ràng buộc gì thêm.

Sample Input 1

2
5 7
878 323

Sample Output 1

LRRL
RRLRRLRLLLLRLRRR

Notes

Ở testcase đầu tiên, đường đi ngắn nhất là ~\frac{1}{1}~ ~\stackrel{L}{\rightarrow}~ ~\frac{1}{2}~ ~\stackrel{R}{\rightarrow}~ ~\frac{2}{3}~ ~\stackrel{R}{\rightarrow}~ ~\frac{3}{4}~ ~\stackrel{L}{\rightarrow}~ ~\frac{5}{7}~.


Comments

Please read the guidelines before commenting.



  • -12
    iamqazolp   commented on Oct. 13, 2022, 8:20 p.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -12
    iamqazolp   commented on Oct. 12, 2022, 6:28 p.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -5
    duyanhdizz   commented on Oct. 10, 2022, 10:02 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.