+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همانطور که از اسمش برمی‌آید، آقای خوش‌قلب به فکر همه است؛ حتی به فکر افراد معتاد. برای همین او از همه‌ی معتاد‌های سراسر کشور دعوت کرده که به پیش او بروند تا فکری به حالشان بکند. اولین معتاد امروز به پیش آقای خوش‌قلب رفت. آقای خوش‌قلب ابتدا باید "سطح اعتیاد" این فرد را معین کند. برای این کار، از شخص معتاد یک تست گرفته شد. آقای خوش‌قلب تعداد خیلی زیادی جسم روی میز گذاشت و به معتاد گفت که اجسام یکسان را بشمرد و روی کاغذی بنویسد از هر جسم چندتا روی میز موجود است. آقای خوش‌قلب سطح اعتیاد افراد را بصورت عددی طبیعی مشخص می‌کند و می‌دانیم که یک معتاد با سطح اعتیاد $k$، هر جسم روی میز را $k$بار می‌بیند. (پس به ازای هر جسم موجود عددی که روی کاغذ می‌نویسد $k$ برابر تعداد واقعی است.) حال آقای خوش‌قلب به خانه‌ی خود رفته و حین دیدن بازی‌های پرهیجان المپیک، می‌خواهد که سطح اعتیاد معتاد را بدست آورد. اما ناگهان متوجه می‌شود که یادش نمی‌آید چه تعداد از هر جسم روی میز بوده! با شتاب به سوی کیف خود رفته و برگه‌ی نوشته‌های معتاد را بیرون می آورد. او با تمام خوش‌قلبی خود، می‌خواهد بفهمد که حداقل چند جسم روی میز بوده است تا کمترین مقدار هزینه به مسئول چیدمان اجسام روی میز بدهد! (کمی خسیس هم هست) حال خوش‌قلب به سراغ شما آمده و با دادن اعداد نوشته‌شده روی کاغذ معتاد به شما، از شما می‌خواهد که بگویید کمترین مقدار ممکن برای تعداد اجسام روی میز چه قدر میتوانسته باشد. # ورودی در سطر ورودی یک عدد $n$ آمده است که نمایانگر تعداد اعداد روی کاغذ معتاد است. (که برابر تعداد اجسام مختلف روی میز است.) سپس در سطر دوم ورودی $n$ عدد آمده است که با فاصله از هم جدا شده‌اند و نمایانگر اعداد نوشته شده روی کاغذ هستند. $$ 1 \le n \le 1\ 000\ 000 $$ اعداد روی کاغذ کوچکتر مساوی $1\ 000\ 000\ 000$ هستند. # خروجی خروجی باید شامل یک عدد باشد که برابر کمترین تعداد اجسام ممکن روی میز است. # مثال ## ورودی نمونه ۱ ``` 3 5 5 10 ``` ## خروجی نمونه ۱ ``` 4 ``` اگر سطح اعتیاد معتاد برابر ۵ باشد، می‌توان گفت روی میز ۴ جسم بوده‌ است که ۲ تای آن یک شکل بودند. ## ورودی نمونه ۲ ``` 3 1 2 3 ``` ## خروجی نمونه ۲ ``` 6 ``` چون معتاد از یکی از اجسام تنها یک دانه دیده، سطح اعتیاد او تنها می‌تواند ۱ باشد پس همه‌ی اجسام گفته‌شده توسط معتاد روی میز موجود هستند؛ سه نوع جسم و از نوع اول یک دانه، از نوع دوم ۲ تا و از نوع سوم، ۳ تا.

سطح اعتیاد

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

همانطور که از اسمش برمی‌آید، آقای خوش‌قلب به فکر همه است؛ حتی به فکر افراد معتاد. برای همین او از همه‌ی معتاد‌های سراسر کشور دعوت کرده که به پیش او بروند تا فکری به حالشان بکند.

