مسئله مربی ناامید

از سوالات ICPC 2007 تهران
جستجو:  

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

مربی می‌خواهد بداند چقدر احتمال دارد به این موفقیت دست پیدا کند و از شما کمک می‌خواهد. فرض کنید احتمال کسب برد، باخت و تساوی در مسابقه‌های بعدی از روی مسابقات انجام شده تا به حال به دست می‌آید. به عنوان مثال اگر این تیم از 10 بازی انجام داده قبلی 3 برد داشته باشد، احتمال برد در آینده 30% خواهد بود.

هجده تیم در این لیگ حضور دارند که همه آنها دو بازی رفت و برگشت با تیم‌های دیگر انجام می‌دهند. هر برد 3 امتیاز، هر تساوی 1 امتیاز و هر باخت صفر امتیاز دارد.

  [برگرد بالا]

ورودی برنامه

  [برگرد بالا]

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

  

5  11

3  5  4

2  3

5  0  5

3  5

5  5  4

1  1

1  1  1

0  0

  

خروجی برنامه

  [برگرد بالا]

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

  

4.3

75.0

42.8

66.7

  

منبع: مسابقه ICPC منطقه‌ای آسیا 2007 - سایت تهران - مسئله Hopeless Coach

  

حل مسئله

  [برگرد بالا]

ورودی‌های برنامه را به ترتیب n (تعداد بازی‌ها)، p (امتیازی که باید کسب شود)، w (تعداد بردها در گذشته)، d (تعداد تساوی‌ها در گذشته)، l (تعداد باخت‌ها در گذشته) در نظر بگیرید. اگر متغیرهای dp ،wp و lp برای ذخیره کردن احتمال برد، تساوی و باخت در هر یک از مسابقه‌های آتی تعریف شوند، بر اساس فرض‌های مسئله می‌توان نوشت:

  

\[ wp = \frac{w}{w+d+l} \] \[ dp = \frac{d}{w+d+l} \] \[ lp = \frac{l}{w+d+l} \]

  

در آینده n بازی انجام خواهد شد. اگر تعداد بردها برابر i و تعداد تساوی‌ها برابر j باشد، احتمال برد (Pw)، تساوی (Pd) و باخت (Pl) بر اساس اصول شمارش به این صورت می‌شود:

  

\[ P_d = \begin{pmatrix} n  \\ i \end{pmatrix} wp^i \] \[ P_w = \begin{pmatrix} n - i \\ j \end{pmatrix} dp^j \] \[ P_l = \begin{pmatrix} n - i - j \\ n - i - j \end{pmatrix} lp^{n-i-j} \]

  

این رویدادها مستقل از هم اتفاق می‌افتند. پس احتمال وقوع i برد، j تساوی و n - i - j باخت در n بازی به این صورت است:

  

\[ P = P_w \times P_d \times P_l = \begin{pmatrix} n \\ i \end{pmatrix} \begin{pmatrix} n - i \\ j \end{pmatrix} \; wp^i \; dp^j \; lp^{n-i-j} \]

  

حال اگر این احتمال را برای تمام انتخاب‌های ممکن i و j که شرط حداقل امتیاز را برآورده کند (یعنی 3i + j ≥ p) جمع بزنیم، احتمال موفقیت مربی به دست می‌آید:

  

  

\[ P_{total} = \sum_{i=0}^{n} \sum_{j=0}^{n-i}\begin{pmatrix} n \\ i \end{pmatrix} \begin{pmatrix} n - i \\ j \end{pmatrix} \; wp^i \; dp^j \; lp^{n-i-j} \]

  

پیاده‌سازی کد محاسبه این عبارت چندان دشوار نیست. مسئله اصلی به دست آوردن همین رابطه است.

  

نکته: ترکیب دو عدد صحیح نامنفی با رابطه زیر محاسبه می‌شود:

  

\[ \begin{pmatrix} n \\ r \end{pmatrix} = \frac{n!}{(n-r)!r!} \]

  

فاکتوریل عدد بزرگ، یک عدد بسیار بزرگ است که محاسبات را سخت می‌کند. یک روش دیگر محاسبه ترکیب دو عدد استفاده از رابطه بازگشتی زیر است:

  

