+ محدودیت زمان: ۲ ثانیه + حدودیت حافظه: ۲۵۶ مگابایت ---------- همانطور که از اسمش برمی‌آید، آقای خوش‌قلب به فکر ورزشکارها هم می‌باشد. او سری مسابقاتی ترتیب داده که ورزشکارهایی که المپیک نرفته‌اند حوصله‌شان سر نرود. (آقای خوش‌قلب خیلی به فکر شما نبود و سفارش نکرد که صورت سوال کوتاه برای شما بنویسیم؛ و ما نیز از فرصت سوء استفاده کردیم!) آقای خوش‌قلب به پیشنهاد یکی از دوستانش، پویان (که یک نوجوان تپل است) مسابقات اسب سواری در $M$ لیگ مختلف ترتیب داده. او این لیگ‌ها را با اعداد طبیعی نام گذاری کرده، بصورتی که لیگ ۱ از همه ساده تر است و سطح لیگ ۲ کمی بالاتر از لیگ ۱ است، ولی پایین‌ تر از لیگ ۳ است. و لیگ شماره $M$ از همه‌ی لیگ‌ها پیشرفته تر است. (عدد $M$ برابر عدد مهربانی آقای خوش‌قلب است. قلب رئوف او اجازه نمی‌دهد که لیگ‌های سخت تر از $M$ برگزار شود؛ بالاخره این ورزشکارها قرار نیست سختی بکشند که!) عمو که فردی بسیار پول پرست است، خبر این مسابقات را شنید و می‌خواهد که حتماً در آن‌ها شرکت کند. او ابتدا پیش آقای خوش‌قلب رفت و با او رفیق شد. حین صحبت‌هایشان، عمو گفته بود که می‌خواهد در این مسابقات شرکت کند و آقای خوش‌قلب هم به او گفته که در صورت بردن باید شیرنی بدهد! اما اگر عمو یک مسابقه را ببازد، آقای خوش‌قلب از سر مهربانی برای اینکه غم باخت را از دل عمو بیرون آورد به او مقداری پول می‌دهد تا خوش‌حال شود. عمو در ابتدا $S$ تومان همراهش هست و هرگاه که پولش به حداقل $T$ تومان برسد، مسابقات را رها کرده و به سراغ کارهای جانبی‌اش میرود. عمو می‌خواهد در چندین روز در مسابقات شرکت کند. در ابتدای هر روز او انتخاب می‌کند که در کدامین لیگ می‌خواهد مسابقه دهد. سپس او می‌تواند به تعداد دلخواهی دور در آن روز در لیگ انتخابی‌اش مسابقه بدهد. هزینه‌ی ورودی لیگ $x$، $x$ تومان است؛ پس عمو اگر در ابتدای روزی $a$ تومان داشته باشد نمیتواند در لیگ $a+1$ یا $a+2$ یا ... شرکت کند. عمو در هر دور مسابقه با احتمال $\frac 1 2$ برنده می‌شود و با احتمال $\frac 1 2$ مسابقه را می‌بازد. اگر عمو در یک دور بازنده شود، از لیگ حذف شده و در آن روز دیگر نمی‌تواند هیچ مسابقه‌ای بدهد.(در آن روز حتی در لیگ‌های دیگر نیز نمی‌تواند شرکت کند.) در انتهای هر روز آقای خوش‌قلب به سراغ عمو میرود تا خبر از شرکت عمو در مسابقات را از او بگیرد. (البته حین مسابقات هم او را زیر نظر دارد!) اگر عمو در این روز در لیگ $x$ مسابقه داده باشد و باخته باشد(مستقل از تعداد بردهای قبل از این باخت)، آقای خوش‌قلب به عمو $2 \times x$ تومان می‌دهد که این غم را فراموش کند. اما اگر او همه‌ی مسابقاتی که داده است را برده باشد، خوش‌قلب از او شیرنی طلب می‌کند. اولین مسابقه در لیگ $x$، $x$ تومان شیرنی دارد. دومین مسابقه $2 \times x$، سومی $4 \times x$ و ... $i$مین برد $2^{i-1} \times x$ تومان شیرنی دارد. اما خوش‌قلب بدلیل رأفت بسیار، در نهایت $x$ تومان پول شرکت در لیگ $x$ را از شیرنی‌ها کم میکند و باقی را از عمو طلب می‌کند. یعنی اگر عمو در این روز $k$ مسابقه را برده باشد، آقای خوش‌قلب از او $x \times (2^k - 2)$ تومان شیرنی طلب می‌کند. اگر عمو این مقدار پول نداشته باشد یا پس از پرداخت این پول، هیچ پولی برایش نماند جلوی آقای خوش‌قلب شرمنده می‌شود و از کل مسابقات کناره می‌گیرد. آقای خوش‌قلب هم کسی نیست که به زور این پول را از عمو بگیرد؛ پس از او می‌گذرد. (کمی هم از این‌که عمو دیگر نمی‌تواند در این مسابقات شرکت کند ناراحت می‌شود؛ بالاخره خوش‌قلب است دیگر!) قلب آقای خوش‌قلب هیچ‌وقت اجازه نمی‌دهد که مقداری که عمو بخاطر یک دور از مسابقه شیرنی می‌دهد از $M$تومان بیشتر باشد؛ پس هرگاه ببیند که عمو در دوری از مسابقه‌ای می‌خواهد شرکت کند که بیشتر از $M$ تومان شیرنی دارد، عمو را از شرکت در این دور از مسابقه باز می‌دارد. (دلیل وجود $M$ لیگ در مسابقات نیز همین است؛ چون قلب آقای خوش‌قلب اجازه نمی‌دهد کسی در لیگ با شماره بیشتر از $M$ شرکت کند، چون اگر بکند و رفیق آقای خوش‌قلب باشد بردن او بیش از $M$ تومان شیرنی دارد!) حال عمو می‌خواهد یک استراتژی برای شرکت در مسابقات برگزیند که احتمال رسیدن به هدف $T$ تومان در آن بیشترین مقدار ممکن باشد. با ورودی گرفتن مقدار $S$ و $T$ و $M$، این احتمال در بهترین استراتژی را به عمو بگویید. **چند مثال برای وضوح بیشتر:** اگر عمو در ابتدای یک روز ۵۰ تومان پول داشته باشد و مقدار مهربانی آقای خوش‌قلب ($M$) برابر ۶۰ باشد، او می‌تواند در روز اول در هریک از لیگ های ۱ و ۲ و ... و ۵۰ شرکت کند. فرض کنیم که او در لیگ شماره ۳۰ شرکت کرده (۳۰ تومان خرج میکند) و برنده شود. اکنون او باید ۰ تومان شیرنی بدهد. (۳۰ تومان این بردش شیرنی داشته که ۳۰ تومان ورود به مسابقات ازش کم شده.) اگر عمو انتخاب کند که یک دور دیگر نیز در این روز در این مسابقه شرکت کند، و دوباره برنده شود باید ۶۰ تومان شیرنی بدهد. (۶۰ تومان این مسابقه شیرنی داشته که به مقدار قبلی اضافه می‌شود.) در این وضعیت عمو دیگر نمی‌تواند در دور دیگری شرکت کند؛ زیرا آنگاه برد مسابقه‌ی بعدی‌اش ۱۲۰ تومان شیرنی خواهد داشت و این مقدار بیشتر از مقدار $M$ است. اما در همین مثال فرض کنید عمو در لیگ ۲۰ شرکت کند و برنده شود. اگر او در دور دیگری از مسابقات شرکت کند و این بار را ببازد، آقای خوش‌قلب به او ۴۰ تومان پول می‌دهد. پس از این روز مقدار پول عمو برابر ۷۰ می‌شود. (۵۰ تومان در ابتدا داشت و ۲۰ تومان برای شرکت در این لیگ هزینه کرد، سپس ۴۰ تومان از آقای خوش‌قلب گرفت.) حال او در روز دوم می‌تواند در همه‌ی ۶۰ لیگ‌ شرکت کند؛ یعنی لیگ ۱ و ۲ و ... و ۶۰. # ورودی در تنها سطر ورودی ۳ عدد طبیعی می آیند که با فاصله از هم جدا شده‌اند و به ترتیب نمایانگر مقادیر $S$ و $M$ و $T$ هستند. $$1 \le S, M, T \le 20$$ $$S < T$$ # خروجی در تنها سطر خروجی باید یک عدد اعشاری خروجی دهید که برابر احتمال رسیدن عمو به $T$ تومان است، اگر بهترین استراتژی را انتخاب کند. این عدد را با دقت دقیقاً ۴ رقم اعشار خروجی دهید. (عدد را گرد کنید. به نمونه‌ی سوم برای توضیح بیشتر دقت کنید!) # مثال ## ورودی نمونه ۱ ``` 1 1 3 ``` ## خروجی نمونه ۱ ``` 0.3333 ``` ## ورودی نمونه ۲ ``` 3 6 12 ``` ## خروجی نمونه ۲ ``` 0.5000 ``` ## ورودی نمونه ۳ ``` 4 20 15 ``` ## خروجی نمونه ۳ ``` 0.7556 ``` در نمونه‌ی ۳، جواب برابر ۰.۷۵۵۵۵۵۵ (با دور گردش ۵) است که پس از گرد شدن در چهار رقم اعشار برابر ۰.۷۵۵۶ می‌شود.

حل سؤال در بانک سؤالات