اولین معتاد امروز به پیش آقای خوش‌قلب رفت. آقای خوش‌قلب ابتدا باید "سطح اعتیاد" این فرد را معین کند. برای این کار، از شخص معتاد یک تست گرفته شد. آقای خوش‌قلب تعداد خیلی زیادی جسم روی میز گذاشت و به معتاد گفت که اجسام یکسان را بشمرد و روی کاغذی بنویسد از هر جسم چندتا روی میز موجود است. آقای خوش‌قلب سطح اعتیاد افراد را بصورت عددی طبیعی مشخص می‌کند و می‌دانیم که یک معتاد با سطح اعتیاد $k$ ، هر جسم روی میز را $k$ بار می‌بیند. (پس به ازای هر جسم موجود عددی که روی کاغذ می‌نویسد $k$ برابر تعداد واقعی است.)

حال آقای خوش‌قلب به خانه‌ی خود رفته و حین دیدن بازی‌های پرهیجان المپیک، می‌خواهد که سطح اعتیاد معتاد را بدست آورد. اما ناگهان متوجه می‌شود که یادش نمی‌آید چه تعداد از هر جسم روی میز بوده! با شتاب به سوی کیف خود رفته و برگه‌ی نوشته‌های معتاد را بیرون می آورد. او با تمام خوش‌قلبی خود، می‌خواهد بفهمد که حداقل چند جسم روی میز بوده است تا کمترین مقدار هزینه به مسئول چیدمان اجسام روی میز بدهد! (کمی خسیس هم هست)

حال خوش‌قلب به سراغ شما آمده و با دادن اعداد نوشته‌شده روی کاغذ معتاد به شما، از شما می‌خواهد که بگویید کمترین مقدار ممکن برای تعداد اجسام روی میز چه قدر میتوانسته باشد.

ورودی🔗

در سطر ورودی یک عدد $n$ آمده است که نمایانگر تعداد اعداد روی کاغذ معتاد است. (که برابر تعداد اجسام مختلف روی میز است.)

سپس در سطر دوم ورودی $n$ عدد آمده است که با فاصله از هم جدا شده‌اند و نمایانگر اعداد نوشته شده روی کاغذ هستند. $1 \le n \le 1\ 000\ 000$

اعداد روی کاغذ کوچکتر مساوی $1\ 000\ 000\ 000$ هستند.

خروجی🔗

خروجی باید شامل یک عدد باشد که برابر کمترین تعداد اجسام ممکن روی میز است.

مثال🔗

ورودی نمونه ۱🔗

3
5 5 10

خروجی نمونه ۱🔗

اگر سطح اعتیاد معتاد برابر ۵ باشد، می‌توان گفت روی میز ۴ جسم بوده‌ است که ۲ تای آن یک شکل بودند.

ورودی نمونه ۲🔗

3
1 2 3

خروجی نمونه ۲🔗

