B. Самбар дээрх Фибоначчи

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Фибоначчийн дараалал нь: $f_{0} = 0$, $f_{1} = 1$, $f_{2} = 1$, $f_{3} = 2$, $f_{4} = 3$, $f_{5} = 5$, $...$, $f_{n} = f_{n - 2} + f_{n - 1}$.

Бажтэк самбар дээр Фибоначчийн тоог олох гоё арга боловсруулжээ. Эхлээд $0$-г бичээд доор нь $1$-г бичнэ. Тэгээд $2$ үйлдэл гүйтэцгэнэ.

  • "$T$" үйлдэл: дээд талын тоог $2$ тооныхоо нийлбэрээр солино;
  • "$B$" үйлдэл: доод талын тоог $2$ тооныхоо нийлбэрээр солино;

"$T$"-ээр эхлэн $n$ үйлдэл ээлжлэн ("$TBTBTBTB$$...$") гүйцэтгэвэл $f_{n + 1}$ -г олох болно.

Харамсалтай нь Бажтэк заримдаа нэг үйлдлээ $2$ юмуу түүнээс олон удаа дарааллан хийж алдаа гаргадаг. Жишээ нь $f_{7}$-г олохын тулд $n = 6$ ("$TBTBTB$)" үйлдэл хийж олох ёстой харин оронд нь тэр "$TTTBBT$" үйлдэл хийсэн гэж үзвэл 3н алдаа гаргаж $f_{7} = 10$ гэж буруу олох болно. Алдаа гаргасан тоог үйлдлийн дараалалд ижил үйлдэлийг $2$ дарааллаж («$TT$» эсвэл «$BB$») хийсэн тоогоор олно.

Бажтэк $n$ үйлдэл хийж $f_{n + 1}$-г гаргаж авах гэж байгаад $r$ (Хамгийн сүүлд бичигдсэн тоо)-г гаргасан нь танд мэдэгдэж байгаа. Тэгвэл хамгийн бага алдаа гаргаж $n$ үйлдлээр $r$-г гаргаж авна уу.

Бажтэк үргэлж $T$-ээр эхэлдэг гэж үз.

Оролт

Эхний мөрөнд $n$ ба $r$ ($1 ≤ n, r ≤ 10^{6})$.

Гаралт

Эхний мөрөнд Бажтэкийн гаргасан хамгийн бага алдаа болох нэг бүхэл тоо. Хоёр дох мөрөнд "$T$"-ээр эхэлсэн $n$ үйлдлийн дараалал, энэ дараалал нь зөвхөн "$T$" эсвэл "$B$"-ээс бүтнэ.

Хэрвээ тийм дараалал олдохгүй бол "$IMPOSSIBLE$" гэж хэвлэнэ.

Орчуулсан: anhaabc

Жишээ тэстүүд

Оролт
6 10
Гаралт
2
TBBTTB
Оролт
4 5
Гаралт
0
TBTB
Оролт
2 1
Гаралт
IMPOSSIBLE
Сэтгэгдлүүдийг ачааллаж байна...