E. Тэнгэр баганадсан барилгуудыг тоолсон нь

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

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

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

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

Шугамын дагуу хэд хэдэн тэнгэр баганадсан барилгууд баригдсан байна. Эдгээр барилгуудын тоог $2$-с $314!$ хүртэлх тоонуудын дундаас санамсаргүйгээр сонгосон (314-ийн факториал нь маш их тоо). Барилга бүрийн өндрийг нэг нэгнээс нь хамааралгүйгээр, санамсаргүй сонгосон ба бүх бүхэл тоо $i$-н хувьд барилгын өндөр $i$ байх магадлал нь $2^{ - i}$ байна. $i$ өндөртэй барилгын давхруудыг $0$-с $i - 1$ хүртэл дугаарлана.

Дамжин өнгөрөх хугацааг хурдасгахын тулд тэнгэр баганадсан барилгуудын хооронд агаарын утас татсан. Тодруулбал хоёр барилгын хооронд $i$ давхар агуулсан барилга байхгүй тохиолдолд л уг хоёр барилгын $i$-р давхруудыг холбосон агаарын шугам оршин байна.

Алис Боб хоёр тэнгэр баганадсан барилгуудын тоог тоолохоор шийдсэн.

Алис маш нягт хүн тул яг хэдэн ширхэг барилга байгааг мэдэхийг хүсч байна. Тэр хамгийн зүүн талын барилгаас эхлэн 1 гэж тоолж эхлэсэн. Тэгээд тэр баруун тийш явах ба дараагийн барилгаруу очих бүртээ тоон дээрээ нэгийг нэмнэ. Ингээд Алис хамгийн баруун талын барилга хүрэх хүртлээ үргэлжлүүлнэ.

Харин Боб бол тэвчээргүй нэгэн ба аль болох хурдан дуусгахыг хүснэ. Тэр хамгийн зүүн талын барилгаас эхлэн 1 гэж тоолно. Тэр барилгаас барилгын хооронд агаарын шугамуудыг ашиглан шилжинэ. Боб баруун тийш шилжих бүртээ баруун талд байгаа боломжит хамгийн өндөр агаарын шугамыг ашиглана, гэхдээ тэр өндрөөс айдаг учир $h$-с их өндөртэй давхруудыг алгасна. Боб агаарын шугамыг ашигласнаар дайран гарах барилгуудаа тоолохдаа маш хурдан явна. Үүний оронд тэр зүгээр л тоон дээрээ $2^{i}$ нэмсэн ба энд $i$ нь түүний одоо байгаа давхрын дугаар байна. Тэр хамгийн баруун талын барилга хүрэх хүртлээ үргэлжлүүлнэ.

Дараах жишээг авч үзье. Энд $1$, $4$, $3$, $4$, $1$, $2$ өндөрүүдтэй $6$ барилга байна мөн $h = 2$. Алис $1$ дугаараас эхлэн таван удаа $1$-г нэмж хариу нь $6$ гарна. Харин Боб $1$-с эхлэн тоолох ба дараа нь $1$-ийг нэмнэ, тэгээд $4$-г, $4$-г, $2$-г нэмж хариу нь $12$ гарна. Боб хамгийн өндөр агаарын шугамыг алгасна учир нь түүний айх өндөр нь $h = 2$.

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

Алис Боб хоёр хамгийн баруун талын барилга дээр ирээд тоонуудаа харьцуулна. Танд Алис эсвэл Бобын тоолсон тоо өгөгдөнө тэгээд та нөгөө нэгнийх нь тоолсон тооны утгыг тооцоолох ёстой.

Оролт

Оролтын эхний мөрөнд "$Alice$" эсвэл "$Bob$" гэсэн тэмдэгт мөрүүдийн аль нэг нь өгөгдөнө. Оролтын хоёр дахь мөрөнд хоёр бүхэл тоо $n$ ба $h$ ($2 ≤ n ≤ 30000$, $0 ≤ h ≤ 30$) байна. Хэрвээ эхний мөрийн тэмдэгт мөр "$Alice$" байвал $n$ нь Алисийн хамгийн баруун барилгад хүрэх үеийн тоо байх бол бусад тохиолдолд Бобын тоо байна. Харин $h$ нь Бобын ашилахыг хүсэж буй хамгийн өндөр давхрыг илэрхийлнэ.

Гаралт

Хэрвээ танд Бобын тоолсон утга өгөгдсөн бол Алисын тоон утгын тооцоолсон утгыг илэрхийлэх нэг бодит тоог хэвлэ, харин танд Алисийн тоон утга өгөгдсөн бол Бобын утгыг хэвлэ.

Таны хариултын үнэмлэхүй эсвэл харьцангуй алдаа нь $10^{ - 9}$-с ихгүй байвал зөвд тооцогдоно.

Орчуулсан: Г.Мэндбаяр

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

Оролт
Alice
3 1
Гаралт
3.500000000
Оролт
Bob
2 30
Гаралт
2
Оролт
Alice
2572 10
Гаралт
3439.031415943

Тэмдэглэл

Эхний жишээн дээр Бобын тоо 3 байх магадлал 62.5% бол 4 байх магадлал 25%, 5 байх магадлал 12.5% байна.

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