چون معتاد از یکی از اجسام تنها یک دانه دیده، سطح اعتیاد او تنها می‌تواند ۱ باشد پس همه‌ی اجسام گفته‌شده توسط معتاد روی میز موجود هستند؛ سه نوع جسم و از نوع اول یک دانه، از نوع دوم ۲ تا و از نوع سوم، ۳ تا.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همانطور که از اسمش بر می‌آید، خوش‌قلب به فکر آدم‌های بیکار هم هست. از این رو بر آن شده است تا اداره ای تاسیس کند و $n$ نفر را در آن استخدام کند. او الان در مرحله‌ی طراحی روند اداری این اداره است. او مرتبه‌ی اداری افراد را به صورت زیر چیده است: کارمند‌ها را به ترتیب ورود به شرکت، با اعداد طبیعی ۱ تا $n$ شماره‌گذاری کرده‌ایم. هرکس که به شرکت وارد میشود زیردست نفراتی میشود که قبلا وارد شرکت شده اند(نفر اول زیردست کسی نیست)؛ بنابراین کارمند شماره ۲ زیردست کارمند شماره ۱ است، کارمند شماره ۳ زیردست کارمند شماره ۲ و ۱ است، و ... . متاسفانه او به اندازه‌ی کافی پول ندارد تا بتواند وسایل تفریحی کافی برای شرکت بخرد. برای همین او تصمیم گرفته است که به کارمندان اجازه دهد که به هم پس گردنی بزنند!! البته هر کسی نمی‌تواند به هر کسی پس گردنی بزند بلکه یک فرد فقط به آن دسته از زیر دستانش می‌تواند پس گردنی بزند که قدشان از او کوچکتر باشد. از آنجایی که آقای خوش‌قلب آدم خاصی است، سلیقه‌ی خاصی هم دارد. او می‌خواهد قد افرادش اعداد طبیعی بین ۱ تا $n$ باشد و در عین حال قد هیچ دو نفری یکسان نباشد. همچنین او می‌خواهد افراد طبق سلیقه‌ی او بتوانند به هم پس گردنی بزنند؛ یعنی او به ازای هر دو نفری می‌گوید که آیا دوست دارد آن شخصی که مرتبه‌اش از آن یکی بالاتر است بتواند به او پس گردنی بزند یا نه. برای مثال فرض کنید که او بخواهد که کارمند شماره ۱ بتواند به کارمند شماره ۳ پس گردنی بزند. در این صورت او باید طوری افراد را استخدام کند به طوری که قد کارمند شماره ۱ از کارمند شماره ۳ بیشتر باشد. قد کارمند شماره $i$ را $h_i$ می‌نامیم. حالا آقای خوش‌قلب سلیقه‌اش را به شما می‌دهد و از شما می‌خواهد که به او بگویید که به ازای هر $i$، قد نفری که برای پست $i$ـم استخدام می‌شود باید چقدر باشد که در نهایت افراد مطابق سلیقه‌ی او بتوانند به هم پس گردنی بزنند. سلیقه‌اش را به صورت یک گراف جهتدار به شما می‌دهد به این صورت که او دوست دارد کارمند شماره $i$ بتواند به کارمند شماره $j$ ($i < j$) پس گردنی بزند اگر و تنها اگر در گرافی که به شما داده‌است، بین راس شماره $i$ و راس شماره $j$ یک یال جهتدار از $i$ به $j$ باشد. سلیقه‌ی آقای خوش‌قلب خاص است. پس سلیقه‌اش هم خاص است. پس گرافی که او به شما می‌دهد هم خاص است. این گراف دو ویژگی دارد: ۱. اگر در آن کارمند شماره $i$ به $j$ پس گردنی می‌زند و کارمند $j$ هم به $k$ پس گردنی می‌زند،‌($i < j < k$) حتما کارمند $i$ هم به $k$ پس گردنی می‌زند. (رابطه‌ی تعدی) ۲. هیچ یالی از بین دو راس طوری قرار نگرفته است که معنی اش این باشد که شخصی به بالا دستی اش پس گردنی بزند. مثلا هیچوقت یال جهتداری از راسی ۳ به راس ۱ وجود ندارد. به عبارتی دیگر هیچ یال جهتداری از راسی با شماره‌ی بزرگتر به راسی با شماره‌ی کوچکتر وجود ندارد. # ورودی در سطر اول ورودی دو عدد طبیعی $n$ و $m$ با فاصله از هم آمده است که نمایانگر تعداد کارمندها و تعداد پس‌گردنی‌های که هر روز زده می‌شود است. در هریک از $m$ سطر بعدی، به ترتیب دو عدد طبیعی $a$ و $b$ با فاصله آمده است که نشان میدهد آقای خوش‌قلب دوست دارد کارمند شماره $a$ به کارمند شماره $b$ پس‌گردنی بزند. $$ 1 \le n, m \le 100\ 000 $$ $$1 \le a < b \le n$$ تضمین می‌شود گراف ورودی دو شرط گفته شده را دارد. # خروجی اگر ورودی ها معتبر نبودند(شرکتی به این شکل وجود نداشت)، در تنها خط خروجی "No answer" چاپ شود. وگرنه در تنها سطر خروجی $n$ عدد با فاصله از هم چاپ کنید که که عدد $i$م نشان دهنده $h_i$ است در یک اداره‌ای که شرایط گراف گفته‌شده توسط خوش‌قلب را برقرار میکند. (یعنی نفر $a$ آن میتواند به $b$ پس‌گردنی بزند اگر و تنها اگر در گراف راس $a$ به $b$ یال داشته باشد.) # مثال ## ورودی نمونه ۱ ``` 2 1 1 2 ``` ## خروجی نمونه ۱ ``` 2 1 ``` ## ورودی نمونه ۲ ``` 3 2 1 2 1 3 ``` ## خروجی نمونه ۲ ``` 3 1 2 ```

