Trái hay phải
Đề bài
Mô tả
Cho cây nhị phân đầy đủ gồm đỉnh, các đỉnh được đánh số từ đến . Gốc là đỉnh . Mỗi đỉnh với có đúng con: con trái là đỉnh và con phải là đỉnh .
Ví dụ, đỉnh đầu tiên của cây tạo thành tầng: tầng là đỉnh ; tầng gồm các đỉnh ; tầng gồm các đỉnh ; tầng gồm các đỉnh ; tầng gồm các đỉnh . Đỉnh có con trái là và con phải là , đỉnh có con trái là và con phải là , đỉnh có con trái là và con phải là , và cứ thế.
Với mỗi đỉnh không phải gốc, đường đi từ gốc đến đỉnh này luôn gồm một số bước "đi xuống", mỗi bước ta đi từ đỉnh hiện tại xuống con trái hoặc con phải của nó. Vì vậy đường đi có thể được biểu diễn bằng một xâu gồm các ký tự L và R, lần lượt nghĩa là đi xuống con trái và đi xuống con phải.
Cho đỉnh , hãy tìm xâu biểu diễn đường đi từ gốc đến đỉnh này.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương , số bộ dữ liệu.
- Mỗi bộ dữ liệu gồm một dòng chứa một số nguyên .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra xâu biểu diễn đường đi từ gốc đến đỉnh .
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 4 |
R LL |
Đỉnh là con phải của gốc. Đỉnh là con trái của đỉnh , còn đỉnh là con trái của gốc. |
| 3 5 6 13 |
LR RL RLR |
Ví dụ bổ sung (không có trong đề gốc). và , . |
Bình luận