trang chủ / đề bài / icpc21_reg_l

Trái hay phải

Đề bài

Mô tả

Cho cây nhị phân đầy đủ gồm 230−1 đỉnh, các đỉnh được đánh số từ 1 đến 230−1. Gốc là đỉnh 1. Mỗi đỉnh i với 1≤i≤229−1 có đúng 2 con: con trái là đỉnh 2·i và con phải là đỉnh 2·i+1.

Ví dụ, 31 đỉnh đầu tiên của cây tạo thành 5 tầng: tầng 1 là đỉnh 1; tầng 2 gồm các đỉnh 2,3; tầng 3 gồm các đỉnh 4,5,6,7; tầng 4 gồm các đỉnh 8,…,15; tầng 5 gồm các đỉnh 16,…,31. Đỉnh 1 có con trái là 2 và con phải là 3, đỉnh 2 có con trái là 4 và con phải là 5, đỉnh 3 có con trái là 6 và con phải là 7, và cứ thế.

Với mỗi đỉnh n 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 n, 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 t, số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm một dòng chứa một số nguyên 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 n.

Ràng buộc

  • t≤1000.
  • 2≤n≤230−1.

Ví dụ

Input Output Giải thích
2
3
4
R
LL
Đỉnh 3 là con phải của gốc. Đỉnh 4 là con trái của đỉnh 2, còn đỉnh 2 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). 13=2·6+1 và 6=2·3, 3=2·1+1.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0