یک اداره‌ی دولتی

محدودیت زمان: ۲ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

همانطور که از اسمش بر می‌آید، خوش‌قلب به فکر آدم‌های بیکار هم هست. از این رو بر آن شده است تا اداره ای تاسیس کند و $n$ نفر را در آن استخدام کند. او الان در مرحله‌ی طراحی روند اداری این اداره است. او مرتبه‌ی اداری افراد را به صورت زیر چیده است:

کارمند‌ها را به ترتیب ورود به شرکت، با اعداد طبیعی ۱ تا $n$ شماره‌گذاری کرده‌ایم. هرکس که به شرکت وارد میشود زیردست نفراتی میشود که قبلا وارد شرکت شده اند(نفر اول زیردست کسی نیست)؛ بنابراین کارمند شماره ۲ زیردست کارمند شماره ۱ است، کارمند شماره ۳ زیردست کارمند شماره ۲ و ۱ است، و ... .

متاسفانه او به اندازه‌ی کافی پول ندارد تا بتواند وسایل تفریحی کافی برای شرکت بخرد. برای همین او تصمیم گرفته است که به کارمندان اجازه دهد که به هم پس گردنی بزنند!! البته هر کسی نمی‌تواند به هر کسی پس گردنی بزند بلکه یک فرد فقط به آن دسته از زیر دستانش می‌تواند پس گردنی بزند که قدشان از او کوچکتر باشد.

از آنجایی که آقای خوش‌قلب آدم خاصی است، سلیقه‌ی خاصی هم دارد. او می‌خواهد قد افرادش اعداد طبیعی بین ۱ تا $n$ باشد و در عین حال قد هیچ دو نفری یکسان نباشد. همچنین او می‌خواهد افراد طبق سلیقه‌ی او بتوانند به هم پس گردنی بزنند؛ یعنی او به ازای هر دو نفری می‌گوید که آیا دوست دارد آن شخصی که مرتبه‌اش از آن یکی بالاتر است بتواند به او پس گردنی بزند یا نه. برای مثال فرض کنید که او بخواهد که کارمند شماره ۱ بتواند به کارمند شماره ۳ پس گردنی بزند. در این صورت او باید طوری افراد را استخدام کند به طوری که قد کارمند شماره ۱ از کارمند شماره ۳ بیشتر باشد. قد کارمند شماره $i$ را $h_i$ می‌نامیم.

حالا آقای خوش‌قلب سلیقه‌اش را به شما می‌دهد و از شما می‌خواهد که به او بگویید که به ازای هر $i$ ، قد نفری که برای پست $i$ ـم استخدام می‌شود باید چقدر باشد که در نهایت افراد مطابق سلیقه‌ی او بتوانند به هم پس گردنی بزنند.