\[ \begin{pmatrix} n \\ r \end{pmatrix} = \begin{pmatrix} n - 1 \\ r \end{pmatrix}  + \begin{pmatrix} n - 1 \\ r - 1 \end{pmatrix} \qquad, \qquad \begin{pmatrix} n \\ 0 \end{pmatrix}  = \begin{pmatrix} n \\ n \end{pmatrix} = 1 \]

  


تا کنون ۱۱ امتیاز ثبت شده
نوشته لایک نداشت؟
 
به اشتراک گذاری نوشته

algs.ir/spj8yf9

اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram


نام: *  

پست الکترونیک (محرمانه):

پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• امیرحسین
۹ دی ۱۳۸۶، ساعت ۲۲:۱۱

سلام خیلی خوب بود ممنون

• محمد رضا
۱۸ دی ۱۳۸۶، ساعت ۱۹:۴۷

تيم ما اين سوالو حل كرد البته خيلي طولاني تر شد

ممنون

بقيه سوالارو نميزاري ؟ مثلا سوال اول رو

• مرادی
۱۶ بهمن ۱۳۸۶، ساعت ۱۱:۲۳

سلام وخسته نباشید عرض میکنم خدمت تمامی طراحان و زحمت کشان سایت  www.aachp.ir :

امیدوارم که زندگی به کامتان باشد .

عذر خواهی می کنم که وقت گرانبهایتان را میگیرم .

چند خواهش و پیشنهاد از شما داشتم اول اینکه اگر متن انگلیسی سوالات ACM را دارید آنها را در سایت قرار دهید و دوم اینکه اگر امکان دارد یک بار دیگر کتاب  Art of Programming Contest را در سایت قرار بدهید سوم اینکه اگر اطللاعاتی در مورد مسابقات ACM دارید در سایت قرار بدهید مثال :1- تاریخچه مسابقات 2- تعداد اعضای تیم 3- تسلط بر کدام زبان بر نامه نویسی؟ 4- زمان تخمینی برگذاری مسابقات  انتخابی و اصلی  5- مکان بر گذاری مسابقات انتخابی  6- مکان بر گذاری مسابقات اصلی 7- معرفی تیمهای اول و دوم و سوم  واعضای تیمها در مسابقات انتخابی 8- معرفی تیمهای اول و دوم و سوم  واعضای تیمها در مسابقات اصلی 8- تعداد سوالات 9-پاسخ سوالات به کدام زبان نوشته میشوند و خلاصه تمامی اطلاعات مربوط به مسابقات ACM انتخابی و مسابقات اصلی 10- یک ایمیل برای سایت درست کنید و آدرسش را هم در سایت ذکر کنید 11- لینک مربوط به نقشه سایت خودتان را نیزدر سایت قرار دهید .

و در آخر یک انتقاد (که انشا اله..سازنده خواهند بود) و آن اینکه به سایت های مربوطه لینک نداده اید مثلا به سایت هایی که امکان دانلود زبان های برنامه نویسی را میدهند .

سایت بسیار خوبی را برای آموزش طراحی کرده اید ولی اطلاع رسانی خوبی در مورد مسابقات  (بخصوص (ACMندارید که انشا اله...رفع خواهد شد .

این هم ایمیل من اگر نیاز بود : l_morad_a@yahoo.com

آرزوی موفقیت و شاد کامی برای تک تک اعضای سایت دارم .یک بار دیگر عذر خواهی می کنم که وقت گرانبهایتان را گرفته ام - میگیرم و خواهم گرفت .  با تشکرات فراوان ارادتمند شما " مرادی".

• mohamad
۲۶ مرداد ۱۳۸۷، ساعت ۰۲:۰۹

doste aziz aval dorod dovom ye sar be site  man bezani mamnon misham sevom ham in ke agha in mosabeghate barname nevisi be che dardi mikhore kolan yani che sodi tosh hast va afrade motefareghe ham mitonan sherkat konan age tosh polam hast manam barname nevisi takhasosim ro el konam biyam mosabeghe bedam