trang chủ / đề bài / blackfib

Phép tính Fibonacci trên bảng

Đề bài

Mô tả

Dãy Fibonacci được định nghĩa: f0=0, f1=1, fk=fk−2+fk−1 với k≥2.

Trên bảng có hai số: số trên là 0, số dưới là 1. Ta thực hiện lần lượt n 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 n thao tác xen kẽ bắt đầu bằng T (tức dãy TBTBTB…) thì số được ghi cuối cùng bằng fn+1.

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 (TT hoặc BB). Ví dụ, dãy TTTBBT có 3 lỗi và số được ghi cuối cùng là 10.

Cho n và r là số được ghi cuối cùng sau n 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 n thao tác cho kết quả r với số lỗi đó.

Dữ liệu vào

Một dòng gồm hai số nguyên n và r.

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 n ký tự T hoặc B, bắt đầu bằng T, là một dãy thao tác cho kết quả r với số lỗi đó. Nếu có nhiều đáp án, in một đáp án bất kỳ.

Ràng buộc

  • 1≤n,r≤106

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 f5=5.
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

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