سلیقه‌اش را به صورت یک گراف جهتدار به شما می‌دهد به این صورت که او دوست دارد کارمند شماره $i$ بتواند به کارمند شماره $j$ ( $i < j$ ) پس گردنی بزند اگر و تنها اگر در گرافی که به شما داده‌است، بین راس شماره $i$ و راس شماره $j$ یک یال جهتدار از $i$ به $j$ باشد.

سلیقه‌ی آقای خوش‌قلب خاص است. پس سلیقه‌اش هم خاص است. پس گرافی که او به شما می‌دهد هم خاص است. این گراف دو ویژگی دارد:

۱. اگر در آن کارمند شماره $i$ به $j$ پس گردنی می‌زند و کارمند $j$ هم به $k$ پس گردنی می‌زند،‌( $i < j < k$ ) حتما کارمند $i$ هم به $k$ پس گردنی می‌زند. (رابطه‌ی تعدی)

۲. هیچ یالی از بین دو راس طوری قرار نگرفته است که معنی اش این باشد که شخصی به بالا دستی اش پس گردنی بزند. مثلا هیچوقت یال جهتداری از راسی ۳ به راس ۱ وجود ندارد. به عبارتی دیگر هیچ یال جهتداری از راسی با شماره‌ی بزرگتر به راسی با شماره‌ی کوچکتر وجود ندارد.

ورودی🔗

در سطر اول ورودی دو عدد طبیعی $n$ و $m$ با فاصله از هم آمده است که نمایانگر تعداد کارمندها و تعداد پس‌گردنی‌های که هر روز زده می‌شود است. در هریک از $m$ سطر بعدی، به ترتیب دو عدد طبیعی $a$ و $b$ با فاصله آمده است که نشان میدهد آقای خوش‌قلب دوست دارد کارمند شماره $a$ به کارمند شماره $b$ پس‌گردنی بزند.

$1 \le n, m \le 100\ 000$ $1 \le a < b \le n$

تضمین می‌شود گراف ورودی دو شرط گفته شده را دارد.

خروجی🔗

اگر ورودی ها معتبر نبودند(شرکتی به این شکل وجود نداشت)، در تنها خط خروجی "No answer" چاپ شود.

وگرنه در تنها سطر خروجی $n$ عدد با فاصله از هم چاپ کنید که که عدد $i$ م نشان دهنده $h_i$ است در یک اداره‌ای که شرایط گراف گفته‌شده توسط خوش‌قلب را برقرار میکند. (یعنی نفر $a$ آن میتواند به $b$ پس‌گردنی بزند اگر و تنها اگر در گراف راس $a$ به $b$ یال داشته باشد.)

مثال🔗

ورودی نمونه ۱🔗

2 1
1 2

خروجی نمونه ۱🔗

2 1

ورودی نمونه ۲🔗

3 2
1 2
1 3

خروجی نمونه ۲🔗

3 1 2

