Bedao Mini Contest 13 - FRACPATH - VNOJ: VNOI Online Judge

Bedao Mini Contest 13 - FRACPATH

Điểm: 0,25 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

bedao

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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ạ:

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}~.

Bình luận

Hãy đọc nội quy trước khi bình luận.

-14

iamqazolp đã bình luận lúc 13, Tháng 10, 2022, 13:20 ← chỉnh sửa →

Công thức tính con của 1 phân số Theo quan sát ta có: Gọi phân số đang xét là a/b và cha của nó là c/d, thì ta có con phía bên ngược với cha của nó =(a+c)/(b+d). Dễ hiểu hơn thì a/b là con bên trái của c/d thì ta tìm đc ngay con phía bên phải của a/b. Tiếp theo ta lại gọi a1/b1 và a2/b2 là 2 con của a/b. Thì ta có a1+a2=3a, b1+b2=3b. Từ nút 1/1 ta có thể dễ dàng tìm đc con của tất cả các nút còn lại với nhận xét: x/y < a/b thì x/y sẽ thuộc cây con gốc là nút con bên trái của a/b và ngược lại. Chúc các bạn thành công

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-13

iamqazolp đã bình luận lúc 12, Tháng 10, 2022, 11:28 ← chỉnh sửa →

test bai nay yeu qua. thoi gian chay gan nhu la o(1). neu ma cho test x=1 y=9e18 vao thi khong ai ac dc ca

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

duyanhdizz đã bình luận lúc 10, Tháng 10, 2022, 15:02

Mình có cách này để AC một cách dễ dàng hơn cách của ad (cách này thì mình chưa chứng minh được, ai có thể chứng minh được thì giải thích hộ mình nhé)

Ta khởi tạo một xâu S là xâu chứa đường đi ngắn nhất giữa phân số 1 / 1 và x / y

Ta xét 2 TH

TH1 : x >= y . Ta sẽ đi sang cây con bên phải x / y (lấy phần nguyên) lần (Ta cho vào xâu S), rồi ta cập nhật x = x % y;

TH2 : x < y . Ta sẽ đi sang cây con bên trái y / x (lấy phần nguyên) lần (Ta cho vào xâu S), rồi ta cập nhật y = y % x;

Ta sẽ thực hiện liên tục thao tác trên cho tới khi x == 0 || y == 0

Ta thấy sau khi thực hiện xong thì phân số x / y sẽ bằng 0 / 1 hoặc 1 / 0, mà đề bài bảo ta bắt đầu từ phân số 1 / 1 nên ta sẽ xóa thao tác cuối cùng của xâu S

Cuối cùng ta in ra xâu S :> Chúc các bạn 1 đấm AC

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.