Phép tính Fibonacci trên bảng
Đề bài
Mô tả
Dãy Fibonacci được định nghĩa: , , với .
Trên bảng có hai số: số trên là , số dưới là . Ta thực hiện lần lượt thao tác, mỗi thao tác là một trong hai loại:
- T: thay số trên bằng tổng của hai số;
- B: thay số dưới bằng tổng của hai số.
Nếu thực hiện thao tác xen kẽ bắt đầu bằng T (tức dãy ) thì số được ghi cuối cùng bằng .
Tuy nhiên, đôi khi người tính lại thực hiện cùng một thao tác hai hoặc nhiều lần liên tiếp. Số lỗi của một dãy thao tác là số cặp thao tác kề nhau giống nhau ( hoặc ). Ví dụ, dãy có lỗi và số được ghi cuối cùng là .
Cho và là số được ghi cuối cùng sau thao tác. Biết rằng thao tác đầu tiên luôn là T. Hãy tìm số lỗi nhỏ nhất có thể và một dãy thao tác cho kết quả với số lỗi đó.
Dữ liệu vào
Một dòng gồm hai số nguyên và .
Dữ liệu ra
Nếu không tồn tại dãy thao tác thỏa mãn, in ra IMPOSSIBLE.
Ngược lại, dòng thứ nhất in số lỗi nhỏ nhất. Dòng thứ hai in một xâu gồm ký tự T hoặc B, bắt đầu bằng T, là một dãy thao tác cho kết quả với số lỗi đó. Nếu có nhiều đáp án, in một đáp án bất kỳ.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 10 | 2 TBBTTB |
Các cặp số lần lượt: (1, 1), (1, 2), (1, 3), (4, 3), (7, 3), (7, 10). Có 2 lỗi (BB và TT). |
| 4 5 | 0 TBTB |
Dãy xen kẽ đúng, cho . |
| 2 1 | IMPOSSIBLE | Sau 2 thao tác các số trên bảng là (1, 2), số ghi cuối là 2. |
Bình luận