+ محدودیت زمان: ۲ ثانیه + حدودیت حافظه: ۲۵۶ مگابایت ---------- همانطور که از اسمش برمی‌آید، آقای خوش‌قلب به فکر ورزشکارها هم می‌باشد. او سری مسابقاتی ترتیب داده که ورزشکارهایی که المپیک نرفته‌اند حوصله‌شان سر نرود. (آقای خوش‌قلب خیلی به فکر شما نبود و سفارش نکرد که صورت سوال کوتاه برای شما بنویسیم؛ و ما نیز از فرصت سوء استفاده کردیم!) آقای خوش‌قلب به پیشنهاد یکی از دوستانش، پویان (که یک نوجوان تپل است) مسابقات اسب سواری در $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 ``` در نمونه‌ی ۳، جواب برابر ۰.۷۵۵۵۵۵۵ (با دور گردش ۵) است که پس از گرد شدن در چهار رقم اعشار برابر ۰.۷۵۵۶ می‌شود.

یک سوال طولانی

محدودیت زمان: ۲ ثانیه
حدودیت حافظه: ۲۵۶ مگابایت

همانطور که از اسمش برمی‌آید، آقای خوش‌قلب به فکر ورزشکارها هم می‌باشد. او سری مسابقاتی ترتیب داده که ورزشکارهایی که المپیک نرفته‌اند حوصله‌شان سر نرود.

(آقای خوش‌قلب خیلی به فکر شما نبود و سفارش نکرد که صورت سوال کوتاه برای شما بنویسیم؛ و ما نیز از فرصت سوء استفاده کردیم!)

آقای خوش‌قلب به پیشنهاد یکی از دوستانش، پویان (که یک نوجوان تپل است) مسابقات اسب سواری در $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

در نمونه‌ی ۳، جواب برابر ۰.۷۵۵۵۵۵۵ (با دور گردش ۵) است که پس از گرد شدن در چهار رقم اعشار برابر ۰.۷۵۵۶ می‌شود.

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همانطور که از اسمش بر‌ می‌آید، خوش‌قلب به فکر وقت آدما هم هست. متاسفانه بین علما اختلاف افتاده است! پروفسور باقر (که یک کاربر ناشی است) با اون میمونه که تو بازی شطرنج کامپیوتری از همه قدرتش کمتره، سر موضوعی کل گذاشته است. آن‌ها به طور مشترک در قرعه کشی بانک شرکت کردند و یک کیسه‌ که داخلش $n$ سکه‌ی پول وجود دارد، برنده شده‌اند. متاسفانه آن‌ها برسر تقسیم سکه‌ها با هم قراری نگذاشتند و حالا یه مقدار بین علما اختلاف افتاده است. از این رو بر آن شده‌اند تا یک بازی راه بیندازند و برنده‌ی مسابقه، چون مسابقه را برده‌است، شیرینی بدهد! بازی به این شکل است: پروفسور باقر یک عدد $p$ انتخاب می‌کند. میمون هم یک عدد $q$ انتخاب می‌کند. حالا دو نفر به نوبت بازی می‌کنند. پروفسور باقر در نوبتش اگر حداقل $p$ سکه درون کیسه موجود بود، باید به اندازه‌ی مضربی طبیعی از $p$ از سکه‌های داخل کیسه بردارد و در جیبش بگذارد. اگر زمانی که نوبت پروفسور باقر می‌رسد کمتر از $p$ سکه درون کیسه باشد، پروفسور مجبور است که دقیقا $p$ سکه از جیبش داخل کیسه بگذارد. حرکت میمون هم به همین صورت است با این تفاوت که میمون برای انجام این حرکات به جای $p$، از $q$ استفاده می‌کند. برنده‌ی مسابقه کسی است که کیسه را خالی از سکه کند. (پس زمانی که داخل کیسه هیچ سکه‌ای نباشد، بازی متوقف می‌شود.) از آنجایی که شیرینی دادن به دوستان کار بسیار پسندیده‌ای است، هر کدام در تلاشند تا بازی را به ببرند. از این رو هر کدام به بهترین شکل ممکن بازی خود را انجام خواهند داد. نوبت اول با پروفسور است. متاسفانه چون بازی بر سر پول است، تعدادی آدم بیکار که از آن دور و ور رد می‌شدند، فکر کردند که بازی خیلی مهم است و برای همین به تماشای بازی پرداختند. تعدادی از آن‌ها هم برای تماشای بازی بلیط فروختند!! آقای خوش‌قلب که از آنجا رد می‌شد و این ماجرا را دید، تصمیم گرفت که با گفتن این که کی برنده می‌شود، بازی را بر همگان کسل کننده کند تا بلکه متفرق شده به زندگی‌شان برسند. (همه مثل چشمشون به آقای خوش‌قلب اعتماد دارند برای همین حرف ایشان سند است!) بعد اینجاست که مردم از بازی منحرف شده و مجذوب آقای خوش‌قلب می‌شوند (به خاطر پیش‌بینی‌‌هایش) و از او می‌خواهند که باز هم برای آن‌ها پیش‌بینی کند. مردم $t$ سناریو‌ی دیگر به آقای خوش‌قلب می‌دهند و از ایشان برنده را می‌خواهند. یعنی از او می‌پرسند که اگر عدد پروفسور و میمون و تعداد اولیه سکه‌های داخل کیسه اعدادی دیگر بود، برنده چه کسی بود. در اینجاست که چون آقای خوش‌قلب توانایی این پیش‌بینی‌ها را ندارد میگوید: ای مسابقه دهنده‌ی پر توان، برس به داد این ناتوان!! (شما را می‌گوید) # ورودی در سطر اول ورودی $t$ آمده است که تعداد سناریو‌ها را نشان می‌دهد. در $t$ خط بعد، در هر خط، اطلاعات یک سناریو آمده است: در هر خط که متعلق به یک سناریو است به ترتیب سه عدد $p$ و $q$ و $n$ با فاصله آمده است که به ترتیب نمایانگر عدد انتخاب پروفسور، عدد انتخابی میمون و تعداد اولیه سکه‌های داخل کیسه است. $$ 1 \le t \le 1000 $$ $$ 1 \le n,p,q \le 1000\ 000\ 000 $$ # خروجی خروجی شامل $t$ سطر است که در سطر $i$، باید پیش‌بینی متناسب با سناریوی $i$ خروجی داده شود. خروجی هر سناریو یکی از سه حالت زیر است: + PW: اگر پروفسور باقر بازی را می‌برد. + MW: اگر میمون بازی را می‌برد. + DW: اگر بازی تا بی‌نهایت ادامه پیدا می‌کند بدون اینکه کسی بازی را ببرد # مثال ## ورودی نمونه ``` 4 3 2 1 2 3 1 3 4 5 2 4 3 ``` ## خروجی نمونه ``` MW MW PW DW ``` توضیح سناریو‌ی اول: تعداد سکه‌ها برابر ۱ است که کمتر از ۳ می‌باشد. بنابراین پروفسور باقر مجبور است که ۳ عدد به تعداد سکه‌های داخل کیسه اضافه کند. در اینجا تعداد سکه‌ها ۴ تا می‌شود و میمون می‌تواند با برداشتن ۴ (که مضربی از ۲ است) سکه، کیسه را خالی نماید و برنده شود.

یک رالی نفس‌گیر

محدودیت زمان: ۰.۵ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

همانطور که از اسمش بر‌ می‌آید، خوش‌قلب به فکر وقت آدما هم هست. متاسفانه بین علما اختلاف افتاده است! پروفسور باقر (که یک کاربر ناشی است) با اون میمونه که تو بازی شطرنج کامپیوتری از همه قدرتش کمتره، سر موضوعی کل گذاشته است. آن‌ها به طور مشترک در قرعه کشی بانک شرکت کردند و یک کیسه‌ که داخلش $n$ سکه‌ی پول وجود دارد، برنده شده‌اند. متاسفانه آن‌ها برسر تقسیم سکه‌ها با هم قراری نگذاشتند و حالا یه مقدار بین علما اختلاف افتاده است. از این رو بر آن شده‌اند تا یک بازی راه بیندازند و برنده‌ی مسابقه، چون مسابقه را برده‌است، شیرینی بدهد! بازی به این شکل است:

پروفسور باقر یک عدد $p$ انتخاب می‌کند. میمون هم یک عدد $q$ انتخاب می‌کند. حالا دو نفر به نوبت بازی می‌کنند. پروفسور باقر در نوبتش اگر حداقل $p$ سکه درون کیسه موجود بود، باید به اندازه‌ی مضربی طبیعی از $p$ از سکه‌های داخل کیسه بردارد و در جیبش بگذارد. اگر زمانی که نوبت پروفسور باقر می‌رسد کمتر از $p$ سکه درون کیسه باشد، پروفسور مجبور است که دقیقا $p$ سکه از جیبش داخل کیسه بگذارد. حرکت میمون هم به همین صورت است با این تفاوت که میمون برای انجام این حرکات به جای $p$ ، از $q$ استفاده می‌کند. برنده‌ی مسابقه کسی است که کیسه را خالی از سکه کند. (پس زمانی که داخل کیسه هیچ سکه‌ای نباشد، بازی متوقف می‌شود.) از آنجایی که شیرینی دادن به دوستان کار بسیار پسندیده‌ای است، هر کدام در تلاشند تا بازی را به ببرند. از این رو هر کدام به بهترین شکل ممکن بازی خود را انجام خواهند داد. نوبت اول با پروفسور است.

متاسفانه چون بازی بر سر پول است، تعدادی آدم بیکار که از آن دور و ور رد می‌شدند، فکر کردند که بازی خیلی مهم است و برای همین به تماشای بازی پرداختند. تعدادی از آن‌ها هم برای تماشای بازی بلیط فروختند!! آقای خوش‌قلب که از آنجا رد می‌شد و این ماجرا را دید، تصمیم گرفت که با گفتن این که کی برنده می‌شود، بازی را بر همگان کسل کننده کند تا بلکه متفرق شده به زندگی‌شان برسند. (همه مثل چشمشون به آقای خوش‌قلب اعتماد دارند برای همین حرف ایشان سند است!) بعد اینجاست که مردم از بازی منحرف شده و مجذوب آقای خوش‌قلب می‌شوند (به خاطر پیش‌بینی‌‌هایش) و از او می‌خواهند که باز هم برای آن‌ها پیش‌بینی کند. مردم $t$ سناریو‌ی دیگر به آقای خوش‌قلب می‌دهند و از ایشان برنده را می‌خواهند. یعنی از او می‌پرسند که اگر عدد پروفسور و میمون و تعداد اولیه سکه‌های داخل کیسه اعدادی دیگر بود، برنده چه کسی بود. در اینجاست که چون آقای خوش‌قلب توانایی این پیش‌بینی‌ها را ندارد میگوید: ای مسابقه دهنده‌ی پر توان، برس به داد این ناتوان!! (شما را می‌گوید)

ورودی🔗

در سطر اول ورودی $t$ آمده است که تعداد سناریو‌ها را نشان می‌دهد. در $t$ خط بعد، در هر خط، اطلاعات یک سناریو آمده است:

در هر خط که متعلق به یک سناریو است به ترتیب سه عدد $p$ و $q$ و $n$ با فاصله آمده است که به ترتیب نمایانگر عدد انتخاب پروفسور، عدد انتخابی میمون و تعداد اولیه سکه‌های داخل کیسه است.

$1 \le t \le 1000$ $1 \le n,p,q \le 1000\ 000\ 000$

خروجی🔗

خروجی شامل $t$ سطر است که در سطر $i$ ، باید پیش‌بینی متناسب با سناریوی $i$ خروجی داده شود. خروجی هر سناریو یکی از سه حالت زیر است:

PW: اگر پروفسور باقر بازی را می‌برد.
MW: اگر میمون بازی را می‌برد.
DW: اگر بازی تا بی‌نهایت ادامه پیدا می‌کند بدون اینکه کسی بازی را ببرد

مثال🔗

ورودی نمونه🔗

خروجی نمونه🔗

MW
MW
PW
DW

توضیح سناریو‌ی اول: تعداد سکه‌ها برابر ۱ است که کمتر از ۳ می‌باشد. بنابراین پروفسور باقر مجبور است که ۳ عدد به تعداد سکه‌های داخل کیسه اضافه کند. در اینجا تعداد سکه‌ها ۴ تا می‌شود و میمون می‌تواند با برداشتن ۴ (که مضربی از ۲ است) سکه، کیسه را خالی نماید و برنده شود.