Bedao Mini Contest 13 - FRACPATH
Xem dạng PDF
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ạ:
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}~. 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}~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.