← 返回题目列表

Codeforces · 217/B

B. 黑板斐波那契

中文机器翻译题面 查看原题

斐波那契数是整数序列:f0 = 0、f1 = 1、f2 = 1、f3 = 2、f4 = 3、f5 = 5、...、fn = fn - 2 + fn - 1。因此,接下来的每个数字都是前两个数字的总和。

Bajtek 开发了一种在黑板上计算斐波那契数的好方法。首先,他写了一个0。然后,他在其下面写了一个1。然后他执行了以下两个操作:

- 操作“T”:用两个数字之和替换顶部数字;
- 操作“B”:用两个数字之和替换底部数字。

如果他执行n次运算,从“T”开始,然后交替选择运算(这样运算顺序看起来像“TBTBTBTB...”),最后写入的数字将等于fn + 1。

不幸的是,Bajtek 有时会犯错误并连续重复操作两次或多次。例如,如果 Bajtek 想要计算 f7,那么他会想要执行 n = 6 次操作:“TBTBTB”。如果他改为执行操作序列“TTTBBT”,那么他将犯 3 个错误,并且他将错误地计算出第七个斐波那契数为 10。操作序列中的错误数是相邻相等操作(《TT》或《BB》)的数量。

您将获得 Bajtek 在尝试计算 fn + 1 时进行的运算次数 n 以及作为其计算结果的数字 r(即最后写入的数字)。找出 Bajtek 必须犯的最小可能错误数,以及导致 r 出现该错误数的任何可能的 n 个操作序列。

假设 Bajtek 始终以操作“T”正确启动。

输入

第一行包含整数 n 和 r (1 ≤ n, r ≤ 106)。

输出

输出的第一行应包含一个数字 — Bajtek 可能犯的错误的最小数量。第二行应包含 n 个字符,以“T”开头,描述具有一定数量错误的可能的操作序列。每个字符必须是“T”或“B”。

如果所需的序列不存在,则输出“IMPOSSIBLE”(不带引号)。

示例

输入 #1

6 10

输出 #1

2
TBBTTB

输入 #2

4 5

输出 #2

0
TBTB

输入 #3

2 1

输出 #3

IMPOSSIBLE