C. Гарах замаа таагаарай!

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

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

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

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

Амар "Гарах замаа таагаарай" хэмээх видео тоглоом худалдан авчээ. Тоглоомын зорилго нь $h$ өндөртэй бүрэн хоёртын мод хэлбэртэй оньсноос гарц хайх юм. Тоглогч эхлээд модны үндэс дээр байрлах ба гарц модны аль нэг навчинд байрлана.

Бүх навчнуудыг зүүнээс нь баруун тийш $1$-ээс $2^{h}$ хүртэл дугаарлая. Гарц $n$ ($1 ≤ n ≤ 2^{h}$) дэх навчин дээр байгаа. Тоглогч гарц хаана байгааг мэдэхгүй тул гарах замаа таах хэрэгтэй.

Амар замаа сонгохдоо дараах энгийн алгоритмыг дагана. "LRLRLRLRL..." гэсэн хязгааргүй үргэлжлэх тэмдэгт мөрөн дараалал бүхий коммандыг авч үзье. ("L" ба "R" тэмдэгтүүд сөөлжлөн орсон). Амар дараахь дүрмээр уг тэмдэгт коммандыг дарааллан гүйцэтгэнэ:

  • "L" тэмдэгт нь "Одоогийн оройн зүүн хүүхэд орой руу яв" гэсэн үг.
  • "R" тэмдэгт нь "Одоогийн оройн баруун хүүхэд орой руу яв" гэсэн үг.
  • Хэрэв очих орой руу өмнө нь ирж байсан бол Амар тухайн коммандыг алгасна.
  • Хэрэв Амар дараалсан хоёр комманд алгассан бол дараагийн коммандаа гүйцэтгэхээсээ өмнө тухайн оройн эцэг орой руу буцна.
  • Хэрэв ямар нэг гарц биш навчинд хүрвэл тухайн оройн эцэг орой руу буцна.
  • Хэрэв гарцанд хүрвэл тоглоом дуусна.

Амар хэрэв энэ алгоритмыг дагавал гарц хүртэл хэдэн орой дайрахыг мэдэхийг хүсчээ.

Оролт

Оролтод хоёр бүхэл тоо $h, n$ ($1 ≤ h ≤ 50$, $1 ≤ n ≤ 2^{h}$) байрлана.

Гаралт

Амар тухайн алгоритмыг ашиглан гарцыг оруулахгүйгээр нийт хэдэн оройг дайрсаныг илэрхийлэх бүхэл тоог хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
1 2
Гаралт
2
Оролт
2 3
Гаралт
5
Оролт
3 6
Гаралт
10
Оролт
10 1024
Гаралт
2046

Тэмдэглэл

$h$ өндөртэй бүрэн хоёртын мод гэдэг нь $h+1$ давхартай хоёртын мод юм. $0$ давхар нь үндэс гэгдэх ганц оройтой, $h$ давхар нь навч гэгдэх $2^{h}$ оройтой. Навчнаас бусад зангилаа бүр баруун, зүүн $2$ хүүхэд оройтой.

Дараахь зураг нь $3$-р жишээг харуулсан байна. Зангилаанууд дээр очсон дарааллын дугаар нь байрласан байна.

Сэтгэгдлүүдийг ачааллаж байна...