| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT122J - Bird tree |
Bird tree là một cây nhị phân vô hạn trong đó 5 mức đầu tiên được biểu diễn như sau:
Ta có thể biểu diễn công thức như sau:
Nhận xét rằng mỗi phân số trong cây trên đều xuất hiện duy nhất tại một vị trí và sẽ luôn tìm thấy xâu nghịch đảo của nó trên cây. Ta có thể biểu diễn một phân số nào đó trong cây bằng cách mô tả hướng đi từ node gốc. Ví dụ phân số 2/5 sẽ được biểu diễn là: LRR (sang trái, sang phải, sang phải). Bài toán đặt ra là cho biết trước phân số, tìm xâu biểu diễn hướng đi đến node chứa phân số đó.
Dữ liệu vào:
- Dòng 1 ghi số bộ test
- Mỗi bộ test ghi một phân số dạng a/b (1<=a,b<=109, a,b không cùng bằng 1 và thỏa mãn ước chung lớn nhất là 1)
Kết quả: Ghi ra trên một dòng xâu biểu diễn (các bộ test đều cho ra xâu dài không quá 10000 ký tụ)
Example
Input:3
1/2
2/5
7/3 Output:L
LRR
RLLR
| Được gửi lên bởi: | adm |
| Ngày: | 2012-02-25 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2017-02-03 05:41:14
ủa 1/2 tách thành 2/3 và 3/1 chứ nhỉ @@ |
|
|
2015-07-03 09:52:47 TICHPX
Từ 1/3 tại sao tách ra được 1/4 và 2/5 nhỉ |
|
|
2014-05-10 13:41:10 Black Hole
Cứ theo công thức đề bài mà giã :)) |
|
|
2013-05-19 14:11:40 an IM3 Ex-Member of Bit
có thể xây dựng cây này từ cây Stern http://www.cut-the-knot.org/blue/Stern.shtml . Cây Stern xây dựng dễ hơn. |
